Making Candies - Hacker Rank Solution

Karl loves playing games on social networking sites. His current favorite is CandyMaker, where the goal is to make candies.

Karl just started a level in which he must accumulate  candies starting with  machines and  workers. In a single pass, he can make  candies. After each pass, he can decide whether to spend some of his candies to buy more machines or hire more workers.
Buying a machine or hiring a worker costs  units, and there is no limit to the number of machines he can own or workers he can employ.

Karl wants to minimize the number of passes to obtain the required number of candies at the end of a day. Determine that number of passes.

For example, Karl starts with  machine and  workers. The cost to purchase or hire,  and he needs to accumulate  candies. He executes the following strategy:

1. Make  candies. Purchase two machines.
2. Make  candies. Purchase  machines and hire  workers.
3. Make  candies. Retain all  candies.
4. Make  candies. With yesterday's production, Karl has  candies.

It took  passes to make enough candies.

Function Description

Complete the minimumPasses function in the editor below. The function must return a long integer representing the minimum number of passes required.

minimumPasses has the following parameter(s):

• m: long integer, the starting number of machines
• w: long integer, the starting number of workers
• p: long integer, the cost of a new hire or a new machine
• n: long integer, the number of candies to produce

Input Format

A single line consisting of four space-separated integers describing the values of , , , and , the starting number of machines and workers, the cost of a new machine or a new hire, and the the number of candies Karl must accumulate to complete the level.

Constraints

Output Format

Return a long integer denoting the minimum number of passes required to accumulate at least  candies.

Sample Input

3 1 2 12

Sample Output

3

Explanation

Karl makes three passes:

1. In the first pass, he makes  candies. He then spends  of them hiring another worker, so and he has one candy left over.
2. In the second pass, he makes  candies. He spends  of them on another machine and another worker, so  and  and he has  candies left over.
3. In the third pass, Karl makes  candies. Because this satisfies his goal of making at least  candies, we print the number of passes (i.e., ) as our answer.

Making Candies - Hacker Rank Solution

This problem can be solved by using a binary search. Basically we binary search on the answer (number of passes) and checking if the current round number is enough to make the required number of candies. If we can do so, we try to minimize our answer by decreasing the number of passes else we increase the number of passes.

Two important observations to make when solving this problem are:

1. Always buy machines and hire workers as early as possible.
   If we do so, then the subsequent operations will lead to a larger product everytime and hence more candies.
2. To maximize the number of candies made during each round, the numbers of workers and machines should be either equal or as close to each other as possible. Hence, we must always invest in whichever resource we have less of.
   This is because let's say the current number of workers and machines are  and  respectively. And we decide to spend a number of candies for the current operation to increase  and  in some ratio. Obviously, our aim is to maximize the product , where  and  are the new  and  after the increment respectively. We know that their sum is . Let's denote this sum by . So we have,  and we need to maximise , which is maximum when . Hence,  and  should be as close as possible.

We write a check function having the following parameters:  and . This function returns a boolean value denoting whether or not it's possible to produce the required number of candies, , in less than or equal to  number of passes if we currently have  machines and  workers where each new machine or worker costs  candies.

If we can make candies with the current resources in the remaining number of passes, then the function returns true; otherwise, we must try to make candies and buy new resources (i.e., if there are more machines than workers, hire more workers or if both are equal increase both of them in equal proportion). Compare the remaining number of passes with the number of passes needed to make candies for buying additional resources and, if the remaining number is less, return false.

Problem Setter's code:

C++

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

bool check(ll machines, ll workers, ll price, ll target, ll rounds) {
    if (machines >= (target+workers-1)/workers) return true;
    ll cur = machines*workers;
    rounds--;
    if (rounds == 0) return false;
    while (1) {
        ll rem = target - cur;
        ll rnds = (rem + machines*workers - 1) / (machines*workers);
        if (rnds <= rounds) return true;
        if (cur < price) {
          rem = price - cur;
          rnds = (rem + machines*workers - 1) / (machines*workers);
          rounds -= rnds;
          if (rounds < 1) return false;
          cur += rnds * machines * workers;
        }
        cur -= price;
        if (machines > workers) {
          workers++;
        } else {
          machines++;
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll m, w, p, n;
    cin >> m >> w >> p >> n;
    ll a = 1, b = 1000000000000LL;
    while (a < b) {
        ll mid = (a + b) >> 1;
        if (check(m, w, p, n, mid)) {
          b = mid;
        } else {
          a = mid + 1;
        }
    }
    cout << a << "\n";
    return 0;
}