We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Loading...
  1. Practice
  2. Algorithms
  3. Greedy
  4. Luck Balance
  5. Discussions

Luck Balance

  • tao_zhang + 16 comments

    This is the same problem I have done in Week Of Code 21. I copied my solution in Java:

    import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int total = 0;
        List<Integer> importantContests = new ArrayList<>();
        for (int i=0; i<n; i++){
            int luck = scanner.nextInt();
            int importance = scanner.nextInt();
            total += luck;
            if (importance == 1) {
                importantContests.add(luck);
            } 
        }
        Collections.sort(importantContests);
        int luckToFlip = 0;
        int mustWinImprCount = importantContests.size() - k;
        for (int i=0; i<mustWinImprCount; i++){
            luckToFlip += importantContests.get(i);
        }
        int result = total - 2*luckToFlip;
        System.out.println(result);
    }
}
    • bingo_22 + 0 comments

      very nice and elegant solution

    • abhishekbawa111 + 2 comments

      in the statement int result = total - 2*luckToFlip; why have you put 2*luckToFlip insted of just luckToFlip?

      • tao_zhang + 1 comment

        In the description of this problem, it says "If Lena wins the contest, her luck balance will decrease by L; if she loses it, her luck balance will increase by L." I added all the "luck" to total assuming she loses all in the beginning. Winning those games should not only NOT "increase by L" (-luckToFlip to make it even), it should also "decrease by L" (-luckToFlip again).

        • SherMM + 3 comments

          I don't understand your explanation

          • aleksazen + 1 comment

            import java.util.*; This is the solution came up with, the formatting might be a little easier to understand.

            public class Solution {
   public static void main(String[] args) {
       Scanner in = new Scanner(System.in);
       int numContests = in.nextInt();
       int maxLosses = in.nextInt();
       ArrayList<Integer>contestLucks = new ArrayList<Integer>();
       int totalLuck = 0;
       for(int i = 0;i<numContests;i++){
           int currContestLuck = in.nextInt();
           int temp = in.nextInt();
           if(temp ==0)totalLuck+=currContestLuck;
           else contestLucks.add(currContestLuck);
       }
       Collections.sort(contestLucks);
       for(int i = 0;i<contestLucks.size();i++){
           if(i<contestLucks.size()-maxLosses)totalLuck-=contestLucks.get(i);
           else totalLuck +=contestLucks.get(i);
       }
       System.out.println(totalLuck);
   }
}
            • tat_lim + 0 comments

              Unfortunately, the "Collections.sort" method degrades the performance to O(N*log(N)). Besides, the "ArrayList" collection uses an additional O(N) amount of memory. An optiomal solution should run in O(N*log(K)) time and use O(K) space.

          • floshaban + 0 comments

            In terms I can even understand: Essentially he got the total luck, (all positive), then you remove the luck from winning contests (neutral) but you actually LOSE luck from winning contests, so you need to go negative (take it away again).

          • [deleted] + 0 comments

            Multiplying with 2 as we have already calculated the luck in total luck so if we are losing the competition instead of gaining X point we are losing the X point so luck = (total - 2 * X)

      • mail9deep + 0 comments

        because he has added that luck also which is need to be deleted so he deleted that twice.

    • daminiaglawe30 + 0 comments

      very nice solution

    • tat_lim + 0 comments

      Unfortunately, the "Collections.sort" method degrades the performance to O(n*log(n)). Besides, the "List" collection uses an additional O(n) amount of memory. An optiomal solution should run in O(n*log(k)) time and use O(k) space.

    • pariharyash6 + 0 comments

      exactly same as mine.

    • jimaica + 0 comments
      [deleted]
    • jimaica + 2 comments

      Very nice! Based on this i wrote it in c#

      var temp = Console.ReadLine().Split(' ');
