Sort by

recency

|

930 Discussions

|

  • + 0 comments

    Here is my intuition for solving this problem:

    Lena is ultimately trying to maximize her luck. We have a list of contests along with their luck and whether they are important or not. In a perfect world she would just bank as much luck as possible and lose every contest, but there is a constraint that stops her from doing this. You can only lose k important contests. So I thought of k as special tokens that I can spend. So for each contest you have 3 scenarios:

    1. If it's not important lose it and keep the luck.
    2. If is it important and you have special (k > 0) left spend 1 token, lose it and keep the luck.
    3. If it's important and you are out of tokens (k < 0) then you have to win it.

    Lena wants to maximize her luck, so if she spends a special token, it better be worth it. In other words be greedy and only spend tokens on the contests that will get you the most luck. With this as a guide you can sort the contests by luck in descending order, then pick the contests that will get you the most luck while spending special tokens. Because the contests are sorted by luck, when you spend a special token (k-= 1) on a contest i, you can be sure that there is no other contest that you can spend a special token on, that will get you more luck or else it would occur before contest i in the array, meaning that you have the optimal solution.

    Running Time:

    1. Sorting the array: O(n log n)
    2. scanning the array while spending special tokens: O(n)

    Because O(n) is bounded above by O(n log n) the running time of this algorithm is O(n log n)

    Python Solution:

    def luckBalance(k, contests):
        # sort by luck
        contests = sorted(contests, key=lambda contest: contest[0], reverse=True)
        max_luck = 0
        for contest in contests:
            if contest[1] == 0:
                max_luck += contest[0]
            elif contest[1] == 1 and k > 0:
                max_luck += contest[0]
                k -= 1
            elif contest[1] == 1 and k == 0:
                max_luck -= contest[0]
        return max_luck
    
  • + 0 comments
    public static int luckBalance(int canlose, List<List<Integer>> contests) {        
        List<Integer> prioritycontestluck = new ArrayList<>();
        List<Integer> optionalcontestluck = new ArrayList<>();
    
        for(int i=0;i<contests.size(); i++) {
            List<Integer> lst = contests.get(i);
            int priority = lst.get(1);
            int luck = lst.get(0);
            if(priority==1) {
                prioritycontestluck.add(luck);
            } else {
                optionalcontestluck.add(luck);
            }
        }
    
        Collections.sort(prioritycontestluck);
        int mustwin = prioritycontestluck.size()-canlose < 0 ? 0 : prioritycontestluck.size()-canlose;
        int maxluck = 0;
        for(int i=0;i<mustwin;i++) {
            maxluck -= prioritycontestluck.get(i);
        }
    
        for(int i=mustwin;i<prioritycontestluck.size();i++) {
            maxluck += prioritycontestluck.get(i);
        }
    
    
        for(int i=0;i<optionalcontestluck.size();i++) {
            maxluck += optionalcontestluck.get(i);
        }
        return maxluck;
    }
    
  • + 0 comments
    def luckBalance(k, contests):
        all_l = 0
        ls_ls = []
        for row in contests:
            if row[1] == 0:
                all_l += row[0]
            elif row[1] == 1:
                ls_ls.append(row[0])
        
        ls_ls = sorted(ls_ls, reverse=True)
        all_l = all_l + sum(ls_ls[:k]) - sum(ls_ls[k:])
        return all_l
    
  • + 0 comments

    public static int luckBalance(int k, List> contests) { PriorityQueue que = new PriorityQueue<>(); // min-heap int sum = 0;

    for (int i = 0; i < contests.size(); i++) {
        int l = contests.get(i).get(0);
        int imp = contests.get(i).get(1);
        if (imp == 1) {
            que.add(l);
        } else {
            sum += l; 
        }
    }
    while (que.size() > k) {
        sum -= que.poll(); 
    }
    while (!que.isEmpty()) {
        sum += que.poll();
    }
    return sum;
    
    }
    
  • + 0 comments

    Here is my c++ solution, you can watch the explanation here : https://youtu.be/7L1lI6JScR8

    int luckBalance(int k, vector<vector<int>> contests) {
        sort(contests.begin(), contests.end(), [](vector<int> l, vector<int>r){
            return l[0] > r[0];
        });
        int ans = 0, im = 0;
        for(int i = 0; i < contests.size(); i++){
            if(im < k || contests[i][1] == 0) ans += contests[i][0];
            else ans -= contests[i][0];
            if(contests[i][1] == 1) im++;
        }
        return ans;
    }