nwhitcher 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 I got lost on that statement, too. I ignored it and focused on the example.
surajvermav38 Actually the description is intentionally made complex for increasing its value.
edrouwendaal i think you're right on this although you received downvotes
tao_zhang 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 very nice and elegant solution
abhishekbawa111 in the statement int result = total - 2*luckToFlip; why have you put 2*luckToFlip insted of just luckToFlip?
tao_zhang 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 I don't understand your explanation
aleksazen 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 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 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).
key_coder 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 because he has added that luck also which is need to be deleted so he deleted that twice.
daminiaglawe30 very nice solution
tat_lim 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 exactly same as mine.
jimaica [deleted]jimaica 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 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 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 Hi. Nice solution. For a challenge, try using quickselect to improve runtime like in this O(n) average runtime solution.
maneeshsagar thanks man
hooni 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 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 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 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 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 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 [deleted]
rakeshsenapathi [deleted]
sam_littlefair 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 [deleted]rakeshreddy5566 [deleted]
SnoopDizzle 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 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 Had same problem. Was getting segmentation fault. Thanks buddy.
rwan7727 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 then what changes u did ?
parthkulkarni998 then how did u solved the thing ??
zutianluo u can cast unsigned int (which is returned by vector.size()) to int
zutianluo thx buddy..
acfromspace My Python3 solution:
def luckBalance(k, contests): # sort from greatest luck to least luck contests.sort(reverse=True) luck, important = 0, 0 for contest in contests: if contest[1] == 0: luck += contest[0] elif important < k: luck += contest[0] important += 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.
knowsuchagency 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
notarealhacker Uhh.. what luck balance does she start with? The descriptions on hackerrank are always kinda iffy.
EDIT: Nevermind I figured out the wording. When she loses she gains that event's "luck". When she wins she loses that event's "luck".
So the question is how many events can she lose to gain the most amount of "luck" in the constraints set.
lausanne_man More specifically which events should she lose (if any) of the ones that she is allowed to lose based on the value of k.
Dmoneyskbow I solved the problem fine, but could someone help me understand why this is a greedy algorithm?
prashant_ravi812 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.
pepi_nedkova_pn commented Java solution :) it must be pretty optimal
// Idea: 1. find the sum of all luck values; 2. save the luck values of all the important contests in a list and sort it; 3. find the (number of contests to be won) minimum values of the list and subtract them twice from the sum (since they were already added once); 4. return the sum static int luckBalance(int k, int[][] contests) { int sum = 0; int rows = contests.length; ArrayList<Integer> sort = new ArrayList<>(); // find the sum of all the luck values; add all the luck values of the important contests to the ArrayList sort for (int i = 0; i < rows; i++){ sum += contests[i][0]; if (contests[i][1] == 1){ sort.add(contests[i][0]); } } // sort the ArrayList sort Collections.sort(sort); // the number of contests to be won = num important - num to be lost // we subtract 1 from this number, since we use numLostImportant as an index in the while-loop int numLostImportant = sort.size() - k - 1; // since sort is already sorted, we subtract the first (and lowest) sort.size() - k values TWICE (firstly, to subtract them from the sum; secondly, to subtract them since they will be won) while (numLostImportant > -1){ sum -= 2*sort.get(numLostImportant); numLostImportant--; } return sum; }
nyhack56 C# passed all tests:
- Loop through contests array
- Add any non-important contests L to a running total
- Add any import contests L to a list
- Sort and reverse the list
- Loop through the list a. Add the L to total for x = 0 to k b. After that, subtract the rest of the L values in the list
// Complete the luckBalance function below. static int luckBalance(int k, int[][] contests) { int total = 0; List<int> impWins = new List<int>(); for(int x= 0; x < contests.GetLength(0); x++) { if(contests[x][1] == 1) impWins.Add(contests[x][0]); else total += contests[x][0]; } impWins.Sort(); impWins.Reverse(); for(int x = 0; x < impWins.Count; x++) { if (x < k) total += impWins[x]; else total -= impWins[x]; } return total; }
GregBarber As a long LINQ one liner for fun:
static int luckBalance(int k, int[][] contests) { return contests.Select(contest => new { Luck = contest[0], Importance = contest[1] }).OrderByDescending(contest => contest.Luck).Select(contest => (contest.Importance == 1 && k-- <= 0) ? -contest.Luck : contest.Luck).Sum(); }
trkmos javaScript solution
function luckBalance(k, contests) { let important = contests.filter(ar => ar[1] === 1).length; let sumAll = contests.reduce((a, b) => a+b[0],0); let sorted = contests.sort((a, b) => a[0] - b[0]) let win = important-k >=0 ?important-k : 0 let min = 0 for(let i=0; i<sorted.length; i++){ if(win === 0) break; if(sorted[i][1] === 0)continue; min += sorted[i][0]; win-- } return sumAll - (2*min); }
jrcastillo2001 There seems to be a lot of loops, with this solutions is the time complexity a: O(n*3) + O(m) ... n being constests - m being sorted ... ?
how about this for a change ?
function luckBalance(k, contests) { const importantContestsVals = [] let val = 0; for (let i = 0; i < contests.length; i++) { if (contests[i][1]) { importantContestsVals.push(contests[i][0]) } else { val += contests[i][0] } } importantContestsVals.sort((a, b) => a - b) const negativeArr = importantContestsVals.splice(0, importantContestsVals.length - k) const largestArr = negativeArr.length >= importantContestsVals.length ? negativeArr.length : importantContestsVals.length for (let j = 0; j < largestArr; j++) { if (negativeArr[j]) { val -= negativeArr[j] } if (importantContestsVals[j]) { val += importantContestsVals[j] } } return val }
prateek181996 Faling Testcase 6,7,8
#include<iostream> #include<algorithm> using namespace std; int main() { int n,k,imp=0,x,j=0,m=0; cin>>n>>k; int l[n],t[n],c[n],d[n]; for(int i=0;i<n;i++) { cin>>l[i]; cin>>t[i]; } for(int i=0;i<n;i++) { if(t[i]==1) { imp++; c[j++]=l[i]; } else if(t[i]!=1) { d[m++]=l[i]; } } x=imp-k; sort(c,c+j); int s1=0,s2=0,s3=0; for(int i=0;i<x;i++) { s1=s1+c[i]; } for(int i=x;i<j;i++) { s2=s2+c[i]; } s2=s2-s1; for(int i=0;i<m;i++) { s3=s3+d[i]; } cout<<s2+s3; return 0; }
Rishabhkv Me too have encountered the same problem,I didn't know why,but I too have same problem,can someone just help us out?
danny10846 You have to account for when there are fewer important tests than number of tests she's allowed to fail.
prachi_1312 you have not taken into consideration the cases when number of unimportant cases are more than or equal to important cases
rajatddjsehgal you have initialized the value of x=imp-k; but as we can assign any value to k,therefore if k>imp :- then x will be negative and after that you have used that x in the for loop also , in which when you have used c[i] where i=x;i
Sort 276 Discussions, By:
Please Login in order to post a comment