A seam through a pixel
A photo editor has a “remove object” button: the user points at a pixel, and the editor tells what it would cost to carve a seam through it. A seam is one pixel in each row from top to bottom, with the pixels of neighbouring rows in the same column or adjacent ones, and a seam’s energy is the sum of its pixels’ energies. For each pixel pointed at, find the smallest energy of a seam passing through it.
The third test is a real photo by the site’s author, 120 pixels wide, and it asks about every pixel.
Input
The first line holds the height H and width W (1 ≤ H, W; H·W ≤ 2.5·105). Then H lines of W integers from 0 to 1530: the pixels’ energies. Then the number of questions q (1 ≤ q ≤ 105) and q lines r c: the pixel’s row and column, from one.
Output
For each question, the smallest energy of a seam through that pixel.
Examples
Example 1
7 10 37 58 68 73 48 100 79 90 84 95 104 63 76 61 58 68 89 101 92 64 76 58 79 83 89 100 110 84 84 87 75 118 104 70 60 48 35 28 35 44 333 371 272 109 61 107 99 163 150 65 289 166 355 263 156 162 207 214 237 183 311 411 267 109 92 138 163 212 197 94 5 1 1 5 1 7 5 4 10 6 2
558 999 552 618 954
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
One question is answered by the cheapest-seam table in which only pixel c is allowed in row r. But a table costs H·W steps, and a hundred thousand tables are 2.5·1010. What do these tables have in common?
2Hint 2
A seam through pixel (c, r) consists of two halves: from the top down to the pixel and from the pixel to the bottom. Do these halves depend on each other?
3The idea
The halves are independent: the upper part of a seam does not care how it goes below the pixel, and vice versa. So the best seam through a pixel is the best seam from the top to it plus the best seam from the bottom to it. Compute two tables: down[y][x], the cheapest seam from the top row to the pixel, as in seam carving, and up[y][x], the same from the bottom row. The answer to a question is down[r][c] + up[r][c] − E[r][c]: the pixel itself entered both halves.
4Walkthrough
The table up is the same as down, only for the picture turned upside down: in Python it is enough to reverse the list of rows, compute and reverse the result back. After that each question is three array accesses.
The trick “compute in advance from both ends and join at the point” comes up often: this is how the cheapest path through a given vertex of a graph is found, or the number of shortest paths passing through it. It works whenever the two pieces of the answer do not interfere with each other.
4+Solution
5Complexity
O(H·W + q) time and O(H·W) memory: two tables and O(1) per question.
6Common mistakes
- A separate table per question. Correct, but the third test alone is 7320 questions about a 120 × 61 photo, and the large tests have up to a hundred thousand questions.
- The pixel counted twice. Without subtracting E[r][c] the answer is larger than the correct one by the pixel’s own energy.
- The seam “from below” by the top table. down[H−1] knows the best seams ending in the bottom row, but not the best path down from a given pixel: a separate table is needed.