PROBLEM LINK:
Author: Vitalii Kozhukhivskyi
Tester: Antoniuk Vasyl and Misha Chorniy
Editorialist: Pushkar Mishra
DIFFICULTY:
Medium
PREREQUISITES:
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:
Subtasks 1 and 2
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[0][i][0] = D, dp[0][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][0] = dp[t-1][i][0];
dp[t][i][1] = dp[t-1][i][1];
//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][0] = max(dp[t][i][0], dp[t-dis][i+dis][0]);
dp[t][i][1] = max(dp[t][i][1], dp[t-dis][i+dis][1]);
//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][0] = max(dp[t][i][0], dp[t-1][i][1]*buying[t-1][i]);
dp[t][i][1] = max(dp[t][i][1], dp[t-1][i][0]/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][0] = max(dp[t][i][0], dp[t-dis][i-dis][0]);
dp[t][i][1] = max(dp[t][i][1], dp[t-dis][i-dis][1]);
dp[t][i][0] = max(dp[t][i][0], dp[t-1][i][1]*buying[t-1][i]);
dp[t][i][1] = max(dp[t][i][1], dp[t-1][i][0]/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][0]
This algorithm runs in \mathcal{O}(MN^2). This is sufficient for the first two subtasks.
Subtask 3
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][0] = v_1 and dp[t][j][0] = v_2 such that v_1 > v_2. Now, when we are choosing the best possible value of dp[t+1][i][0], we needn’t check dp[t-2][i-2][0], i.e., dp[t][k][0] explicitly. This is because if dp[t][k][0] 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][0] 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][0] 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.
OPTIMAL COMPLEXITY:
\mathcal{O}(MN)