var arr = Array.ConvertAll(temp, Int32.Parse);
var N = arr[0];
var K = arr[1];
List<Tuple<int, int>> luckBalance = new List<Tuple<int, int>>();
for (var contest = 0; contest < N ; contest++){
    var ln_temp = Console.ReadLine().Split(' ');
    var ln = Array.ConvertAll(ln_temp, Int32.Parse);
    var luck = ln[0];
    var importance = ln[1];
    luckBalance.Add(Tuple.Create(luck, importance));
}
var importanContests = luckBalance.Where(u => u.Item2 == 1).Select(u => u.Item1).OrderBy(u=>u).ToList();
var luckSum = luckBalance.Select(u => u.Item1).Sum();
int luckToFlip = 0;
int mustWinImprCount = importanContests.Count() - K;
for (int i = 0; i < mustWinImprCount; i++)
{
    luckToFlip += importanContests[i];
}
int result = luckSum - 2 * luckToFlip;        
Console.Write(result);
      • Shrihari_stark + 0 comments

        Some performance add-ons would be to just add the zero luck values directly to the resultant luck. The new array would only contain the must win.

        Sort the array(O(k * log(k)) where k is the number of 1s).

        Finally, Iterate the 1s array and where for each n: if(k <= 0) => result = result - n; else => result = result + n; k--;

        Basically, accumulate all the luck you can until you run out of k, once k is zero, start reducing your luck (you will be spending least luck value for reduction)

      • nikolay_em + 0 comments

        there is my code, works

        static int luckBalance(int k, int[][] contests)
{
int result = contests.Where(_ => _[1] == 0).Sum(_ => _[0]);

int[] important = contests.Where(_ => _[1] == 1).Select(_ => _[0]).OrderByDescending(_ => _).ToArray();

result += important.Take(k).Sum() - important.Skip(k).Sum();

return result;
}
    • RodneyShag + 0 comments

      Hi. Nice solution. For a challenge, try using quickselect to improve runtime like in this O(n) average runtime solution.

      HackerRank solutions.

    • maneeshsagar + 0 comments

      thanks man

    • hooni + 0 comments

      would it improve the performance if we replace the last part with

      Iterator<Integer> iter = list.iterator();
while(list.size() > k) {
	totalLuck -= 2*iter.next();
	k++;
}
return totalLuck;

      ?

    • akhilvaibhav1 + 0 comments

      for a test case n == k wont the line 

      int mustWinImprCount = importantContests.size() - k;

      cause a problem, Since Arraylist size is less than n, the variable mustWinImprCount will be initialized with negative value causing the for loop to cease in the beginning?

    • dylanvanderberg + 1 comment

      Why not use a heap (PriorityQueue in Java) to remove the need for the O(nlog(n)) operation of sorting the array. Adding to a heap is O(log(n)) in worst-case, but O(1) in the average case. Since that happens n times, it should be faster on average. See my implementation: 

         // Complete the luckBalance function below.
    static int luckBalance(int k, int[][] contests) {
        int numLuck = 0;
        int totalImportant = 0;
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(new Comparator<Integer>(){
            @Override
            public int compare(Integer obj1, Integer obj2){
                return obj1 - obj2;
            }
        });
        for(int[] contest : contests){
            numLuck += contest[0];
            if(contest[1] == 1){
                minHeap.offer(contest[0]);
                totalImportant++;
            }
        }
        for(int i = 0; i < totalImportant - k; i++){
            numLuck -= 2 * minHeap.poll();
        }
        return numLuck;
    }
      • Shrihari_stark + 2 comments

        You will be adding n elements to your heap. For each insert it is logn and therefore for n elements, it would be n * log n. No difference is performance. Since there won't be anymore addition/deletion after the sort, it would not make any difference to choose heap over list.

        • douglasdejesus92 + 0 comments

          Instead of letting the heap grow, keep it at size k. Now, each insert is logk instead of logn, and the total complexity is therefore nlogk.

        • michael_armes + 0 comments

          As mentioned elsewhere, the heap should be kept at k. Average case, insertion is O(1), so the average case complexity of the overall luck balance algorithm in O(n). Worst case is O(nlogk). Therefore, only in the worst case scenario, and also when k=n, does the algorithm implementing the heap perform the same as the sort. In all other cases, the heap outperforms.

    • kalama449 + 0 comments
      [deleted]
    • rakeshsenapathi + 0 comments
      [deleted]
    • sam_littlefair + 0 comments

      Just completed this problem and this solution is eerily similar to mine:

      static int luckBalance(int k, int[][] contests) {
    List<Integer> important = new ArrayList<Integer>();
    int totalLuck = 0;
    for(int i = 0; i < contests.length; i++){
         if(contests[i][1] == 1){
             important.add(contests[i][0]);
         }
        totalLuck += contests[i][0];
    }
    int canWin = important.size() - k, score = 0;
    Collections.sort(important);
    for(int i = 0; i < canWin; i++){
        score += 2 * important.get(i);
    }

    return totalLuck - score;
}

      Great minds think alike? haha

    • rakeshreddy5566 + 1 comment
      [deleted]