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.
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).
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);
}
}
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.
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).
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)
Luck Balance
You are viewing a single comment's thread. Return to all comments →
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).
I don't understand your explanation
import java.util.*; This is the solution came up with, the formatting might be a little easier to understand.
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.
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).
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)