Luck Balance - Hacker Rank Solution

Lena is preparing for an important coding competition that is preceded by a number of sequential preliminary contests. She believes in "saving luck", and wants to check her theory. Each contest is described by two integers,  and :

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

If Lena loses no more than  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,  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 . Since she is allowed to lose  important contests, and there are only  important contests. She can lose all three contests to maximize her luck at . If , she has to win at least  of the important contests. She would choose to win the lowest value important contest worth . Her final luck will be .

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  contains two integers that represent the luck balance and importance of the  contest.

Input Format

The first line contains two space-separated integers  and , the number of preliminary contests and the maximum number of important contests Lena can lose.
Each of the next  lines contains two space-separated integers,  and , the contest's luck balance and its importance rating.

Constraints

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  contests. Of these contests,  are important and she cannot lose more than  of them. Lena maximizes her luck if she wins the  important contest (where ) and loses all of the other five contests for a total luck balance of .

Luck Balance - Hacker Rank Solution

There is no point in winning unimportant contests, so we can just lose all of them and get their luck.

Let's denote the number of important contests as . If , we can just lose all of them and add their luck to our luck balance. If , we want to win the  preliminary competitions having the smallest luck value. To do this, we sort all the luck values and subtract the first  values from our luck balance.

Problem Setter's code:

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;
}

Problem Tester's code:

Python 2

n, k = map(int, raw_input().split())

# I can definitely lose all of the unimportant contests
# and I have to lose exactly k important contests
res = 0
imp_contest = []

for i in range(n):
    a, b = map(int, raw_input().split())
    if b == 0:
        res += a
    else:
        imp_contest.append(a)
imp_contest.sort(reverse=True)

# Losing only k contests
res += sum(imp_contest[:min(k, len(imp_contest))])

# winning the remaining contests
res -= sum(imp_contest[k:])
print res