arujbansal's blog

By arujbansal, 4 years ago, In English

Take a look at the tasks here: Contest Link


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

| Write comment?
»
4 years 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

  • »
    »
    4 years 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.

    • »
      »
      »
      4 years 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.

      • »
        »
        »
        »
        4 years 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

        • »
          »
          »
          »
          »
          4 years 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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is there any solution for D using top down approach or we have to go for recursive dp always? I am new to DP problems.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Try this code for top-down :

      Spoiler
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My Solution using bottom-up note: "berat" means weight

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    The solution given here for Knapsack 1 fails for many test cases, Had your same submission got accepted ?

»
4 years 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:

»
4 years 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.

  • »
    »
    4 years 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.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Start of with the recursive approach first. Then go for the memoizing. Have a look at this solution for problem C. https://www.youtube.com/watch?v=7MTpY-kbX74

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The editorial written by the author is sufficiently detailed and there is no need for him to start off in the way you are suggesting.

»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

If you want you can use this for Problem J's editorial: Sushi editorial written by me
It is quite easy to understand and well detailed(atleast that is what I think :p)

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can problem Frog 2 solved with the complexity of $$$O(n\ polylog\ n)$$$ ?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, I think you can do it with BIT or Segment Tree. I think it will work by doing RMQ, but how you maintain the |h_i-h_j| is the problem.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Somebody please tell the approach for M-Candies using recursive dp

»
13 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Can anyone Explain the rooting of Subtree .