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

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 but the overall complexity would be similar.

The game changer is a selection algorithm like Quickselect. In C++, nth_element is the implementation of quickselect.

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);
comments powered by Disqus