Solving an AtCoder Problem, Picking Goods

Hi everyone,

I recently discovered another competitive programming website called AtCoder. At least once a month they run the AtCoder Beginner Contest (ABC). I recommend taking a look at these contests. You’ll find a mix of challenge levels involving material assumed by my Algorithmic Thinking book, material taught in the book, and even some material beyond the book.

(… Yeah: the Beginner descriptor isn’t lost on me. Nor the ABC taunt. Ahh well: we’re all beginners relative to someone.)

I’ve been having fun solving these problems, so I chose one for us to solve here. It’s the Picking Goods problem from AtCoder Beginner Contest 175.

The Problem

There is a grid with $r$ rows and $c$ columns. The rows are numbered from $1$ at the top to $r$ at the bottom; the columns are numbered from $1$ at the left to $c$ at the right. I’ll occasionally use the notation $(r, c)$ to refer to row $r$, column $c$.

Takahashi begins at row 1, column 1 (the top left); he wants to end up at row $r$, column $c$ (the bottom right).

At each step, Takahashi can move one position to the right (moving to the next column) or one position down (moving to the next row).

Why is Takahashi moving around this grid? Well, it’s because there are valuable items here! Takahashi wants to maximize the total value of items that he can collect on his way from the top left square to the bottom right square. He is allowed to pick up at most three items per row.

Input

The first line of input contains three integers: the number $r$ of rows in the grid, the number $c$ of columns in the grid, and the number $k$ of items that are in the grid. $r$ and $c$ are between $1$ and $3000$; $k$ is between $1$ and $200000$.

Each of the next $k$ lines contains the information for one item, in the form of three integers: the item’s row, the item’s column, and the item’s value. No two items exist at the same row and column; each item value is between $1$ and $1000000000$.

Output

Output the maximum sum of item values that Takahashi can pick up.

Example

Here’s a test case:

3 5 7
1 5 50
2 1 25
2 2 35
3 2 1
3 3 1
3 4 1
3 5 8

It’s common in these types of problems for the input to be laid out as a grid of values, but that’s not what the input for this problem looks like. Rather, as I described above, the input for each item is on its own, separate line, and gives the item’s row, column, and value. I’ve ordered the items from top to bottom, left to right, but there’s no guarantee of this ordering in general.

It can be easier to visualize what’s happening here if we do display the test as a grid. We can put item values in the appropriate cells of the grid, and use x for a position that has no item, like this:

 x  x  x  x 50
25 35  x  x  x
 x  1  1  1  8

Starting at the top left, where should we go? Remember that at each move we have to make a choice of whether to go to the right or down. There’s that unbelievable 50 at the top-right corner – wouldn’t it be nice to walk right over there and get that? no! That 50 turns out to be pretty manky, because all we could do after getting the 50 is walk straight down and get the 8. That would give us $50+8=58$ total value.

But we can do better. Starting from the top-left corner, here we go: move down and get the 25, move right and get the 35, move down and get the 1, move right and get the 1, move right and don’t get the 1, move right and get the 8. (The reason we had to skip the 1 there is so that we could still pick up the 8. Remember: we can pick up at most three items per row!) That’s $25+35+1+1+8=70$. That’s the best we can do here, and is the correct answer for this test case.

Dynamic Programming

This is a Dynamic Programming problem. I’d say that the example closest to this one in the book is the Hockey Rivalry problem. At this point, I’d recommend re-reading Chapter 3 in the book, working through the four steps for developing a dynamic programming solution to solve the current problem. I’ll hit the highlights here, but there’s no substitute for practice. If you get stuck, keep reading here – but as soon as you feel unstuck, go back to your code and try to finish up!

Many problems that involve moving through a grid can be solved by dynamic programming. The idea is to use subproblem $(i, j)$ to hold the best solution to get from the starting point to position $(i, j)$. When dynamic programming works for these problems, it’s because there are only a small number of possibilities for what the optimal solution to $(i, j)$ must look like.

For the current problem, we might think that a two-dimensional dynamic programming table will suffice. After all, we care about keeping track of the current row and column, right? So one dimension for the row, one dimension for the column? ??

