CHINFL - Editorial

PROBLEM LINK:

Practice
Contest

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)

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

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

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.

Link to sol : https://www.codechef.com/viewsolution/9075309

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

Comments welcome!

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

Best Question :slight_smile:

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

2 Likes

Best Question :slight_smile:

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][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]);

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

Anybody solved this question using recursion with memoization?

Editorialist solution now available