CCO '05 P5 - Segments

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 16M

Problem type
Canadian Computing Competition: 2005 Stage 2, Day 2, Problem 2

You are to find the length of the shortest path from the top to the bottom of a grid covering specified points along the way.

More precisely, you are given an n by n grid, rows 1 \dots n and columns 1 \dots n (1 \le n \le 20\,000). On each row i, two points L(i) and R(i) are given where 1 \le L(i) \le R(i) \le n. You are to find the shortest distance from position (1, 1), to (n, n) that visits all of the given segments in order. In particular, for each row i, all the points

\displaystyle (i, L(i)), (i, L(i)+1), \dots, (i, R(i)-1), (i, R(i))

must be visited. Notice that one step is taken when dropping down between consecutive rows. Note that you can only move left, right and down (you cannot move up a level). On finishing the segment on row n, you are to go to position (n,n), if not already there. The total distance covered is then reported.

Input Specification

The first line of input consists of an integer n, the number of rows/columns on the grid. On each of the next n lines, there are two integers L(i) followed by R(i) (where 1 \le L(i) \le R(i) \le n).

Output Specification

The output is one integer, which is the length of the (shortest) path from (1, 1) to (n, n) which covers all intervals L(i), R(i).

Sample Input

2 6
3 4
1 3
1 2
3 6
4 5

Sample Output


Explanation for Sample Output

Below is a pictorial representation of the input.

1       2       3       4       5       6
.       _________________________________
                        _________       .

Notice that on the first row, we must traverse 5 units to the right and then drop down one level.

On the second row, we must traverse 3 units to the left and drop down one level.

On the third row, we must traverse 2 units to the left and drop down one level.

On the fourth row, we move 1 unit to the right and then drop down one level.

On the fifth row, we move 4 units to the right and drop down one level.

On the sixth (and final) row, we move 2 units left, then 2 units right.

In total, we have moved 6+4+3+2+5+4 = 24 units.


There are no comments at the moment.