Sunday, January 20, 2019

An anti-library week

TopCoder held two SRMs this week. SRM 746 took place on Tuesday (problems, results, top 5 on the left, my screencast, analysis). Once again the topic of floating-point precision took center stage: 27 solutions were submitted for the hard problem, many relying on floating-point and/or ternary search, but only 5 passed, all computing the answer exactly and using either arbitrary-length integers, arbitrary-length floating point, or int128.

I've already made this point in the Codeforces discussion thread, but let me repeat here: the super high precision requirement had a side effect of essentially penalizing the contestants that had a prewritten 3D geometry library: using the library as-is would fail because of precision issues, and adapting a set of interconnected methods from floating-point to big integers is actually much more time-consuming than figuring out the relatively simple required computation from scratch and implementing it. Looking at the five accepted solutions, four or maybe all five seem to be written from scratch.

This has also provided for an unusual challenge phase, with 9 out of 26 successful challenges coming on the hardest problem. In most cases ending up in room 1 is a bad sign for the challenge phase (I believe the rooms are sorted by decreasing average rating, or something like that), but here it was exactly the opposite :)

SRM 747 followed on Saturday (problems, results, top 5 on the left, my screencast). The relatively standard medium and hard meant that the first place was decided during the challenge phase, and the easy problem seemed to have been designed specifically to make the challenge phase more interesting: it was a constructive problem with such loose requirements that a lot of solutions worked, and even more solutions passed the sample cases. In fact, one could almost say that it was possible to pass the samples by accident :) However, challenging those solutions was also not trivial, as they might pass a challenge case by accident just as well.

Thanks for reading, and check back next week!

No comments:

Post a Comment