Luck Balance Hackerrank Solution – Greedy Problem

Luck Balance Hackerrank Solution – Greedy Problem

3 min read

Lena is preparing for an important coding competition that is preceded by a number of sequential preliminary contests. Initially, her luck balance is 0. She believes in “saving luck”, and wants to check her theory. Each contest is described by two integers, L[i]  and T[i]:

  •  L[i] is the amount of luck associated with a contest. If Lena wins the contest, her luck balance will decrease by L[i]; if she loses it, her luck balance will increase by L[i].
  •  T[i] denotes the contest’s importance rating. It’s equal to 1 if the contest is important, and it’s equal to 0 if it’s unimportant.

If Lena loses no more than k important contests, what is the maximum amount of luck she can have after competing in all the preliminary contests? This value may be negative.

For example, k = 2 and:

Contest L[i] T[i]
1 5 1
2 1 1
3 4 0

If Lena loses all of the contests, her will be 5 + 1 + 4 = 10 . Since she is allowed to lose 2 important contests, and there are only 2 important contests. She can lose all three contests to maximize her luck at 10. If k = 1, she has to win at least 1 of the 2 important contests. She would choose to win the lowest value important contest worth 1. Her final luck will be 5 + 4 – 1 = 8 .

Function Description

Complete the luckBalance function in the editor below. It should return an integer that represents the maximum luck balance achievable.

luckBalance has the following parameter(s):

  • k: the number of important contests Lena can lose
  • contests: a 2D array of integers where each contests[i]  contains two integers that represent the luck balance and importance of the ith contest.

Input Format

The first line contains two space-separated integers n and k, the number of preliminary contests and the maximum number of important contests Lena can lose.
Each of the next n lines contains two space-separated integers, L[i] and T[i], the contest’s luck balance and its importance rating.

Constraints

  • 1<= n <= 100
  • 0<=k <=N
  • 1 <= L[i] <= 10000
  • T[i] E {0,1}

Output Format

Print a single integer denoting the maximum amount of luck Lena can have after all the contests.

Sample Input

6 3
5 1
2 1
1 1
8 1
10 0
5 0

Sample Output

29

Explanation

There are n = 6 contests. Of these contests, 4 are important and she cannot lose more than k = 3 of them. Lena maximizes her luck if she wins the 3rd important contest (where L[i] = 1) and loses all of the other five contests for a total luck balance of 5 + 2 + 8 + 10 + 5 -1 = 29.

Solution in Python 3

#!/bin/python3

import math
import os
import random
import re
import sys

# Complete the luckBalance function below.
def luckBalance(k, contests):
    imp_const = []
    luck = 0
    
    for i in contests:
        if i[1] == 1:
            imp_const.append(i[0])
        else:
            luck += i[0]
            
    imp_const.sort(reverse=True)

    luck += sum(imp_const[:min(k, len(imp_const))])

    # winning the remaining contests
    luck -= sum(imp_const[k:])
    
    
    return luck

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nk = input().split()

    n = int(nk[0])

    k = int(nk[1])

    contests = []

    for _ in range(n):
        contests.append(list(map(int, input().rstrip().split())))

    result = luckBalance(k, contests)

    fptr.write(str(result) + '\n')

    fptr.close()

Solution in C++

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int ans = 0;
    assert(1 <= n && n <= 100);
    assert(0 <= k && k <= n);
    vector<int> a;
    for (int i = 0; i < n; i++) {
        int x, tp;
        cin >> x >> tp;
        assert(1 <= x && x <= 100000);
        assert(0 <= tp && tp <= 1);
        if (tp == 0) {
            ans += x;
        }
        else {
            a.push_back(x);
        }
    }
    sort(a.begin(), a.end() );
    reverse(a.begin(), a.end() );
    for (int i = 0; i < min((int)a.size(), k); i++) {
        ans += a[i];
    }
    for (int i = k; i < a.size(); i++) {
        ans -= a[i];
    }
    cout << ans << endl;
    return 0;
}
Choose your Reaction!
Leave a Comment