Not quite. If we try, we run into difficulty. Suppose we want to know the maximum sum of item values that can be picked up starting at the top-left corner and ending at $(i, j)$. One possibility is that we come from column $j-1$ and pick up the item at $(i, j)$. Our solution would include the value of the item at $(i, j)$, plus the solution for $(i, j-1)$. But if we just solve $(i, j-1)$ here, we might end up picking up too many items in the current row $i$. Maybe solving $(i, j-1)$ optimally already picks up three items in row $i$. Then we’re in fact not allowed to pick up the item at $(i, j)$ at all.

No: just knowing the target row and column is not sufficient. We also need to know how many items we are allowed to pick up in the current row. And this means that we’re going to use a three-dimensional dynamic programming table, not a two-dimensional one. The first dimension specifies a row, the second specifies a column, and the third specifies the number of items we are allowed to pick up in the current row (between 3 if we haven’t picked up anything in the current row, and 0 if we’ve already picked up three items and aren’t allowed to pick up anymore). That is, each subproblem is specified by three indices $(i, j, k)$.

There are now only four possibilities for the optimal solution for subproblem $(i, j, k)$:

1. Come from the row above; don’t pick up the item at $(i, j)$. Solving this involves solving the subproblem for $(i-1, j, 3)$. Why the 3 there? Because we’re moving down to row $i$; so picking up three items in the row above is just fine.
2. Come from the row above; do pick up the item at $(i, j)$. We can only do this one if $k > 0$; if $k$ is already $0$, then we’re not allowed to pick up anything else in this row.
3. Come from the column to the left; don’t pick up the item at $(i, j)$. Solving this involves solving the subproblem for $(i, j-1, k)$.
4. Come from the column to the left; do pick up the item at $(i, j)$. We can only do this one if $k > 0$.

The Code

Here’s my code for solving the problem.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE 3000
#define MAX_ROW 3

long max(long v1, long v2) {
  if (v1 > v2)
    return v1;
  else
    return v2;
}

long solve(long grid[SIZE + 1][SIZE + 1], int r, int c) {
  int i, j, k;
  long first, second, third, fourth;
  static long dp[SIZE + 1][SIZE + 1][MAX_ROW + 1];

  for (i = 1; i <= r; i++)
    for (j = 1; j <= c; j++)
      for (k = 0; k <= MAX_ROW; k++) {
        
        // Come from the row above; don't take item at (i, j)
        first = dp[i-1][j][MAX_ROW];
        
        // Come from the row above; take item at (i, j)
        if (k > 0) 
          second = grid[i][j] + dp[i-1][j][MAX_ROW];
        else
          second = 0;
        
        // Come from the column to the left; don't take item at (i, j)
        third = dp[i][j-1][k];
        
        // Come from the column to the left; take item at (i, j)
        if (k > 0) 
          fourth = grid[i][j] + dp[i][j-1][k-1];
        else
          fourth = 0;
        
        dp[i][j][k] = max(first, max(second, max(third, fourth)));
  }
  return dp[r][c][MAX_ROW];
}

int main(void) {
  int r, c, k, i;
  int next_r, next_c, next_v;
  static long grid[SIZE + 1][SIZE + 1];

  scanf("%d%d%d", &r, &c, &k);

  for (i = 0; i < k; i++) {
    scanf("%d%d%d", &next_r, &next_c, &next_v);
    grid[next_r][next_c] = next_v;
  }

  printf("%ld\n", solve(grid, r, c));
  return 0;
}

Here are some questions for you about the code:

1. Why do the grid and dp arrays use size + 1 instead of size?
2. Nowhere in the code do I check where there is actually an item at grid[i][j]. Why is this OK?

In Closing

Keep practicing! :) I’ve been collecting a few practice problems corresponding with the book chapters. Please get in touch if you have a favourite problem that you’d like me to consider.

I maintain a very low-traffic newsletter where I send occasional updates related to the book, algorithms, and competitive programming. Please see my Contact and Newsletter page if you’re interested. Thanks!