Hackerrank Luck Balance solution in C++

Question

I solved the Hackerrank Luck Balance problem the "C" way (I am much more used to C) and I wanted to know if there were any C++ features I could have used that would have made my code more concise/neater. That's it! Any other criticism is welcome, of course.

All the stuff that I wrote is in the LuckBalance() function. Pay no attention to anything else - that was provided by the challenge (which wasn't really a challenge)

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, \$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.

Note that the k parameter in the luckBalance function is the maximum number of important contests Lena can lose, and the vector<vector<int>> contests input is a column vector of \$L[i]\$ along with a column vector of \$T[i]\$.

#include <bits/stdc++.h>
#include <stdlib.h>

using namespace std;

vector<string> split_string(string);

// Complete the luckBalance function below.
int luckBalance(int k, vector<vector<int>> contests) {

    int totalLostLuck = 0;
    int totalGainedLuck = 0;
    int totalRegainedLuck = 0;
    vector<int> regainedLuck(k, 0);

    for(int i = 0; i < contests.size(); i++)
    {
        if(contests[i][1] == 1)
        {
            totalLostLuck += contests[i][0];
            for(int j = 0; j < k; j++)
            {
                // Choose to win the contests that have the greatest
                // amount of luck
                if(regainedLuck[j] < contests[i][0])
                {
                    regainedLuck[j] = contests[i][0];
                    sort(regainedLuck.begin(), regainedLuck.end());
                    j = k;
                }
            }
        }
        // If it is a non-important contest, we get the luck for free!
        else
        {
            totalGainedLuck += contests[i][0];
        }
    }

    for(int i = 0; i < k; i++)
    {
        totalRegainedLuck += regainedLuck[i];
    }

    return totalGainedLuck - totalLostLuck + (2*totalRegainedLuck);
}

int main()
{
    //ofstream fout(getenv("OUTPUT_PATH"));

    string nk_temp;
    getline(cin, nk_temp);

    vector<string> nk = split_string(nk_temp);

    int n = stoi(nk[0]);

    int k = stoi(nk[1]);

    vector<vector<int>> contests(n);
    for (int i = 0; i < n; i++) {
        contests[i].resize(2);

        for (int j = 0; j < 2; j++) {
            cin >> contests[i][j];
        }

        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }

    int result = luckBalance(k, contests);

    cout << result << "\n";

    //fout.close();

    return 0;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}

Answer 1

The algorithm should be:

1. Lose any unimportant contest where doing so does not lose luck.
2. Win any contest where doing so does not lose luck.
3. Lose the up to k contests where winning would cost most luck.

At the moment, you assume winning never gains luck and losing never loses luck.

You do a full sort each iteration for point 3, which with a cost of \$O(k*\log(k))\$ leads to \$O(n*k*\log(k))\$.
Using a fixed-length priority-queue instead only needs \$O(\log(k))\$ per insert / replace, resulting in \$O(n*\log(k))\$, a factor of \$k\$ better.
While C++ doesn't have exactly that, <algorithm> provides pop_heap() and push_heap() which is enough to replace the head if the new item is less expensive. A custom replace_heap() or exposed down_heap() would be slightly more efficient, but for that you have to branch out.

Now the form:

1. <bits/stdc++.h> is non-standard and likely far more than you actually need. Unless coupled with use of precompiled headers, it will slow down compilation at least, if not bloat the resulting executable. Replace it with the standard includes. See "How does #include <bits/stdc++.h> work in C++?".

2. Never import wholesale any namespace which isn't designed for it. Doing so leads to conflicts, silent changes of behaviour, and generally brittle code. See "Why is “using namespace std” considered bad practice?".

3. Don't use a std::vector if all you need is an array of statically-known length.
   Such overkill costs. Anyway, a std::tuple<int, bool> or std::pair<int, bool> would be an even better fit.

4. If one can rely on anything, it's that if there is a way to screw something up, it will be done, at the most inconvenient time. Like the input. As it is under the coders control, it isn't quite a fatal defect though.

5. return 0; is implicit for main().

6. Small trivial types like char should not be passed by constant reference without good reason, but by value. Doing so avoids the pitfalls of aliasing, and is slightly more efficient. Happily, the compiler should fix that by inlining.

7. Getting and storing input in the loop-condition is actually idiomatic. And it avoids error-prone repetition.
   This:

   size_t i = 0;
   size_t pos = input_string.find(delimiter);
   
   while (pos != string::npos) {
       splits.push_back(input_string.substr(i, pos - i));
   
       i = pos + 1;
       pos = input_string.find(delimiter, i);
   }
   

   Could simply be:

   for (size_t i = 0, pos; (pos = input_string.find(delimiter, i)) != string::npos; i = pos + 1)
       splits.push_back(input_string.substr(i, pos - i));
   

8. The final call to .substr() needlessly contains a complicated calculation for the second argument. Just leaving it out will do the right thing.

   splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));
   

9. As an aside, split_string() would be better off accepting a std::string_view and returning a std::vector<std::string_view>. Less allocation-overhead.

10. There is no reason to pass the contests by copy. Either move them, pass a constant reference, or preferably use a std::span (C++20 or GSL (Guideline Support Library)).

11. Yes, there's no need to forward-declare functions defined before first use, which is a good thing. But above all, please try to be consistent which option you use.

Finally your code:

1. There's no reason at all to keep track of parts of the result-sum separately. Just combine them already.

2. Using auto instead of explicit types avoids errors and reduces clutter. Thus, almost always auto. That also counts for the form.

The rest was handled in the algorithm section.

Using the better algorithm:

int luckBalance(int k, vector<vector<int>> contests) {
    // Keeping the bad interface because they force it
    auto r = 0;
    const auto heap = std::make_unique<int[]>(k);
    for (const auto& x : contests) {
        if (!x[1] || x[0] <= heap[0]) {
            r += std::abs(x[0]);
        } else {
            std::pop_heap(heap.get(), heap.get() + k, std::greater());
            r -= heap[k - 1];
            heap[k - 1] = x[0];
            std::push_heap(heap.get(), heap.get() + k, std::greater());
        }
    }
    return r;
}

Could be improved by not pre-filling the heap with zeroes, but I'm too lazy.

Answer 2

Prefer standard headers

<bits/stdc++.h> isn't in any standard; even on those platforms where it exists, it's probably a poor choice if it includes the whole of the Standard Library. Instead, include (only) the standard library headers that declare the types that are required for the header.

Avoid using namespace std;

Bringing all names in from a namespace is problematic; namespace std particularly so. See Why is “using namespace std” considered bad practice?.

Prefer C++ standard headers

Instead of <stdlib.h>, it's better to include <cstdlib>, so that standard library names are consistently declared in the std namespace, away from your own identifiers (though, at a first glance, I don't see where you need this particular header).

---

Now to the implementation of luckBalance(). One thing we can observe here is that we only ever use i to iterate through the elements of contests; that's a good indication that we can use a range-based for loop. Since we only read from contests[i] (and never write), we can use a const reference (and should have accepted a reference to const vector as function argument):

for (const auto& contest: contests) {
    if (contest[1] == 1) {
        totalLostLuck += contest[0];

---

(This is a partial review; I intend to return and complete it later).