UVa 10418

From Algorithmist
Jump to navigation Jump to search

10418 - Hyper-Toy Soldiers[edit]

Explanation[edit]

Notice that on a set of moves, when the up soldiers and down soldiers are stuck, we will swap every soldier because it does not make sense to keep them stuck when we can put them into a place to progress towards a target. Also every permutation we can swap the Golden Soldier with a stuck soldier not on a target and move him to a any target of choice. Thus in the worst case we can always get all soldiers on targets in 2k permutations where k=up soldiers=down soldiers.

This problem is really two steps. First we have to determine the smallest number of permutations from any soldier starting point to every target on the board. A modified DFS-BFS combination algorithm can be run from every soldier position to build a table of permutations for each soldier to each target. When this table is complete the problem turns into a Maximum Bipartite Matching problem, with a small twist to handle the Golden soldier. Lastly we binary search on the bipartite matching algorithm to determine if a given number of permutations is enough for all soldiers to reach a target.

Input[edit]

5

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

4 3 3 7
1 1 1 2 1 3 4 1 4 2 4 3 1 1
1 1 1 2 1 1 2 2 1 2 3 1 3 1 1 3 2 1 3 3 1
1 1 1
2 2 2
3 3 3
4 4 4

8 11 3 7
1 1 1 5 1 9 8 1 8 5 8 9 4 5
1 3 1 1 7 1 1 11 1 4 5 1 8 3 1 8 7 1 8 11 1
9 2 3 1 9 2 3 1 9 2 3
1 1 1 1 1 1 1 1 1 1 1
9 9 9 9 9 9 9 9 9 9 9
1 1 1 1 1 1 1 1 1 1 1
9 9 9 9 9 9 9 9 9 9 9
1 1 1 1 1 1 1 1 1 1 1
9 9 9 9 9 9 9 9 9 9 9
1 8 7 9 1 8 7 9 1 8 7

7 4 5 7
4 2 6 4 2 3 4 2 4 1 1 2 7 1 2 4 1 2 3 4 7 6
4 1 2 1 2 3 1 1 1 2 2 2 7 4 1 6 4 1 4 2 3
32 12 32 54
62 92 28 48
27 23 91 38
71 68 1 59
93 19 38 32
41 28 26 24
29 12 11 92

30 30 10 11
5 2 7 2 4 6 2 3 30 30 30 30 29 28 25 15 12 18 19 20 20 25 2 27 18 12 28 2 8 18 17 3 9 30 7 8 9 11 11 15 15 12
27 6 2 2 8 2 18 2 3 25 5 3 2 18 1 3 18 1 20 21 1 30 5 2 6 8 2 11 27 3 8 21 1
26 76 82 52 51 31 21 21 100 74 50 6 77 8 4 100 53 82 35 82 13 89 12 1 62 27 40 17 43 89 
12 25 6 25 69 48 24 93 68 37 19 48 23 88 49 93 88 3 31 40 70 27 63 55 5 2 81 76 11 39 
84 56 37 96 85 81 83 73 60 66 87 86 34 38 15 97 93 6 2 18 66 7 64 72 27 65 52 44 16 3 
17 92 38 96 82 39 99 97 44 18 32 93 65 99 57 56 94 31 49 77 18 61 65 14 34 98 6 23 32 86 
22 40 4 19 76 76 65 42 24 98 1 57 85 16 82 16 37 23 7 62 70 50 88 34 59 52 90 99 89 4 
25 85 41 48 37 80 16 75 59 86 84 14 49 76 99 11 71 34 63 72 16 42 85 32 4 59 46 73 47 90 
64 82 31 7 51 95 24 51 50 20 25 82 29 31 64 26 2 54 99 14 99 9 52 5 92 66 25 9 39 52 
69 93 59 14 39 66 78 96 39 4 22 72 72 96 27 52 41 75 94 33 8 11 77 51 17 60 83 82 76 100 
85 94 14 23 10 71 55 96 27 70 80 8 41 98 9 50 27 9 74 16 80 76 44 68 60 43 10 17 76 45 
77 26 85 50 44 82 77 84 77 93 71 17 94 24 39 94 14 47 49 16 81 17 88 34 70 86 74 55 32 99 
82 100 67 5 13 62 57 86 4 22 41 81 48 31 45 1 13 62 48 61 85 23 85 97 17 79 67 72 57 19 
38 41 3 10 90 95 74 35 77 77 18 25 8 62 9 53 76 95 30 12 46 99 16 62 16 72 96 11 24 34 
1 39 77 95 91 25 46 22 13 91 51 22 21 85 97 32 79 80 75 3 94 38 15 91 21 90 48 5 21 54 
10 98 80 39 88 26 80 8 26 26 67 28 86 42 52 22 92 1 65 87 77 16 10 79 68 39 48 81 90 74 
56 50 15 63 16 89 64 35 39 67 83 13 14 85 68 41 24 25 31 33 91 37 22 45 59 71 61 63 75 65 
65 83 11 65 19 54 33 13 77 27 22 64 23 76 2 39 75 82 71 6 14 94 20 26 62 25 66 62 46 15 
24 39 26 27 7 53 15 56 37 42 87 53 27 57 35 89 86 76 2 53 26 28 88 90 26 39 36 10 12 28 
9 17 49 32 74 94 72 24 87 40 26 23 27 69 39 60 40 27 80 6 20 93 6 73 19 12 96 19 74 87 
93 43 68 61 20 11 21 53 24 49 40 35 21 77 20 54 78 8 38 96 1 94 84 67 38 67 16 6 53 95 
41 62 82 23 6 58 97 9 43 56 84 81 62 24 90 55 50 35 26 14 44 91 38 95 24 56 91 77 82 2 
77 80 39 71 6 96 59 52 24 76 36 96 82 47 96 45 33 33 60 10 68 98 56 60 35 12 63 96 44 31 
46 86 66 69 26 87 14 77 89 32 12 25 56 5 22 95 49 38 100 21 75 76 26 72 93 5 35 97 39 87 
79 41 46 64 2 59 21 24 49 40 93 17 23 43 94 54 63 64 26 7 63 15 96 44 62 35 10 42 82 24 
69 65 84 9 44 62 78 26 73 40 43 90 84 71 45 12 84 32 24 65 10 21 11 83 84 8 23 45 97 55 
38 44 22 94 97 40 94 28 9 24 65 77 53 75 28 99 37 51 21 69 44 51 55 3 49 20 18 36 100 37 
57 84 85 6 97 75 66 23 42 29 48 51 92 68 88 65 98 53 36 47 54 21 47 14 40 72 50 10 44 30 
87 84 22 56 30 34 86 76 79 45 4 54 22 25 58 62 78 10 34 31 10 74 1 27 10 22 89 76 100 23 
7 24 3 1 19 23 50 44 96 85 75 85 76 39 4 19 76 40 4 48 6 57 1 28 47 65 44 15 90 46 
56 49 72 11 20 40 34 20 67 26 29 60 62 56 48 61 88 84 36 29 25 6 24 12 30 7 44 82 69 80 
19 14 52 26 81 32 47 98 8 100 93 60 85 57 74 85 60 62 42 46 52 95 29 27 89 21 92 71 94 17 

Output[edit]

1
0
2
1
6