When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

delta13's blog

By delta13, history, 6 years ago, In English

Problem Statement: USA Computing Olympiad

Problem Solution: Contest Results

Problem Summary: Essentially the problem describes Bessie the cow traveling through a course consisting of N checkpoints visited in sequence. However, being lazy, Bessie decides to skip K checkpoints where K < N (She cannot skip the first and last checkpoints as well). We must find the minimum distance Bessie is required to run by skipping K checkpoints. In this case, the distances are computed as Manhattan distances where the distance from x to y would be represented as: |x1-x2| + |y1-y2|.

Question: The issue is I am having trouble wrapping my head around the dynamic programming solution (linked above). Could someone provide a through explanation of the steps in discovering such a dynamic programming solution as well? Thanks for the support!

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

| Write comment?
»
6 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

Look at this loop:

    for(int i = 0; i <= k; i++) {
      for(int j = 0; j < n; j++) {
        for(int l = j+1; l < n && i + l-j-1 <= k; l++) {
          int nextI = i + (l-j-1);
          int nextJ = l;
          dp[nextI][nextJ] = Math.min(dp[nextI][nextJ], dp[i][j] + distBetween(j, l));
        }
      }
    }

I'm assuming that you were able to catch that dp[i][j] is the shortest distance to point j after skipping i points.

It might look complicated, but it's actually not. In the inner loop, Bessie has skipped i points and is currently at point j. l is a potential value for the next point that Bessie can go to (nextI corresponds to the total number of points skipped if Bessie goes directly to l). The inner loop updates the distance to nextJ after Bessie skips a total of nextI steps.

The result is dp[k][n-1] which is the shortest distance to point n - 1 after skipping k steps (n - 1 in this case since the points are indexed at zero, not one).

Dynamic programming quite often involves being at a particular state (in this case being at point j after skipping i points) and observing the possible subsequent states. I don't think there was anything particularly clever as this problem uses a standard form of dp. Look out for these problems in the future.

Let me know if you need any more clarifications.