Can I further optimize this solution for HackerRank's “Making Candies”?

Question

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

Answer 1

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.

Answer 2

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