- Practice
- Algorithms
- Greedy
- Luck Balance
- Discussions

# Luck Balance

# Luck Balance

nwhitcher + 5 comments The description would be clearer if it read "L is the amount of luck that can be gained by

*losing*the contest." She believes that luck is spent on wins and earned from losses.shesanmigz + 0 comments I got lost on that statement, too. I ignored it and focused on the example.

surajvermav38 + 1 comment Actually the description is intentionally made complex for increasing its value.

edrouwendaal + 1 comment i think you're right on this although you received downvotes

Abhishek_G0YAL + 0 comments # C++ Solution

# PASSES 100% OF TEST CASES ✅

# O(nlogn) TIME COMPLEXITY ✅

# SHORTEST CODE YOU CAN FIND IN C++! 🔥

#include <bits/stdc++.h> using namespace std; int main() { int n, k; cin >> n >> k; bool imp; vector<int> impContest; int luck, luckBalance = 0; for(int i = 0; i < n; i++) { cin >> luck >> imp; if(imp) impContest.push_back(luck); else luckBalance += luck; } sort(impContest.rbegin(), impContest.rend()); for(int luck : impContest) { if(k-- > 0) luckBalance += luck; else luckBalance -= luck; } cout << luckBalance << endl; }

FaxMachin3 + 3 comments # C# Code

int totalLuckBalance = 0; int impContestCount = 0; List<int> tempList = new List<int>(); int index = 0; for(int i = 0; i < contests.Length; i++){ if(contests[i][1] == 0) totalLuckBalance += contests[i][0]; else{ impContestCount ++; tempList.Add(contests[i][0]); totalLuckBalance += contests[i][0]; } } if(impContestCount > k){ tempList.Sort(); int n = impContestCount - k; for(int j = 0; j < n; j++){ totalLuckBalance -= 2 * tempList[j]; } } return totalLuckBalance;

kodido127 + 1 comment The complexity above is o(nlogn) because of the sort.

I have a solution with complecity of O(kn) which actually O(n):

We need to fill a matrix of 2D. Lines are contests and columns are the number of remaining imprortant contest failures:

## 0 1 2 3 ... K

## 0

## 1

## :

if this is a non-important contest then:

m[contest][k_left] = m[contest-1][k_left] + contest's luck

Otherwise we need to choose between failing or not failing the content (if we have remaining failures):

m[contest][k_left] = max ( m[contest-1][k_left] - contest's luck, m[contest-1][k_left+1] + contest's luck)

The 1st is a win, thus not changing the remaining failures.

The 2nd is a failure, thus we decreased the number of remaining failures from previous contest (k_left+1 --> k_left)

As for the last column, it means that we do decide not to fail at all.

aburduk + 0 comments Worse happens to your algorithm as k approaches n?

aburduk + 0 comments Shorter version:

`static int luckBalance(int k, int[][] contests) { var minLosses = contests .Where(x => x[1] == 1) .OrderByDescending(x => x[0]) .Skip(k) .Sum(x => x[0]); var totalVal = contests.Sum(x => x[0]); return totalVal - (minLosses * 2); }`

glm3531 + 1 comment totalLuckBalance -= 2 * tempList[j];

what is the reason for the 2*tempList[j]? Why do you need to subtract twice the value?

fred_knutson + 0 comments You need to multiply by 2 because you have already added it. So you need to remove what was added, and then remove the value.

sarathy_v_krish1 + 0 comments C++ solution :

int luckBalance(int k, vector<vector<int>> contests) { vector<int> imp; int luck=0; for (int i=0;i<contests.size();i++) { if (contests[i][1]) { imp.push_back(contests[i][0]); luck-=contests[i][0]; } else luck+=contests[i][0]; } sort(imp.begin(), imp.end(), greater<int>()); for (int i=0;i<min(k, (int)imp.size());i++) luck+=2*imp[i]; return luck; }

cris_kgl + 4 comments # Java Solution

### PASSES 100% OF TEST CASES ✅

### O(N) TIME COMPLEXITY ✅

### SHORTEST CODE YOU CAN FIND IN JAVA! 🔥

static int luckBalance(int k, int[][] c) { PriorityQueue<Integer> imp = new PriorityQueue<>(Collections.reverseOrder()); int luck = 0; for(int row = 0; row < c.length; row++){ if(c[row][1] == 0) luck += c[row][0]; else imp.offer(c[row][0]); } boolean decreaseLuck = false; while(!imp.isEmpty()){ if(k == 0) decreaseLuck = true; if(decreaseLuck == true) luck -= imp.poll(); else luck += imp.poll(); k--; }return luck; }

jiangyh91 + 0 comments Java Priority Queue is implemented using Heap Data Structures and Heap has O(log(n)) time complexity to insert and delete element.

