2
\$\begingroup\$

My C++ solution for HackerRank's "Making Candies" problem, reproduced below, is as optimized as I can make it and appears similar to what others say are optimal solutions. However, six of the test cases still fail due to timing out. I would be interested to know if there are any significant opportunities to optimize my code that I missed.

I'm guessing that I'm either missing some way to simplify the computation (perhaps part of it can be precomputed and stored in a lookup table?), or there's some way to compute the answer without using a loop.

std::ios::sync_with_stdio(false);

long m, w, p, n;

std::cin >> m >> w >> p >> n;

for (long candies = 0, passes = 0, total = LONG_MAX; ; ++passes) {
    const auto production = __int128{m} * w;

    const long goal = n - candies;

    const long passes_needed = goal/production + !!(goal%production);

    const long subtotal = passes + passes_needed;

    if (passes_needed <= 2) {
        std::cout << subtotal;
        return 0;
    }

    if (total < subtotal) {
        std::cout << total;
        return 0;
    }

    total = subtotal;

    candies += production;

    if (candies >= p) {
        const auto d = std::div(candies, p);

        long budget = d.quot; candies = d.rem;

        const long diff = w - m;

        if (diff < 0) {
            const long w_hired = std::min(budget, -diff);

            budget -= w_hired;
            w += w_hired;
        } else if (diff > 0) {
            const long m_purchased = std::min(budget, diff);

            budget -= m_purchased;
            m += m_purchased;
        }

        const long half = budget >> 1;

        m += half + (budget & 1);
        w += half;
    }
}
\$\endgroup\$
4
  • 3
    \$\begingroup\$ Links can rot over time. Please improve the question by including a synopsis of the problem your code is solving. \$\endgroup\$
    – Edward
    Mar 26, 2021 at 18:15
  • \$\begingroup\$ Have you looked at how your algorithm behaves on the 6 tests that fail? Offhand, there's some smell where you used the __int128 compiler intrinsic to do a multiplication, but then added the result to a long. What actually happens when your algorithm fails on those 6 test?s \$\endgroup\$
    – Cort Ammon
    Mar 26, 2021 at 22:56
  • \$\begingroup\$ Also, you may find your life is easier if you write either an Algorithm Description Document, or comment the reasons why you are doing the operations you are doing. That will help isolate algorithmic issues from coding errors. \$\endgroup\$
    – Cort Ammon
    Mar 26, 2021 at 22:57
  • \$\begingroup\$ @CortAmmon It gets the correct answer, it just takes too long. There's no issue with adding production to candies, because if production is too large to fit in a long then it must be the case that passes_needed <= 2. \$\endgroup\$
    – Ray Hamel
    Mar 26, 2021 at 23:58

2 Answers 2

1
\$\begingroup\$

Unlearn bad behavior taught by competitive coding sites

Competitive coding sites unfortunately teach some bad coding habits. You did not include your whole program, the #includes are missing for example. If you did #include <bits/stdc++.h>, don't.

The call to std::ios::sync_with_stdio() is only useful if your program is I/O bound, and it won't make a difference if you are just writing the final result to std::cout.

Use of integer types

__int128 is not a standard C++ type, and I don't think it is necessary at all to use it. The problem states that n is limited to \$10^{12}\$, so you only need 64-bit variables and some care to avoid values wrapping around.

A long is only guaranteed to be at least 32-bits in size. So reading in the initial values is already broken since they might be larger than that. Also, none of the values should ever become negative, so the appropriate type to use here is std::uint64_t.

Speeding up the algorithm

Yes, you can optimize your solution further. Consider the case where the desired number of candies n = 1000000000000, the cost is so high you can never buy/hire (p = n), and you start with m = 1 and w = 1. Then your loop will just do n iterations, adding 1 to candies each time.

What you should do is calculate how many iterations it would take to get enough money to buy/hire something new, and then advance that many iterations in one step. So:

const auto passes_needed_to_buy = candies < p ? (p - candies) / production : 0;

Of course, if this value is more than passes_needed, then you know you will never be able to buy anything before you produced enough candy.

