A London week

TopCoder SRM 683 was the first round of this week (problems, results, top 5 on the left). Two successful solutions for the hard problem seems like an unusually high number these days :) jiry_2 has won with a big margin because of being the only one to solve all three - congratulations!

On Thursday, 25 finalists gathered in London for the Facebook Hacker Cup 2016 Onsite Final Round (problems with Facebook login, results, top 5 on the left). The round contained 6 solvable problems, but with quite a few tricks and extremely simple example cases, so the room for failure was huge. Well done to Makoto on avoiding the failures and winning convincingly!

Bruce, who was one of the contestants to solve all 6 problems, only to end up with 0 accepted solutions, explains what happened to his solutions here, and what are the correct approaches here. Let me cover my part of the failure story:

In the problem "Boomerang Crews", I've made a mistake that comes up again and again for me: tried to use a TreeSet as a multiset. In the problem "RNG", I've checked if a vertex has any outgoing edges before actually reading the edges from the input - so all vertices got marked as "no outgoing edges". Finally, in problem "Grundy Graph" my solution was a bit further from the correct one - I forgot to add the reverse edges, and to check if one Bob's vertex is reachable from another.

Failing like this in an important round naturally makes one think about better ways to avoid such mistakes. Bruce mentions that one of his failures was due to an integer overflow, and I've protected myself against that via CHelper plugin's ability to use Cojac library to detect integer overflows in Java at runtime. However, one wonders whether any other bugs mentioned above by myself or by Bruce are preventable by building better tools?

One relatively straightforward idea I had was to define a TreeSet class in my library which raises an exception when trying to add duplicates, and tune IDEA's auto-completion to offer it above the system one. In most cases where ignoring duplicates is a good thing, a HashSet is a more natural fit, and adding duplicates to a TreeSet seems to be a mistake more often than not.

Please share your suggestions!

Tweet