The official analysis discusses this approach, briefly: > We might consider using backtracking solutions. One possible concern is > that these solutions, whether they are breadth-first or depth-first, > proceed in an orderly fashion that might be more likely to leave us > with tough "endgames" in which the constraints are impossible.
To elaborate on this a bit: As the grid size increases, the size of the search tree grows extremely quickly. For an NxN grid, there are (N^2)! possible paths to be checked. Your only hope is that the algorithm will quickly find a solution that is _almost_ correct, and only have to do a small amount of backtracking. But this is not guaranteed. If your algorithm makes a bad decision early on, it can end up in a "dead end" node which is fairly high in the tree -- meaning it has an enormous number of descendants -- but doesn't lead to any valid solutions. Once it gets to this point, the algorithm will keep exploring this subtree before exploring any other possibilities, causing it to run out of time. You might not run into this problem all the time, but there are 100 test cases in the test set, and it only takes one bad one to trigger a TLE. The randomized algorithm described in the official analysis avoids this problem, by taking advantage of the fact that even though there are lots of dead ends in the search tree, there are also a large number of different valid solutions. So if you hit a dead end, it makes more sense to just start over with a different random path, instead of spending an unknown amount of time backtracking. In practice, this almost always succeeds after a small number of attempts; for 7x7 grids and above, each attempt has a >50% chance of success. During a contest, it's probably not worth spending the time to rigorously prove that this randomized approach will _always_ succeed in a reasonable amount of time. But it's easier to show that _if_ the code succeeds quickly when you test locally against all 400 possible inputs, then the probability of it making enough unlucky decisions to fail while being judged is infinitesimally small. So rather than trying to prove that it works, it's easier to just code it up and see. -- David -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/b59cec01-b93f-4430-b8a0-32c982c18608%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
