# UVa 103

Jump to navigation Jump to search

## Summary

This is a Longest Increasing Subsequence problem, with a little twist. Sorting is required to give us the properties that allow us to make the connection.

• You can also solve it by Branch and bound using backtracking!
• You can also solve it as a graph problem. Considering each box as a node, and the relation "fits in" as edges. The solution is then the longest path in this DAG. (Which of course is a complex way to solve the LIS problem.)

## Explanation

It should be clear that it's a Longest Increasing Subsequence problem. We want to be able to check if box a fits in box b easily. To accomplish this, we first sort on the dimensions of each box to renormalize it - giving us, for each box, the dimensions ${\displaystyle (s_{1},s_{2},s_{3},...,s_{i})}$ such that ${\displaystyle s_{i}\leq s_{j}}$ for all ${\displaystyle i.

Now, box a is in box b if the dimension vector of box a is less than the dimension vector of box b. (${\displaystyle a if ${\displaystyle a_{i} for all i).

Sort all the boxes using the above definition, and we can then use the Longest Increasing Subsequence algorithm. (For this problem, the ${\displaystyle O(n^{2})}$ implementation is enough.)

Note that the boxes need to be sorted, before using the Longest Increasing Subsequence algorithm, using its dimensions as priority. What that means is that if the first dimension of box a is less than the first dimension of box b, consider a as less than b. The same apply if the first dimension is greater, meaning that the box a is greater than box b. Now, if they are equal, use the next dimension to decide. Decide as soon as possible.

## Input

5 2
3 7
8 10
5 2
9 11
21 18
8 6
5 2 20 1 30 10
23 15 7 9 11 3
40 50 34 24 14 4
9 10 11 12 13 14
31 4 18 8 27 17
44 32 13 19 41 19
1 2 3 4 5 6
80 37 47 18 21 9
10 2
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
6 1
6
8
10
4
5
4
30 10
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
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
200 201 202 203 204 205 206 207 208 209
100 101 102 103 104 105 106 107 108 109
300 301 302 303 304 305 306 307 308 309
200 201 202 203 204 205 206 207 208 209
100 101 102 103 104 105 106 107 108 109
300 301 302 303 304 305 306 307 308 309
400 401 402 403 404 405 406 407 408 409
500 501 502 503 504 505 506 507 508 509
411 412 413 414 415 416 417 418 419 420
521 522 523 524 525 526 527 528 529 530
50 60 70 80 90 50 60 70 80 90
20 30 40 50 60 70 80 90 10 99
10 9 8 7 6 5 4 3 2 1
19 29 39 49 59 69 79 89 95 9
15 35 25 45 65 55 85 75 93 5
50 60 70 80 90 50 60 70 80 90
20 30 40 50 60 70 80 90 10 99
10 9 8 7 6 5 4 3 2 1
19 29 39 49 59 69 79 89 95 9
15 35 25 45 65 55 85 75 93 5


## Output

5
3 1 2 4 5
4
7 2 5 6
1
1
5
4 5 1 2 3
13
1 2 3 4 5 21 12 11 13 17 19 18 20