You are viewing a single comment's thread. Return to all comments →
Using QuickSelect, you can get an O(n) average-case solution.
The full solution is in my HackerRank solutions. Here is a snippet of the code.
public static void main(String[] args) { Scanner scan = new Scanner(System.in); int N = scan.nextInt(); int K = scan.nextInt(); ArrayList<Integer> contest = new ArrayList<>(N); int savedLuck = 0; for (int i = 0; i < N; i++) { int luck = scan.nextInt(); int importance = scan.nextInt(); if (importance == 0) { savedLuck += luck; // lose every non-important contest } else { contest.add(luck); } } scan.close(); /* Compete in "important" contests */ quickselect(contest, 0, contest.size() - 1, contest.size() - K); for (int i = 0; i < contest.size(); i++) { if (i < contest.size() - K) { savedLuck -= contest.get(i); // win contest } else { savedLuck += contest.get(i); // lose contest } } System.out.println(savedLuck); }
Let me know if you have any questions.
Seems like cookies are disabled on this browser, please enable them to open this website
Luck Balance
You are viewing a single comment's thread. Return to all comments →
Java O(n) solution
Using QuickSelect, you can get an O(n) average-case solution.
The full solution is in my HackerRank solutions. Here is a snippet of the code.
Let me know if you have any questions.