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.
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 →
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)