A testcase preparation week

CodeChef SnackDown 2016 Final Round in Mumbai has continued the run of two-person team contests this week (problems, results, top 5 on the left). The winning team was 50% the same as last week - congratulations Gennady and Boris!

TopCoder SRM 694 followed a few hours later (problems, results, top 5 on the left, my screencast). The problems were quite standard, and jcvb and xudyh showed great mastery of flow algorithms to solve the 900 very fast and keep the battle for the first place just between themselves. In the end jcvb emerged victorious by a mere 0.09 points - congratulations!

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?

Codeforces held the online mirror of the 2016 Helvetic Coding Contest on Sunday (problems, results, top 5 on the left). The onsite version took place quite a while ago, and had slightly different problemset and rules. Congratulations to team Zg on earning the victory with more than an hour to spare, and on coming head and shoulders ahead of all onsite teams as well!

Thanks for reading, and see you next week!