\$\endgroup\$
5
  • \$\begingroup\$ 1) I included algorithm, climits, cmath and iostream. I did not include bits/stdc++.h. The sync_with_stdio(false) is in there to make clear that the test cases aren't failing due to the program being I/O-bound. 2) The use of __int128 is because m and w can be up to 10^12 (≈2^40), and the result of the multiplication indeed overflows an (unsigned) 64-bit integer in several of the test cases. I used long because that's what the question said to use; I'm aware it's not portable (to Windows). 3) Good idea, but it doesn't speed it up enough to pass the failing test cases. \$\endgroup\$
    – Ray Hamel
    Mar 27, 2021 at 18:33
  • \$\begingroup\$ Ah, the question tells you that the values are passed as long parameters to a function named minimumPasses(), but you are reading them from std::cin. So you are already not following the instructions to the letter. About m and w: please follow the link where the answer shows you to detect if the multiplication overflowed. If it did, you know you have more production than you ever need. So there is no need to store anything in a __int128. What are the test cases that are failing exactly? \$\endgroup\$
    – G. Sliepen
    Mar 27, 2021 at 18:42
  • \$\begingroup\$ The values are read from cin because that's how the test cases are set up. I did follow the link and it looks like about 20 lines of code to detect overflow, which is clearly less optimal than just doing a 128-bit multiplication. I'm not asking how to make this code more portable, I'm asking how it can be optimized. Test cases 4, 7, 9, 14, 16 and 19 are failing due to timeout. \$\endgroup\$
    – Ray Hamel
    Mar 27, 2021 at 19:00
  • \$\begingroup\$ Please read the answers in the question about overflow handling again. The top one mentions this one-liner: if (a != 0 && x / a != b) { // overflow handling }. As for the failing test cases: please provide us with the actual values for m, w, p and n. And while you might not care about portability, other people will read your question as well and have different priorities, so in our answers will point out all the issues we find. \$\endgroup\$
    – G. Sliepen
    Mar 27, 2021 at 23:42
  • \$\begingroup\$ So I tried using that method of detecting overflow, but it caused several test cases to fail. I think there must be some edge cases it doesn't catch, or else the fact that signed integer overflow is UB is screwing things up. So I'm going to stick with using 128-bit ints for now, although I may try your method with unsigned ints later. I did however manage after some trial and error to get the failing test cases working (see my answer above), with some help from your optimization suggestion. And you are right, portability is important. Apologies if I came across as aggressive. \$\endgroup\$
    – Ray Hamel
    Mar 29, 2021 at 23:55
0
\$\begingroup\$

I figured out how to get the failing test cases passing, with a little help from G. Sliepen's answer. It turns out I needed to calculate the number of passes needed to buy another machine or worker, and return early, as G. Sliepen suggested, if that number equaled or exceeded the number of passes needed to complete the order without any purchases.

But, in addition to returning early, I also could leverage that calculation to advance the algorithm forward to the point where we buy something. This addition is what ultimately allowed the program to pass all the test cases.

The relevant snippet:

const std::int64_t passes_needed_to_buy =
    candies < p ? (p - candies) / production : 0;

if (passes_needed_to_buy >= passes_needed - 1) {
    // We won't buy anything, so return early
    std::cout << total;
    return 0;
}
// Skip forward to when we buy something
passes += passes_needed_to_buy;
candies += production * passes_needed_to_buy;

The full program:

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdint>
#include <iostream>

#ifdef __SIZEOF_INT128__

using Int128 = __int128;

#else

#include <boost/multiprecision/cpp_int.hpp>

using Int128 = boost::multiprecision::int128_t;

#endif

int main() {
    std::ios::sync_with_stdio(false);

    std::int64_t m, w, p, n;

    std::cin >> m >> w >> p >> n;

    assert(m > 0 && m <= 1'000'000'000'000);
    assert(w > 0 && w <= 1'000'000'000'000);
    assert(p > 0 && p <= 1'000'000'000'000);
    assert(n > 0 && n <= 1'000'000'000'000);

    for (std::int64_t candies = 0, passes = 0, total = INT64_MAX; ; ++passes) {
        const auto production = Int128{m} * w;

        const auto goal = n - candies;

        const std::int64_t passes_needed =
            goal/production + !!(goal%production);

        const auto subtotal = passes + passes_needed;

        if (passes_needed <= 2) {
            std::cout << subtotal;
            return 0;
        }

        if (total < subtotal) {
            std::cout << total;
            return 0;
        }

        total = subtotal;

        candies += production;

        const std::int64_t passes_needed_to_buy =
            candies < p ? (p - candies) / production : 0;

        if (passes_needed_to_buy >= passes_needed - 1) {
            std::cout << total;
            return 0;
        }

        passes += passes_needed_to_buy;
        candies += production * passes_needed_to_buy;

        const auto d = std::div(candies, p);

        auto budget = d.quot; candies = d.rem;

        const auto diff = w - m;

        if (diff < 0) {
            const auto w_hired = std::min(budget, -diff);

            budget -= w_hired;
            w += w_hired;
        } else if (diff > 0) {
            const auto m_purchased = std::min(budget, diff);

            budget -= m_purchased;
            m += m_purchased;
        }

        const auto half = budget >> 1;

        m += half + (budget & 1);
        w += half;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.