Surveillance: Difference between revisions
imported>Kmk21 Created page with "This may seem like minimum set cover...which is NP complete...but we have extra state, the fact that the sets are all continuous. Pick a random set, and then select the overl..." |
imported>Kmk21 No edit summary |
||
| Line 1: | Line 1: | ||
This may seem like minimum set cover...which is NP complete...but we have extra state, the fact that the sets are all continuous. | This may seem like minimum set cover...which is NP complete...but we have extra state, the fact that the sets are all continuous. | ||
Pick a random set, and then select the overlapping set which goes as far as possible further around the circle. | Pick a random set, and then select the overlapping set which goes as far as possible further around the circle. Keep track of the segments you select in order, and maintain a pointer into the list keeping track of the furthest back segment needed such that the segments between it and the head of the list form a full cover. As you add to the front of the list, increment the trailing pointer, and keep track of the minimum. Whenever we hit some minimum cover (from and to the same segments), terminate. This is guaranteed to happen in O(N). | ||
There is also some hacky way of looping around once forward, and then once backward...seems like it should work. | |||
Computing the mapping of which segment to choose next seems tricky, it seems like we should be able to do it in constant or nlogn time with a sort of caterpillar walk, but not sure I can work out the exact details right now. | |||
[[Category:ICPC Problems]] | [[Category:ICPC Problems]] | ||
[[Category:Finals2014]] | [[Category:Finals2014]] | ||
[[Category:Greedy]] | [[Category:Greedy]] | ||
[[Category:Caterpillar Walk]] | |||
Latest revision as of 19:07, 25 August 2016
This may seem like minimum set cover...which is NP complete...but we have extra state, the fact that the sets are all continuous.
Pick a random set, and then select the overlapping set which goes as far as possible further around the circle. Keep track of the segments you select in order, and maintain a pointer into the list keeping track of the furthest back segment needed such that the segments between it and the head of the list form a full cover. As you add to the front of the list, increment the trailing pointer, and keep track of the minimum. Whenever we hit some minimum cover (from and to the same segments), terminate. This is guaranteed to happen in O(N).
There is also some hacky way of looping around once forward, and then once backward...seems like it should work.
Computing the mapping of which segment to choose next seems tricky, it seems like we should be able to do it in constant or nlogn time with a sort of caterpillar walk, but not sure I can work out the exact details right now.