Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

arujbansal's blog

By arujbansal, 5 weeks ago, In English,

Motivation Behind Writing This Editorial

Initially, Dynamic Programming is a hard concept to grasp. I had a lot of difficulty when I started out. One of the problems were that there was no text based editorial for the Atcoder Educational DP contest and I had to go through videos again and again because sometimes they weren't clear.
I will be updating this blog post with solutions to more problems frequently. If something is unclear, please let me know so that I can explain it better.
This editorial is written keeping beginners in mind, not skipping small details presuming that they will be familiar with them.

As there are a lot of problems, it will probably take me a long time to cover them all. If you wish to contribute to this post, please write a comment or message me.

Also, I have not been able to find a single post or blog containing explanations to all these problems. There are many video based editorials but sometimes you don't want to watch a whole video as you might know the concept and just want a hint or you learn better by reading.

Contest Link
UPD: More problems coming soon!


A — Frog 1

The main thing to note in this problem is that the frog, from a position i can jump to only i + 1 or i + 2. This simplifies the problem.
We will create an array dp of size n (the total number of stones). dp[i] will store the minimum cost we can achieve till position i. An array jumps of size n will store the height of each stone.

For our base cases, we will set dp[0] = 0 and dp[1] = abs(jumps[1] — jumps[0]) as if we are on the second stone (0 based indexing), there is only one way to reach it i.e from the first stone.

Now, to get our final answer, dp[n-1], we need to solve all of our subproblems. To solve for any given position i, we need to have calculated the best we could do for positions i — 1 and i — 2. Why do we need to only consider positions i — 1 and i — 2? Well that is because the frog can only jump one or two stones ahead of its current position i.e to reach its current position i it had to have been at either i — 1 or i — 2.

We can simply do this in O(n).
For any given position i > 2, we can solve the subproblem this way:

dp[i] = min(dp[i-1] + abs(jumps[i] - jumps[i-1]), dp[i-2] + abs(jumps[i] - jumps[i-2]))

dp[i] will be the minimum cost to reach that position. To calculate this, we find the minimum cost of reaching positions i — 1 and i — 2. and then add the cost of jumping to position i and store the minimum.

Problem Link
Solution Link


B — Frog 2

This problem is slightly different from the first one. This time, we are given an additional variable k telling us the maximum size of a jump. k in the last problem was basically fixed to 2 as from a stone i we could only jump to i + 1 and i + 2.

Now, how do we modify our solution to handle this new case where k can be greater than 2?

We will still create an array dp (all values set to INFINITY) of size n (the number of stones we have). dp[i] will denote the minimum cost to reach stone i.
Our base case again, dp[0] = 0 (0 based indexing) as we start off from the first stone.

We use a nested loop:

for (int i = 0; i < n; i++) { // i represents the stone the frog is currently at.
        for (int j = i + 1; j <= i + k; j++) { // j represents a potential stone for the frog to jump to.
            if (j < n) // We have to check if the stone we want to jump to is not out of bounds.
                // Storing the total minimum cost to reach stone j from stone i.
                dp[j] = min(dp[j], dp[i] + abs(stones[j] - stones[i]));
        }
}

Here, the first for loop denotes that the frog is currently at stone[i]. The second for loop basically calculates the best we can do if we jump from stone[i] to stone[i+1], stone[i+2], stone[i+3] ... stone[i+k].
We are performing the min() operation because if the cost of jumping from i to j is higher than a cost we have already found, we do not want to update dp[j] to a higher cost.

We perform this for every position the frog could be at i.e it is performed for all positions i, i+1, i+2...n.

After performing these operations (solving all the subproblems), our final answer is stored at dp[n-1] (0 based indexing).

Problem Link
Solution Link


C — Vacation

We are given three types of activities. We get different amount of points by doing each activity each day. The only restriction is that we cannot do the same activity on two consecutive days.
For example, if we did activity A yesterday, we cannot do activity A today but we can do it tomorrow.

To solve this problem, we will maintain a 2D array, dp[n][3].

dp[i][0] will store the maximum points we can gain by doing activity A on day i.
dp[i][1] will store the maximum points we can gain by doing activity B on day i.
dp[i][2] will store the maximum points we can gain by doing activity C on day i.

Our base cases will be:

// If you swim in the sea in sea on the first day, you cannot get more than a[0] points.
dp[0][0] = a[0]; 
// If you catch bugs in the mountains on the first day, you cannot get more than b[0] points.
dp[0][1] = b[0]; 
// If you do homework at home on the first day, you cannot get more than c[0] points.
dp[0][2] = c[0]; 

For every day i, as we cannot do the activity we did on the previous day,

// If we do activity A today, we have to have done activities B or C on the previous day.
dp[i][0] = a[i] + max(dp[i - 1][1], dp[i - 1][2]); 

// If we do activity B today, we have to have done activities A or C on the previous day.
dp[i][1] = b[i] + max(dp[i - 1][0], dp[i - 1][2]);

// If we do activity C today, we have to have done activities A or B on the previous day. 
dp[i][2] = c[i] + max(dp[i - 1][1], dp[i - 1][0]); 

Simply by checking for each day i, we can calculate the best we can do by the end of our last day.
As we can end by doing activities A, B, or C, our answer will be the maximum points gained on doing activities A, B, or C on the last day.
Time complexity: O(n)

Problem Link
Solution Link

 
 
 
 
  • Vote: I like it
  • +38
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

D — Knapsack 1

One of the most basic DP Problem two state DP is all we need (DP[105][1e5+5]) note that we can define a global array of this size. Then all we need to do is go to each item. We will start from index 0 and recursively go till index n. At every index We have two Choice :-

Either we take the item of current index and its value to answer and weight to Knapsack and move to next indexdynamic(pos + 1, we + w[pos]) + v[pos]

Or

We dont take the item and simply move to next index dynamic(pos + 1, we)

We always take maximum of these two recursive calls at every index because we have to maximize the total value of weight in knapsack.

We also keep a check at total weight inside knapsack as it can never be greater than knapsack capacity and if it exceeds it we return INT_MIN because the value of that weight is not a valid ans.

if (we > wt) return INT_MIN;

Problem Link

Solution Link

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Please elaborate. I'm writing this post keeping beginners in mind. I have also tried to remove most of my code template from my solution link so that it improves readability and I have added comments.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Alright I will edit my code to remove the template and elaborate the solution more.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Any hint for Knapsack 2? I tried to solve it but get a TL

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          In Knapsack 1 the value of W was less so you were able to build a dp of [Position][Weight] and were able to maximize the total value which is not the case in knapsack 2 as the weights are huge. The Hint is that do reverse this time for every value check if it is possible or not by minimizing weight and take maximum of possible values.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice editorial! I hope you finish it soon :D

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It is certainly a pity that the official contest didn't include a proper editorial. I hope you can complete this post so we have a complete tutorial for these classical problems c:

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

By the way, many of the solutions were discussed in the comments at https://codeforces.com/blog/entry/64250. Maybe you want to go into more detail since you are targeting beginners, but hopefully that will help.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, thanks for sharing this! It will help a lot.
    I am going to add more detail to the editorials. Even though this is targeting beginners, it will have the explanations to the problems in a structured manner, something that I could not find anywhere.