Re: 10259 - Hippity Hopscotch
Posted: Tue Oct 21, 2008 6:09 am
This problem isn't entirely straightforward, but not that hard either. At first I got TLE when I use BFS starting from (0, 0) to update the maxPennies of each square. Then I leveraged the sorting idea in the code above by first sorting the squares based on numPennies on it, and then update the maxPennies of the nearby squares accordingly. This got me several WA until I made it so that you only perform the operation above for squares that are reachable from (0, 0).
For instance, suppose this is the input.
1
2 1
3 2
5 4
We have numPennies = 3 for (0,0). Even though there's a 4, we don't want to update the maxPennies of the nearby squares because this square containing 4 pennies is never reachable from (0, 0). Similarly you don't want to update the square that contains 2 pennies either because you start off with a square containing 3 pennies already. So you need to accomodate these when you do the updating after you sorted.
For instance, suppose this is the input.
1
2 1
3 2
5 4
We have numPennies = 3 for (0,0). Even though there's a 4, we don't want to update the maxPennies of the nearby squares because this square containing 4 pennies is never reachable from (0, 0). Similarly you don't want to update the square that contains 2 pennies either because you start off with a square containing 3 pennies already. So you need to accomodate these when you do the updating after you sorted.