IOI 2009 - Day 0 - Hill
Okay, first up, the "hill" question.
So you have a grid, up to 1000x1000 cells, and every cell has a distinct positive altitude. You can query the altitude of up to 3050 cells ("scanning" them with your laser) and you have to discover and report the location of a cell that is higher than its four neighbours (a "hill").
The naive solution would be to start in any cell and scan its neighbours. As soon as you find a higher one, switch to it and repeat. If you find no higher one you have discovered a hill and can stop. However, this is not guaranteed to find a hill within 3050 scans. If that's not obvious, consider this pathological case:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
198 197 196 195 194 193 192 191 190 189 188 187 186 185 16
199 52 53 54 55 56 57 58 59 60 61 62 63 184 17
200 51 154 153 152 151 150 149 148 147 146 145 64 183 18
201 50 155 88 89 90 91 92 93 94 95 144 65 182 19
202 49 156 87 126 125 124 123 122 121 96 143 66 181 20
203 48 157 86 127 108 109 110 111 120 97 142 67 180 21
204 47 158 85 128 107 114 113 112 119 98 141 68 179 22
205 46 159 84 129 106 115 116 117 118 99 140 69 178 23
206 45 160 83 130 105 104 103 102 101 100 139 70 177 24
207 44 161 82 131 132 133 134 135 136 137 138 71 176 25
208 43 162 81 80 79 78 77 76 75 74 73 72 175 26
209 42 163 164 165 166 167 168 169 170 171 172 173 174 27
210 41 40 39 38 37 36 35 34 33 32 31 30 29 28
211 212 213 214 215 216 217 218 219 220 221 222 223 224 225
Here there's only one "hill": the 225 cell in the bottom-right. Suppose you start searching at 114 near the centre. Its highest neighbour is 115. 115's highest neighbour is 116. And so on, round and round the spiral, until you eventually reach the hill. On a 1000×1000 cell grid you could need many, many more scans than the 3050 allowed.
However, we can do better. Let's try subdivision. (Credit to my colleague Luke who came up with a lot of the ideas here.) We'll start by doing a sweep that cuts the grid in two. We can afford that - it takes 1000 of our 3050 budget on a full-sized grid - so long as we don't plan to make many more of this length! Here I've highlighted the sweep:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
198 197 196 195 194 193 192 191 190 189 188 187 186 185 16
199 52 53 54 55 56 57 58 59 60 61 62 63 184 17
200 51 154 153 152 151 150 149 148 147 146 145 64 183 18
201 50 155 88 89 90 91 92 93 94 95 144 65 182 19
202 49 156 87 126 125 124 123 122 121 96 143 66 181 20
203 48 157 86 127 108 109 110 111 120 97 142 67 180 21
204 47 158 85 128 107 114 113 112 119 98 141 68 179 22
205 46 159 84 129 106 115 116 117 118 99 140 69 178 23
206 45 160 83 130 105 104 103 102 101 100 139 70 177 24
207 44 161 82 131 132 133 134 135 136 137 138 71 176 25
208 43 162 81 80 79 78 77 76 75 74 73 72 175 26
209 42 163 164 165 166 167 168 169 170 171 172 173 174 27
210 41 40 39 38 37 36 35 34 33 32 31 30 29 28
211 212 213 214 215 216 217 218 219 220 221 222 223 224 225
Now, in that sweep, one cell must be higher than all the others. That's easy to remember. In this case, 218 is our highest value. Let's scan the cells on either side of it. Now, either at least one of its neighbours is higher than it, or neither is. If neither is higher, then it must be a hill, and we can stop! If one is higher, then we have discovered something important: there must be a hill somewhere on that side of the divide. We know this because every cell in the dividing line is lower than this neighbouring cell; the upward path from the neighbouring cell cannot wander back across the dividing line, so it must terminate in a hill somewhere on that side. In this case, we find that cell 219 is higher, so we know there must be a hill somewhere on the right.
Now, can we repeat this subdivison? It gets a bit trickier. From this first cut, we created two rectangular partitions, each of which was bounded by the edge of the field on three sides, and the cut on the other. We could guarantee that a hill was on one side of the cut because the upward slope to a hill could neither escape back across the cut (it was already higher than every point in the cut), nor could it escape across the other sides because, well, they were the end of the world. Let's continue with some degree of caution.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
198 197 196 195 194 193 192 191 190 189 188 187 186 185 16
199 52 53 54 55 56 57 58 59 60 61 62 63 184 17
200 51 154 153 152 151 150 149 148 147 146 145 64 183 18
201 50 155 88 89 90 91 92 93 94 95 144 65 182 19
202 49 156 87 126 125 124 123 122 121 96 143 66 181 20
203 48 157 86 127 108 109 110 111 120 97 142 67 180 21
204 47 158 85 128 107 114 113 112 119 98 141 68 179 22
205 46 159 84 129 106 115 116 117 118 99 140 69 178 23
206 45 160 83 130 105 104 103 102 101 100 139 70 177 24
207 44 161 82 131 132 133 134 135 136 137 138 71 176 25
208 43 162 81 80 79 78 77 76 75 74 73 72 175 26
209 42 163 164 165 166 167 168 169 170 171 172 173 174 27
210 41 40 39 38 37 36 35 34 33 32 31 30 29 28
211 212 213 214 215 216 217 218 219 220 221 222 223 224 225
So we make a new cut on the right. This time the highest value cell in the cut is 179, near the right. Now, the interesting thing here is that this is lower than our previous high-point. So rather than measuring its neighbours, we can instead observe that we have "boxed in" our hill. We know that somewhere uphill from cell 219 there's a hill, and we know that the upward slope to it can cross neither of our boundary lines, so it must be somewhere in the bottom-right.
If instead our new cut had found a cell higher than our maximum, then we could have again scanned its neighbours and either discovered it to be a hill or proven that a hill must lie on one side of the cut.
So, it sounds like we have a strategy to find a hill. How many scans might it require in the worst case? Well, we could have a 1000×1000 grid, and we may need to keep subdividing it until we get down to a single cell. Our first cut will be 1000 cells, our second cut will be ≤500 cells, our third cut will be ≤500 cells, our fourth cut ≤250, and so on, every second cut being half the length of the one before. This works out to a bit less than 3000 cells. We might have to make up to 17 (I think?) cuts, and on each one we might have to check two neighbours, giving an extra 34 cells to scan. So we do manage to come in just under our 3050 budget in the worst case.
So, I tried to code up this solution in Pascal, but either there's a flaw in the strategy or I made a mistake in the coding, because when I submitted it I was told it passed only 4 of 5 tests, and failed the remaining one by giving a wrong answer (as opposed to using too many scans). Of course, since the test data remains secret it's hard to figure out where it's going wrong. I think I'll need to build a proper test runner that can feed it the results of the laser scans, since at the moment I'm limited to testing it by typing in altitudes by hand as it asks for them.
So you have a grid, up to 1000x1000 cells, and every cell has a distinct positive altitude. You can query the altitude of up to 3050 cells ("scanning" them with your laser) and you have to discover and report the location of a cell that is higher than its four neighbours (a "hill").
The naive solution would be to start in any cell and scan its neighbours. As soon as you find a higher one, switch to it and repeat. If you find no higher one you have discovered a hill and can stop. However, this is not guaranteed to find a hill within 3050 scans. If that's not obvious, consider this pathological case:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
198 197 196 195 194 193 192 191 190 189 188 187 186 185 16
199 52 53 54 55 56 57 58 59 60 61 62 63 184 17
200 51 154 153 152 151 150 149 148 147 146 145 64 183 18
201 50 155 88 89 90 91 92 93 94 95 144 65 182 19
202 49 156 87 126 125 124 123 122 121 96 143 66 181 20
203 48 157 86 127 108 109 110 111 120 97 142 67 180 21
204 47 158 85 128 107 114 113 112 119 98 141 68 179 22
205 46 159 84 129 106 115 116 117 118 99 140 69 178 23
206 45 160 83 130 105 104 103 102 101 100 139 70 177 24
207 44 161 82 131 132 133 134 135 136 137 138 71 176 25
208 43 162 81 80 79 78 77 76 75 74 73 72 175 26
209 42 163 164 165 166 167 168 169 170 171 172 173 174 27
210 41 40 39 38 37 36 35 34 33 32 31 30 29 28
211 212 213 214 215 216 217 218 219 220 221 222 223 224 225
Here there's only one "hill": the 225 cell in the bottom-right. Suppose you start searching at 114 near the centre. Its highest neighbour is 115. 115's highest neighbour is 116. And so on, round and round the spiral, until you eventually reach the hill. On a 1000×1000 cell grid you could need many, many more scans than the 3050 allowed.
However, we can do better. Let's try subdivision. (Credit to my colleague Luke who came up with a lot of the ideas here.) We'll start by doing a sweep that cuts the grid in two. We can afford that - it takes 1000 of our 3050 budget on a full-sized grid - so long as we don't plan to make many more of this length! Here I've highlighted the sweep:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
198 197 196 195 194 193 192 191 190 189 188 187 186 185 16
199 52 53 54 55 56 57 58 59 60 61 62 63 184 17
200 51 154 153 152 151 150 149 148 147 146 145 64 183 18
201 50 155 88 89 90 91 92 93 94 95 144 65 182 19
202 49 156 87 126 125 124 123 122 121 96 143 66 181 20
203 48 157 86 127 108 109 110 111 120 97 142 67 180 21
204 47 158 85 128 107 114 113 112 119 98 141 68 179 22
205 46 159 84 129 106 115 116 117 118 99 140 69 178 23
206 45 160 83 130 105 104 103 102 101 100 139 70 177 24
207 44 161 82 131 132 133 134 135 136 137 138 71 176 25
208 43 162 81 80 79 78 77 76 75 74 73 72 175 26
209 42 163 164 165 166 167 168 169 170 171 172 173 174 27
210 41 40 39 38 37 36 35 34 33 32 31 30 29 28
211 212 213 214 215 216 217 218 219 220 221 222 223 224 225
Now, in that sweep, one cell must be higher than all the others. That's easy to remember. In this case, 218 is our highest value. Let's scan the cells on either side of it. Now, either at least one of its neighbours is higher than it, or neither is. If neither is higher, then it must be a hill, and we can stop! If one is higher, then we have discovered something important: there must be a hill somewhere on that side of the divide. We know this because every cell in the dividing line is lower than this neighbouring cell; the upward path from the neighbouring cell cannot wander back across the dividing line, so it must terminate in a hill somewhere on that side. In this case, we find that cell 219 is higher, so we know there must be a hill somewhere on the right.
Now, can we repeat this subdivison? It gets a bit trickier. From this first cut, we created two rectangular partitions, each of which was bounded by the edge of the field on three sides, and the cut on the other. We could guarantee that a hill was on one side of the cut because the upward slope to a hill could neither escape back across the cut (it was already higher than every point in the cut), nor could it escape across the other sides because, well, they were the end of the world. Let's continue with some degree of caution.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
198 197 196 195 194 193 192 191 190 189 188 187 186 185 16
199 52 53 54 55 56 57 58 59 60 61 62 63 184 17
200 51 154 153 152 151 150 149 148 147 146 145 64 183 18
201 50 155 88 89 90 91 92 93 94 95 144 65 182 19
202 49 156 87 126 125 124 123 122 121 96 143 66 181 20
203 48 157 86 127 108 109 110 111 120 97 142 67 180 21
204 47 158 85 128 107 114 113 112 119 98 141 68 179 22
205 46 159 84 129 106 115 116 117 118 99 140 69 178 23
206 45 160 83 130 105 104 103 102 101 100 139 70 177 24
207 44 161 82 131 132 133 134 135 136 137 138 71 176 25
208 43 162 81 80 79 78 77 76 75 74 73 72 175 26
209 42 163 164 165 166 167 168 169 170 171 172 173 174 27
210 41 40 39 38 37 36 35 34 33 32 31 30 29 28
211 212 213 214 215 216 217 218 219 220 221 222 223 224 225
So we make a new cut on the right. This time the highest value cell in the cut is 179, near the right. Now, the interesting thing here is that this is lower than our previous high-point. So rather than measuring its neighbours, we can instead observe that we have "boxed in" our hill. We know that somewhere uphill from cell 219 there's a hill, and we know that the upward slope to it can cross neither of our boundary lines, so it must be somewhere in the bottom-right.
If instead our new cut had found a cell higher than our maximum, then we could have again scanned its neighbours and either discovered it to be a hill or proven that a hill must lie on one side of the cut.
So, it sounds like we have a strategy to find a hill. How many scans might it require in the worst case? Well, we could have a 1000×1000 grid, and we may need to keep subdividing it until we get down to a single cell. Our first cut will be 1000 cells, our second cut will be ≤500 cells, our third cut will be ≤500 cells, our fourth cut ≤250, and so on, every second cut being half the length of the one before. This works out to a bit less than 3000 cells. We might have to make up to 17 (I think?) cuts, and on each one we might have to check two neighbours, giving an extra 34 cells to scan. So we do manage to come in just under our 3050 budget in the worst case.
So, I tried to code up this solution in Pascal, but either there's a flaw in the strategy or I made a mistake in the coding, because when I submitted it I was told it passed only 4 of 5 tests, and failed the remaining one by giving a wrong answer (as opposed to using too many scans). Of course, since the test data remains secret it's hard to figure out where it's going wrong. I think I'll need to build a proper test runner that can feed it the results of the laser scans, since at the moment I'm limited to testing it by typing in altitudes by hand as it asks for them.