Luck Balance

See the original problem on HackerRank.

Solutions

Simple observation: there is no point in winning unimportant contests so we can lose them all to get their luck.

If \(K\) is greater than the number of important contests, we can lose them all. In this case the luck balance is just the sum of all the contest values.

Otherwise, we have to win some important contests but we don’t have to lose more than \(K\). So the number of important contests to win is:

\(W = N_{important} - K\).

Since we need to maximize the luck, we’d better off winning the contests with the smallest luck value (because their luck will be subtracted from the total).

Thus, the problem boils down to finding \(W\) smallest luck values in an array.

A simple approach (that works) consists in sorting the important contests and then picking up the first \(W\) elements.

Here is a C++ solution implementing this idea:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int N, K, l, t; cin >> N >> K;
vector<int> im; im.reserve(N);
long luck = 0;
for (auto i=0; i<N; ++i)
{
    cin >> l >> t;
    if (t)
    {
        im.push_back(l);
    }
    luck += l;
}
if (K > im.size())
{
    cout << luck << endl;
}
else
{
    sort(begin(im), end(im));
    auto W = im.size()-K;
    auto lostLuck = accumulate(begin(im), begin(im) + W, 0);
    cout << (luck - 2*lostLuck);
}

Notes:

• we eagerly accumulate luck along the way by summing up all the luck values
• lostLuck must be doubled because we have previously added its contribution to luck

In addition to this, consider that the solution schema hides some interesting patterns we can express, for example, in C# with LINQ:

1
2
3
4
5
6
7
8

var loss = contests
            .Where(x => x[1] == 1)
            .OrderByDescending(x => x[0])
            .Skip(k)
            .Sum(x => x[0]);

var totalLuck = contests.Sum(x => x[0]);
Console.WriteLine(totalLuck - (loss * 2));

1
2
3
4
5
6
7

solve :: (Int, [(Int, Int)]) -> Int
solve (k, zs) = totalLuck - (loss * 2)
  where
    important = fst <$> filter (\(_, t) -> t == 1) zs
    sortedImportant = sortBy (flip compare) important
    totalLuck = sum $ fst <$> zs
    loss = sum (drop k sortedImportant)

This problem open doors to investigating better and more generic ways to finding the first \(n\) smallest/biggest values of a sequence.

Actually, not only sorting the sequence is more expensive but also unnecessary. Indeed, the actual order of the first \(W\) elements is not important for our problem because addition is a commutative operation.

Another option is using a partial sort algorithm, however the overall complexity would be similar.

The game changer is a selection algorithm like Quickselect that can solve this problem in linear time. The C++ standard library provides nth_element that typically implements introselect or other selection algorithms with suitable average-case complexity (linear).

Here is the affected code fragment:

1
2
3
4

auto W = im.size()-K;
nth_element(begin(im), begin(im) + W, end(im));
auto lostLuck = accumulate(begin(im), begin(im) + W, 0);
cout << (luck - 2*lostLuck);