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.
  1. Prepare
  2. Algorithms
  3. Greedy
  4. Luck Balance
  5. Discussions

Luck Balance

  • rajivaiyer
     + 0 comments

    Here's my solution in Java 8, which passes all test cases.

    The basic idea is to store the List<List<Integer>> into a List<ContestParams>. And then sort that in descending order, based first on impRating, and for the same impRating values, further sort based on descending order of luckBal. Once the list is sorted, then all simply iterate sequentially, and keep losing the first k "important contests", following which, all other "important contests" are won. And of course, lose all "non-important contests". And keep adding / subtracting the individual luckBal from the maxLuckBal total, to get the final result.

        static class ContestParams {
        Integer luckBal;
        Boolean impRating;

        public ContestParams(Integer luckBal, Boolean impRating) {
            this.luckBal = luckBal;
            this.impRating = impRating;
        }


        public Integer getLuckBal() {
            return luckBal;
        }

        public Boolean getImpRating() {
            return impRating;
        }

        @Override
        public String toString() {
            return "{" + luckBal + ", " + impRating + "}";
        }
    }

    /*
     * Complete the 'luckBalance' function below.
     *
     * The function is expected to return an INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER k
     *  2. 2D_INTEGER_ARRAY contests
     */

    public static int luckBalance(int k, List<List<Integer>> contests) {
        // Write your code here
        int maxLuckBal = 0;

        List<ContestParams> contestsParamsLst = new ArrayList<>();

        for (int cIdx = 0 ; cIdx < contests.size() ; cIdx++) {
            Integer luckBal = contests.get(cIdx).get(0);
            Boolean impRating = contests.get(cIdx).get(1) != 0 ? 
                                                Boolean.TRUE : Boolean.FALSE;
            contestsParamsLst.add(cIdx, new ContestParams(luckBal, impRating));
        }

        contestsParamsLst.sort(
            Comparator.comparing(ContestParams::getImpRating).reversed()
                      .thenComparing(ContestParams::getLuckBal, Comparator.reverseOrder())
        );
        
        int curNumImpContestsLost = 0;
        for (int cIdx = 0 ; cIdx < contestsParamsLst.size() ; cIdx++) {
            ContestParams curContestParams = contestsParamsLst.get(cIdx);

            if (!curContestParams.getImpRating() || 

                curNumImpContestsLost < k) {
                maxLuckBal += curContestParams.getLuckBal();
                if (curContestParams.getImpRating()) {
                    curNumImpContestsLost++;
                }

            } else {

                maxLuckBal -= curContestParams.getLuckBal();                

            }
        }

        return maxLuckBal;
    }