 # CHINFL - Editorial

Author: Vitalii Kozhukhivskyi
Tester: Antoniuk Vasyl and Misha Chorniy
Editorialist: Pushkar Mishra

Medium

DP

### PROBLEM:

There are N kiosks (numbered 0 to N-1) which exchange Peppercorns for Antarctican Dollars and vice versa at different rates. The rates vary per second. You have D Peppercorns in the beginning, and you have M seconds to perform exchanges. You need to maximise the Peppercoins you have after M seconds.

### EXPLANATION:

The question clearly hints towards a standard DP. For the given constraints, there exists no brute force solution. Thus, we directly move towards formulating a DP. Let us first define some arrays. Let buying[i][j] give the buying rate at the i^{th} second at kiosk number j. Similarly, let selling[i][j] give the selling rate at the i^{th} second at kiosk number j.

Now, we need to think of the states and overlapping subproblems for the DP. Let us have DP[time][kiosk][currency]. What does this denote? DP[t][i][c] denotes the maximum money that you can have in currency ‘cur’ if you are at kiosk i at the end of t seconds. How many possible values does each state have? t ranges from 1 to M, i goes from 1 to N and c can have 2 possible values. Let c = 0 denote Peppercorns currency and c = 1 denote Antarctic Dollar.

We now need to formulate the reccurence for this DP. Here we provide a pseudocode of the reccurence:

for i = 0 to N-1
{
//at time 0, chef can start at any kiosk with
//D Peppercorns and 0 Antarctic Dollars

dp[i] = D, dp[i];
}

for t = 1 to M
{
for i = 0 to N-1
{
//chef can simply wait at this kiosk for another second
dp[t][i] = dp[t-1][i];
dp[t][i] = dp[t-1][i];

//or approached this kiosk from some other kiosk
//at distance 'dis'
for dis = 1 to N-1
{
if(i+dis < N)
{
//chef can travel from the (i+dis) kiosk to this one.
//it takes time d.
dp[t][i] = max(dp[t][i], dp[t-dis][i+dis]);
dp[t][i] = max(dp[t][i], dp[t-dis][i+dis]);

//the other option chef has is to exchange currency
//at this particular kiosk. Since, exchanging takes
//1 second, we need to exchange the money we had 1
//second ago, i.e, time (t-1)

dp[t][i] = max(dp[t][i], dp[t-1][i]/selling[t-1][i]);
//recall the 1 = Antarctican Dollar, 0 = Peppercoins
}

//similarly for the analogous case of the kiosk (i-dis)
if(i-dis >= 0)
{
dp[t][i] = max(dp[t][i], dp[t-dis][i-dis]);
dp[t][i] = max(dp[t][i], dp[t-dis][i-dis]);

dp[t][i] = max(dp[t][i], dp[t-1][i]/selling[t-1][i]);
}
}
}
}

//return the maximum of Peppercorn currencies
//over all kiosks at time M. If this value is
//greater than 10^18, then output Quintillionnaire
return max of dp[M][0..N-1]


This algorithm runs in \mathcal{O}(MN^2). This is sufficient for the first two subtasks.

We need to somehow optimize the above algorithm. For that, we need to make a crucial observation. The innermost loop with variable dis goes from 1 to N-1. But a little bit of thinking tells us that dis only has to go from 1 to 1. In other words, we just need to check the immediate neighbours of a kiosk instead of checking all the kiosks. Why is that so?

Let us say there are three kiosks i, j, k such that j = i-1 and k = j-1. Let us say that at time t, dp[t][k] = v_1 and dp[t][j] = v_2 such that v_1 > v_2. Now, when we are choosing the best possible value of dp[t+1][i], we needn’t check dp[t-2][i-2], i.e., dp[t][k] explicitly. This is because if dp[t][k] contains a value larger than the neighbours of i, which by our assumption (v_1 > v_2) it does, then by the recurrence given in the pseudocode, dp[t][i-1] would contain at least that value or a bigger one. In other words, it is like saying that if a kiosk is at distance dis from i, we needn’t check the dp[t-dis][i-dis] cell since had that cell contained a big amount, chef would have walked with that amount from the (i-dis)^{th} kiosk to (i-1)^{th} kiosk in the meanwhile (i.e., in dis-1 time). Hence, we only need to check the neighbours of a kiosk because we are dealing with a DP which has maximisation in its recurrence.

This observation brings the complexity of the algorithm down to \mathcal{O}(MN) which is sufficient for all the subtasks.

The editorialist’s program follows the editorial. Please see for implementation details.

\mathcal{O}(MN)

### SAMPLE SOLUTIONS:

1 Like

I made a recusive solution without memoization. To my surprise it passed the first subtask.

Are there were no test file having value of n and m =100 in first subtask?
Can anyone tell how to make this solution work for 100 points? I didn’t use cache as there were 4 states in my recursion.

@ankurverma1994: you can check my solution here. I did not use recursive solution.

Here is a link to my commented AC solution. https://www.codechef.com/viewsolution/9152306

1 Like

Anybody solved this question using recursion with memoization?

Editorialist solution now available

I think this will be easier to understand:
let
A[i][j] be max amount of Antarctican Dollars you can have at ith kois at jth sec
P[i][j] be max amount of Peppercons you can have at ith kois at jth sec

Then ans will be max of P[i][m] where 1<=i<=n.

Now
A[i][t] = max( A[i][t-1], A[i-1][t-1], A[i+1][t-1], P[i][t-1]/rates[i][t-1].sell)
P[i][t] = max( P[i][t-1], P[i-1][t-1], P[i+1][t-1], A[i][t-1]*rates[i][t-1].buy)
i.e. max money you can have is maximum of money you had in prev sec at same or adjacent kois and money you can have by converting from second currency.

I learnt DP just the day before solving, and did it in first go. I did not use this algo, but made a cumulative DP Matrix, and it took just 3.3M. And the recursion is easy to understand as well:
https://www.codechef.com/viewsolution/9145917

I didn’t understand why one the neighbours have to be considered in the subtask 3?Please, help me.

Best Question here’s my Aced solution : https://www.codechef.com/viewsolution/9111009

2 Likes

Best Question here’s my Aced solution : https://www.codechef.com/viewsolution/9111009

2 Likes

Please someone explain why we are traversing from dis = 1 to n as maybe the time is not sufficient to jump from the i+dis to ith index ? If i am wrong please share your approach to solve the problem.

great problem and great editorial. Thanks.

great problem and great editorial. Thanks.

BTW no need to write this condition for buying/selling twice inside the third inner loop:

dp[t][i] = max(dp[t][i], dp[t-1][i]*buying[t-1][i]);
dp[t][i] = max(dp[t][i], dp[t-1][i]/selling[t-1][i]);


It can be written only once along with the condition where the chef simply waits at the kiosk for 1 second. See this.

//