UVa 103

From Algorithmist
Jump to: navigation, search

103 - Stacking Boxes[edit]

Summary[edit]

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[edit]

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 (s_{1},s_{2},s_{3},...,s_{i}) such that s_{i}\leq s_{j} for all i<j.

Now, box a is in box b if the dimension vector of box a is less than the dimension vector of box b. (a<b if a_{i}<b_{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 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.

Gotcha's[edit]

Input[edit]

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[edit]

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 

Solution[edit]

Solution Hints[edit]