Solution: Google Kickstart Round H 2022 | Problem B: Magical Well Of Lilies

Problem Statement

There is a deep magical well in a forest that has some lilies on its waters. You have a large empty basket and some coins, and are standing next to the well. You have more coins than there are lilies in the well. The well has taken note of the fact that your basket is empty.

If you toss one coin into the well, the well will toss out one lily into your basket. If you toss four coins at once into the well, the well will take note of how many lilies it has tossed out into your basket so far. If you toss two coins at once into the well, the well will toss out as many lilies into your basket as it had last taken note of. If you toss one coin, or two coins at once, into the well, and there are not enough lilies left in the well, the well will not toss out any lilies.

Given the number of lilies L in the well at the beginning, return the minimum number of coins you will need to toss into the well to make it toss all of its lilies into your basket.

Constraints

1 ≤ L ≤ 100000

Samples

Explanation

For test case 1, when there are 5 lilies in the well, the least number of coins needed is

5. We toss them, one at a time, into the well, and the well tosses out the 5 lilies, one at a time, into our basket. No other sequence of moves results in a better solution, so 5 is our answer.

Solution

Let’s narrow down the language of the question in simple terms , So in the question we have been given a start state ( 0 ) and a goal state ( L ) , and we have to reach the goal state after performing some sets of operations Using minimum coins.

The operations are

1. Use 1 coin and jump to the next state i.e. i → i + 1.
2. Use 4 coins and take a checkpoint note of the current Lilies.
3. Use 2 coins and take a jump of x where x is the last registered checkpoint.

So our first intuition is to use the Brute Force way approach , which is recursion and we will try all possible ways and then minimise our answer.

But since L is too large , the above approach will lead to TLE.

Let’s try to think of dp. How can we introduce Dynamic programming in it?

We can see that if we have to reach the i + 1 th state from i th state then simply we can take the min( i+1 th state , 1 + i th state)

Let’s declare 1-D DP of size L+2. and initialize dp[i]=i. As we can use 1 coin to reach from previous state to current state hence i th state will take i coins.

Now , we will see each of the three steps described above.

1. We are at i th state , Now we will use 1 coin to go on i+1th state . Hence the transition will look like dp[ i + 1 ] = dp[ i ] + 1, But since there can be already a value assign to dp[ i + 1] we will take minimum of both i.e. dp[ i + 1 ] = min( dp[ i ] + 1 , dp[ i + 1 ] ).
2. We will Use 4 coins to Record the current state . Let’s use a variable cur , Hence the statement will look like cur = dp[ i ] + 4.
3. Now we will Try and Update all the multiples of i th state with the Using 2 coins at each update. ( As we are adding the last noted lilies Hence we must only consider the multiples of the current state). So for this we will use a for loop traversing i+i to L.

Code

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

int main()
{
int t;
cin >> t;
while(t — )
{
int l;
cin >> l;
vector<int> dp(l + 2);
for (int i = 0; i <= l;i++)
{
dp[i] = i;
}
for (int i = 2; i <= l;i++)
{
dp[i + 1] = min(dp[i] + 1, dp[i + 1]);
int cur = dp[i] + 4;
for (int j = i + i; j <= l; j += i)
{
cur += 2;
dp[j] = min(dp[j], cur);
}
}
cout << dp[l] << endl;
}
}

Time Complexity

For the time complexity , the outer loop is running for O(L) times , and for each index i from 2 to L . There are L/i multiples. So TC will be calculated like

O ( L/2 + L/3 + L/4 + L/5 + ……….. + L/L )

O ( L ( ½ + ⅓ + ¼ + ⅕ + ……….+ 1/L )

O(L log L )

As the ½ + ⅓ + ¼ + ⅕ + ….+ 1/L is a Harmonic Series And solution to this series is log L.

Space Complexity

Since we are using a 1-D Dp array , SC will be O(L).

You can also watch this solution LIVE on our YouTube channel now: https://youtu.be/pQvyU2mt7KI

Start your journey with Programming Pathshala.

Logon to www.programmingpathshala.com and take a free trial TODAY!