ZIO06004 - Editorial

editorial
, , , , ,
1

Editorialist: Anubhav Dhar

Problem Statement: ZIO 2006 Problem 4

Quick Explanation:

  • We can use a dynamic programming approach to solve this problem.
  • Let dp[i][j] be the minimum amount spent in Rupees, such that Mona has exactly j Martian Dollars at the “end” of the i-th day.
  • If we denote the amount in Martian Dollars that Mona needs everyday by Exp, the upper limit on the amount of Martian Dollars Mona might keep at a time by Lim, and the exchange rate on the i-th day by C[i] then we have
    • dp[1][j] = C[1].(j+Exp) [since we withdraw “before” spending in a day, and we have j Martian Dollars at the “end” of the day].
    • For i > 1, we have : dp[i][j] = \max\limits_k\{dp[i-1][k] + (j - k + Exp)*C[i] \}, where (j+Exp) ≤ Lim [since j is the amount of Martian Dollars Mona has at the “end” of the i-th day, and on the same day, Mona spent Exp amount of Martian Dollars, so at the “beginning” of the day, Mona must be having (j + Exp) Martian Dollars, which must have been less than or equal to the upper limit, Lim.
  • So the final answer that we should report is dp[Number\_of\_days][0].
  • There are also a couple of greedy solutions which work for this problem. These are explained at the end.

Explanation:

This problem can be solved using a dynamic programming approach, although being familiar with dynamic programming beforehand is not essential.

Let dp[i][j] be the minimum amount spent in Rupees, such that Mona has exactly j Martian Dollars at the “end” of the i-th day.

Further we denote the amount in Martian Dollars that Mona needs everyday by Exp, and the upper limit on the amount of Martian Dollars that Mona might keep at a time by Lim. Let the exchange rate on the i-th day be C[i]. So for dp[i][j], we know that 1 ≤ i ≤ Number\_of\_days and 0 ≤ j ≤ (Lim - Exp) [since at the beginning of the i-th day, Mona had j + Exp amount of Martian Dollars, and only after using Exp amount throughout the day she had amount j, so j + Exp must have been within the upper limit, that is Lim].

Now, we will attempt to calculate dp[1][j], 0 ≤ j ≤ (Lim - Exp). We observe that, to end up with j Martian Dollars at the “end” of the “first” day, Mona had to withdraw (j + Exp) Martian Dollars on the beginning of that day. So the amount, in Rupees deducted for the same must be the amount in Martian Dollars, times the exchange rate for day 1, i.e. (j + Exp).C[1] Rupees. So we simply get dp[1][j] = (j + Exp).C[1] .

Now for i > 1, to calculate dp[i][j], 0 ≤ j ≤ (Lim - Exp), we must keep in mind that at the “end” of the (i-1)-th day, Mona might have some amount of money left (possibly 0). Let’s say that at the “end” of the (i-1)-th day, Mona had k Martian Dollars left with her, 0 ≤ k ≤ (Lim - Exp). Also we know that on the i-th day, Mona spent Exp Martian Dollars and at the “end” of that day, she had j Martian Dollars left (we are only considering the case corresponding to dp[i][j]). So, if the amount that she withdrew on the i-th day be w Martian Dollars, then we get: w + k - Exp = j, or w = (j + Exp- k). Now, as w cannot be negative we must have w \ge 0, i.e. j + Exp - k \ge 0, i.e. k \le (j + Exp); and as we already know 0 ≤ k ≤ (Lim - Exp), we now have 0 ≤ k ≤ min((j + Exp),(Lim - Exp)). So the amount of money in Rupees deducted on the i-th day has to be C[i].w = C[i].(j + Exp - k). As, at the “end” of the (i-1)-th day, Mona had k Martian Dollars, so the minimum amount in Rupees deducted till day (i-1), is dp[i-1][k]. Summing things up, we get: dp[i][j] = dp[i-1][k] + (j + Exp - k). C[i], for a particular value of k. Now since k can be any integer in the interval [0,min(Lim - Exp, j + Exp)] and we are only interested in the minimum of those, we take the minimum of dp[i-1][k] + (j + Exp - k). C[i], over all k, 0 ≤ k ≤ min((j + Exp),(Lim - Exp)). So we get-

dp[i][j] = \min \limits_{0 ≤ k ≤ min((j + Exp),(Lim - Exp))}\{dp[i-1][k] + (j + Exp - k).C[i] \}

Now, we just need to calculate the values.

Subtask (a):

We are given the following values-

Number\_of\_days = 10

Exp = 1

Lim = 4

day(i) 1 2 3 4 5 6 7 8 9 10
C[i] 6 6 7 7 7 5 4 6 5 7

So if we define dp[i][j] as we did earlier, we must have 1 ≤ i ≤ 10 and 0 ≤ j ≤ 3 in this case.

Now, we maintain a table containing dp[i][j], for 1 ≤ i ≤ 10 and 0 ≤ j ≤ 3. For dp[1][j], as discussed before we just compute (j + Exp).C[1] = 6.(j+1). Setting these up, we get,

j \ i 1 2 3 4 5 6 7 8 9 10
0 6
1 12
2 18
3 24

Now we will fill the second column in the table, i.e. i = 2. For a particular j, we consider all k, 0 ≤ k ≤ min ((j+1),3), and take the minimum of dp[1][k] + (j + Exp - k).C[2] = dp[1][k] + 6(j + 1 - k). For example, considering j = 2, k can be 0, 1, 2 or 3. So we will take minimum of

dp[1][0] + 6(3 - 0) = 24

dp[1][1] + 6(3 - 1) = 24

dp[1][2] + 6(3 - 2) = 24

dp[1][3] + 6(3 - 3) = 24.

The minimum of these values is 24, so we set dp[2][2] = 24 (Note that it just happens to be the case that for all k, we get the same value. It might not be this way every time). Filling other cells of the second column similarly, we get-

j \ i 1 2 3 4 5 6 7 8 9 10
0 6 12
1 12 18
2 18 24
3 24 30

Now,to fill up the third column, we just do the same thing. For a particular value of j, we consider all k, 0 ≤ k ≤ (j+1,3), and take the minimum of dp[2][k] + (j + Exp - k).C[3] = dp[2][k] + 7(j + 1 - k). For example, considering j = 2, k can be 0, 1, 2 or 3. So we will take minimum of

dp[2][0] + 7(3 - 0) = 33

dp[2][1] + 7(3 - 1) = 32

dp[2][2] + 7(3 - 2) = 31

dp[2][3] + 7(3 - 3) = 30.

The minimum of these values is 30, so we set dp[3][2] = 30. Filling other cells of the third column similarly, we get-

j \ i 1 2 3 4 5 6 7 8 9 10
0 6 12 18
1 12 18 24
2 18 24 30
3 24 30 37

Now, we fill other columns in the same manner. The final table will look like

j \ i 1 2 3 4 5 6 7 8 9 10
0 6 12 18 24 30 35 39 43 47 51
1 12 18 24 30 37 40 43 47 51 56
2 18 24 30 37 44 45 47 51 56 61
3 24 30 37 44 51 50 51 57 61 68

Now, with the values filled, we should just report dp[10][0] (Ideally we should be reporting \min\limits_{0 ≤ k ≤ 3}dp[10][k], but it is intuitive that keeping 0 Martian Dollars at the end of the 10 th day should always cost less than keeping any positive amount of Martian Dollars).

Therefore the answer is 51.

Note that multiple tables were created for the purpose of illustration only; we only need to compute one such table for a single subtask.

Similarly, we can do subtasks (b) and (c).

Table for Subtask (b):

The values given are

Number\_of\_days = 15

Exp = 2

Lim = 5

day(i) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
C[i] 5 1 4 2 4 2 1 3 4 4 1 5 2 3 3

The table will be-

j \i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 10 12 14 17 21 25 27 29 33 40 42 44 47 51 56
1 15 13 15 19 23 27 28 30 36 44 43 45 49 53 59
2 20 14 19 21 27 29 29 33 40 48 44 50 51 56 62
3 25 15 23 23 31 31 30 36 44 52 45 55 53 59 65

Answer : 56

Table for Subtask (c):

The values given are

Number\_of\_days = 20

Exp = 1

Lim = 4

day(i) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
C[i] 4 2 1 1 3 1 6 3 4 5 5 4 1 5 4 6 6 4 3 1

The table will be-

ij 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 4 6 7 8 9 10 11 12 13 16 19 23 24 25 26 27 31 35 38 39
1 8 8 8 9 10 11 12 13 16 19 23 27 25 26 27 31 35 39 41 40
2 12 10 9 10 11 12 13 16 19 23 28 31 26 27 31 35 41 43 44 41
3 16 12 10 11 14 13 19 19 23 28 33 35 27 32 35 41 47 47 47 42

Answer : 39

Alternate Solution 1 (Greedy):

Our ultimate aim is to reach the last day, spending Exp everyday, such that the minimum amount in Rupees is deducted. Now suppose there was no restriction on the upper limit of Martian Dollars we can keep. If that was the case, suppose we are at some day, say day i, and let’s say after d days the exchange rate is “less than or equal” to that on the day i, and all the days in between have an exchange rate greater than that on day i. So we would stock as much required on day i to just survive all the days from day i to (i + d - 1) and on the (i + d)-th day, and we would just run out of Martian Dollars and therefore we would stock some more to keep going. Notice that instead of withdrawing on the i-th day, it is “always” beneficial to stock on the (i + d)-th day; the amount we stock on the i-th day is as little as necessary to reach the (i + d)-th day. Now we do the same thing on the (i + d)-th day, that is find out which day after that we would have an exchange rate less than the present day, and do exactly what we just did. If there is no such day, we simply stock enough to reach the last day.

But we do have an upper limit. To fix this, we simply don’t cross the limit. So if there are more days in between day i and day (i+d), than the number of days our upper limit would allow us to spend for; then we would just stock as much as possible, i.e. just up to the limit. Notice that if the number of days in between day i and day (i+d) is large, then withdrawing up to the limit is the most beneficial thing to do, since for some of the next few days (precisely the days in between day i and day (i+d)) have an exchange rate strictly greater than that on the i-th day.Otherwise, if the number of days in between is less enough, then we can just do what we did when there was no upper limit.

Subtask (b):

Let’s call the day which has an exchange rate “less than or equal” to that of the current day, Aim for that day. If there is no such day, Aim is just the last day. Also Aim for the last day is the last day itself. So in each step we would decide whether to stock the amount necessary to reach Aim (if Aim is close enough), or do we need to stock the maximum amount i.e. upto the limit(if Aim is not close enough).

Since Lim = 5, Exp = 2, we can only stock for Aim if it is within two days, otherwise we have to stock up to the limit.

Day Exchange rate Aim What we do Amount withdrawn Net amount we have after spending Amount deducted in Rupees on that day
1 5 2 Stock for Aim 2 0 10
2 1 7 Stock max 5 3 5
3 4 4 Stock for Aim 0 (since we already have enough to go to aim) 1 0
4 2 6 Stock for Aim 3 (since we already have 1 Martian Dollar) 2 6
5 4 6 Stock for Aim 0 (since we already have enough to go to aim) 0 0
6 2 7 Stock for Aim 2 0 4
7 1 11 Stock max 5 3 5
8 3 11 Stock max 2 (since we already have 3 and Lim = 5) 3 6
9 4 10 Stock for Aim 0 (we have enough to reach aim) 1 0
10 4 11 Stock for Aim 1 0 4
11 1 15 Stock max 5 3 5
12 5 13 Stock for Aim 0 1 0
13 2 15 Stock max 4 3 8
14 3 15 Stock for Aim 0 1 0
15 3 15 Stock for Aim 1 0 3

Net amount deducted = 10+5+0+6+0+4+5+6+0+4+5+8+0+3 = 56.

We can solve other subtasks similarly.

Alternate Solution 2 (Greedy):

Another approach might be to somehow prefer the days with less exchange rate for transaction compared to the days in which exchange rate is higher. But how exactly do we come up with a solution which utilizes this fact?

What we can do is, we can plan ahead, in which days we withdraw money by how much and in which days we spend the money withdrawn. In that plan, we will consider the days in increasing order of their exchange rate. What I mean by this is if exchange rates for five days are 1, 4, 6, 2, 3 then we would consider days in the order day 1, day 4, day 5, day 2, day 3 (In case of ties, we can take any order). Now, in the new order of days, we would withdraw the maximum amount of money that does not cross the upper limit and should not be somewhat excess. So we might keep a table containing two values W[i] and E[i] corresponding to each day i, which denote the amount withdrawn on day i and the amount that we can spend on day i respectively. We can initialize both of these to be 0 for all days. Now we will update these values gradually. What we might do is, consider the days in the increasing order of the exchange rates, and then decide how much to withdraw on a particular day by considering the E values of the next few days which can be updated by withdrawing on the current day. Our goal is to make every E value equal to Exp. This is best understood with an example.

Consider Subtask (a), we have Exp = 1 and Lim = 4. Suppose we have the ordering of the days. Now by “decide how much to withdraw on a particular day by considering the E values of the next few days which can be updated by withdrawing on the current day”, what I mean is: look at the current day, and the next three days only, because we can only have a maximum of 4 Martian Dollars and by spending 1 each, we do not have any control of the fourth day from our current day. So we look at the current day, and the next three days and see whether all E values are equal to Exp or not. If any of these are less than Exp, we can update that to Exp and since we need to withdraw that amount on the current day, we need to increment the W value of our current day by Exp. Notice that by considering days in the order of exchange rate, we actually have the minimum amount deducted. Now, let’s actually solve Subtask (a):

Number\_of\_days = 10

Exp = 1

Lim = 4

day(i) 1 2 3 4 5 6 7 8 9 10
C[i] 6 6 7 7 7 5 4 6 5 7

We can easily get the ordering of the days, which is 7, 9, 6, 1, 2, 8, 3, 4, 5, 10.

So we initially have

day 1 2 3 4 5 6 7 8 9 10
W 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0

Now we go to day 7, and since all values after that are 0, we make them equal to 1 each and change W[7] to 4.

day 1 2 3 4 5 6 7 8 9 10
W 0 0 0 0 0 0 4 0 0 0
E 0 0 0 0 0 0 1 1 1 1

Now we go to day 9, and observe that all four days after that have E = Exp, so we change nothing.

Then we go to 6 and see that E[6] is less than Exp, so we change E[6] to 1 and increase W[6] to 1. So we have

day 1 2 3 4 5 6 7 8 9 10
W 0 0 0 0 0 1 4 0 0 0
E 0 0 0 0 0 1 1 1 1 1

Now we come to day 1 and see that the E values of days 1, 2, 3, 4 are all 0. So we increment all by 1 and update W[1] = 4.

day 1 2 3 4 5 6 7 8 9 10
W 4 0 0 0 0 1 4 0 0 0
E 1 1 1 1 0 1 1 1 1 1

Then we come to day 2. We observe that among days 2, 3, 4, 5, only day 5 has E value equal to 0. So we make E[5] = 1 and W[2] = 2. So we have

day 1 2 3 4 5 6 7 8 9 10
W 4 1 0 0 0 1 4 0 0 0
E 1 1 1 1 1 1 1 1 1 1

Now all E values are equal to Exp, so we are done. Now we have to calculate the net amount deducted. We know that we withdrew 4, 1, 1, 4 Martian Dollars on days 1, 2, 6, 7, so we just need to multiply by the rates. So we have 4.6 + 1.6 + 1.5 + 4.4 = 24 + 6 + 5 + 16 = 5 (Answer).

We can solve Subtask (c) similarly. But for Subtask (b), there is a small catch. Consider that the current day is day i. Since Lim = 5 and Exp = 2, we can increase E[i] and E[i+1] to 2. But for E[i+2], we cannot make it 2; we can only make E[i+2] = 1, since our Lim = 5. With this slight modification we can solve the Subtask (b).

I would like to thank @akashbhalotia sir, for sharing the last two solutions.

2 Likes