Unusually for TopCoder there was quite some time to spare at the end of the coding phase, and thus one had the opportunity to prepare for the challenge phase thoroughly. The required mindset is quite similar to the one of the problemsetter: need to come up with testcases that would fail various potential incorrect solutions, and ideally with ones that are likely to fail even unforeseen incorrect solutions, too.
Here's the approach I've chosen this time for the easy problem (you can see it in more detail, but a bit slowly, on the screencast): let's construct random testcases that have many parts, and yet exactly one way to group the parts to achieve the maximum score. An incorrect solution in this problem is likely to be some kind of greedy instead of dynamic programming, and having exactly one solution makes sure that there are many more ways for the greedy to make mistakes. Having the testcase random instead of manually crafted ensures that it doesn't become too well-structured, as greedy solutions might actually be correct for well-structured cases.
More precisely, I've started with just three numbers which would be the xors of the groups in the final answer, and then repeatedly tried to replace any number x with (x xor y, y), where y is a random number, checked if there's still just one way to achieve the maximum, and if yes, then kept the replacement. I've generated a few cases using this approach, and picked the one with more components, and without components that looked too simple (powers of 2).
When I opened a greedy solution during the challenge phase (screencast pointer), I could then successfully use the testcase prepared in advance without crafting a case specifically against that solution. My other challenge (screencast pointer) was a bit more straightforward :)
How did you prepare for the challenge phase this time? Or maybe you remember a useful challenge phase preparation trick you've used earlier?
0 komentar:
Post a Comment