dprathyusha252 + 2 comments Not sure why this has so many down votes. This is an efficient solution in Java 8

cris_kgl + 0 comments Thank you

jonzivku + 0 comments It is being downvoted because the poster excitedly proclaimed that their solution is O(n), without understanding that the PriorityQueue data structure itself is handling the sorting in O(n log n) time.

https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

We enque and deque - an O(log n) operation - n times. Hence O(n log n).

cris_kgi’s implementation is fine as a solution to the hackerrank problem, but it is not O(n), and they did not find the free lunch.

chakrabortybisw1 + 0 comments Wonderful code

chakrabortybisw1 + 2 comments Hello can you tell me when we should go for priority queues...

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.

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]rakeshreddy5566 + 0 comments [deleted]

SnoopDizzle + 6 comments I learned a funny thing by doing this... in C++, the vector.size() method returns an

*unsigned*int, so subtraction might silently wrap around to a large number, instead of a negative one. I can't believe I've never encountered this problem before...lausanne_man + 0 comments I haven't used C++ in over a decade but this implementation certainly makes sense. Would I have caught it right away - probably not!

Kartik1607 + 0 comments Had same problem. Was getting segmentation fault. Thanks buddy.

rwan7727 + 0 comments `int n,k; cin >> n >> k; vector <int> impt; int impt_sum=0; int unimpt_sum=0; for (int i=0;i<n;i++) { int luck,type; cin >> luck >> type; if (type) { impt.push_back(luck); impt_sum+=luck; } else unimpt_sum+=luck; } sort(impt.begin(),impt.end()); int isize=impt.size(); if (k<=isize) for (int i=isize-k-1;i>=0;i--) impt_sum-=(2*impt[i]); cout << impt_sum+unimpt_sum;`

parthkulkarni998 + 0 comments then what changes u did ?

parthkulkarni998 + 1 comment then how did u solved the thing ??

zutianluo + 0 comments u can cast unsigned int (which is returned by vector.size()) to int

zutianluo + 0 comments thx buddy..

acfromspace + 4 comments My

**updated**Python3 solution:def luckBalance(k, contests): # sort from greatest luck to least luck contests.sort(reverse=True) luck = 0 for contest in contests: if contest[1] == 0: luck += contest[0] elif k > 0: luck += contest[0] k -= 1 else: luck -= contest[0] return luck

It took a lot of whiteboarding to clearly put out what I wanted. Sorted the nested list by the first value, number of points, and from there chose which points I wanted to add and which points I needed to subtract. Thanks to @hubrando for the code review, took out an unnecessary variable and utilized an existing one.

knowsuchagency + 0 comments same idea, but your solution is much clearer and more concise

def luck_balance(k, contests): # group important and unimportant contests sorted_contests = sorted(contests, key=itemgetter(1)) groups = tuple(list(g) for k, g in it.groupby(sorted_contests, key=itemgetter(1))) if len(groups) > 1: unimportant, important = groups elif groups[0][0][1] == 0: unimportant, important = groups[0], [] else: unimportant, important = [], groups[0] # calculate how many matches we need to throw throws = len(important) - k if throws < 1: return sum(luck for luck, _ in important + unimportant) # start by sorting important contests to throw the smallest in terms of luck sorted_important = sorted(important) # group wins and losses losses, wins = sorted_important[:throws], sorted_important[throws:] # do math total = sum(luck for luck, _ in wins + unimportant) net = total - sum(luck for luck, _ in losses) return net

hubrando + 0 comments Good clean solution, very similar to what I did, but I didn't introduce a new important variable and just directly decremented k instead and checked if k was greater than 0 instead of important < k.

arunsai63 + 3 comments A slightly more python way -

def luckBalance(k, contests): total_luck = 0 for luck,important in sorted(contests, reverse=True): if not important: total_luck += luck elif k: total_luck += luck k -= 1 else: total_luck -= luck return total_luck

sivatoms + 0 comments How did you think of this way of solution???

ramya_mamidipaka + 0 comments why is the same program not running..when I copy pasted into IDE here,I am not understanding how to write the code in Hackerrank(I am new here but not to coding)

ajsmith22 + 0 comments You can trim it down just a bit more, though your method would probably be a bit clearer.

def luckBalance(k, contests): luck = 0 for lck, imp in sorted(contests, reverse=True): if k > 0 or not imp: luck += lck k -= imp else: luck -= lck return luck

junyiyang_snow + 0 comments Very clean answer. sort() is very useful. For loop is efficient by looping every list in the nested list.

Dmoneyskbow + 1 comment I solved the problem fine, but could someone help me understand why this is a greedy algorithm?

prashant_ravi812 + 0 comments While selecting competition to win you pick competition which is important and has least luck cost. Your solution is optimal at that instant that's why it is greedy.

Sort 406 Discussions, By:

Please Login in order to post a comment