Friday, January 3, 2020

A 4-point week

With TCO19 over, the qualification for TCO20 is well underway, and TopCoder SRM 771 was a part of that during the Nov 25 - Dec 1 week (problems, results, top 5 on the left, my screencast, analysis). Tourist did all he can to bounce back from a resubmit on the 1000-pointer, found 175 challenge points but was just 2 points short to overtake majk with his wonderful 800+-point solution :) Congratulations to both!

I was implementing the solution described in this comment, but an internal assertion kept failing on one of the samples. With just seconds left in the round I've removed the assertion and submitted, but of course it still failed the system tests. It turns out the idea was incorrect as well, but the system tests would not have caught that, so one could say I was close :) Luckily for me, many others have failed the system tests and I barely climbed into the top 10, so both myself and tourist gathered 4 points for the TCO20 qualification standings.

On the ICPC side, the Northern Eurasia Finals took place in St. Petersburg, Barnaul, Tbilisi and Almaty on Sunday (problems, results, top 5 on the left, broadcast, online mirror resultsanalysis). The strong favorite team NNSU Almost Retired did well but team SPbSU 25 was a bit faster and won, both teams at 10 problems while others got at most 9. Congratulations to both teams!

In the online mirror, three teams placed above them but as I understand none of those are active/eligible for ICPC. Team Cafe Mountain in the 7th place actually is a current ICPC team competing for Seoul NU (please correct me if I'm wrong!)

I have set the interactive problem I for this round, which went like this: there are 2n elements (n>=3). We can compare any two elements, and there are no equal ones, so one will compare bigger than the other. Our goal is to make such set of comparisons that uniquely determines the n biggest elements out of 2n, but not the ordering of those n elements. In other words, there must be at least two possible orderings of those n elements that are consistent with the outcomes of comparisons. Can you come up with an algorithm with a requirement that it does not do something? :)

Note that this would not be possible for n=2, as it might happen that the first two elements we try to compare are the two biggest elements, and thus we would learn a unique order for them.

Thanks for reading, and check back for more!


  1. Twos of Gifted Infants is retired, maroon_rk is only remaining but won't attend to the next WF.