Sunday, January 4, 2015

This week in competitive programming

Codeforces Good Bye 2014 round wrapped up the year on Tuesday (problems, results, top 5 on the left, my screencast). In following with the spirit of 2014, tourist claimed the top spot - and in fact the entire top 3 are the top 3 by rating. My hopes to catch Gennady were at the highest level at this moment in the screencast: I've finished writing problem F at 1:06 into the contest, and the scoreboard showed that Gennady has not yet submitted it. Just a few seconds later, it turned out that my solution didn't pass pretests and I had to implement a stress-test to find the bug, whereas the scoreboard was just refreshing very slowly and Gennady has in fact submitted 10 minutes ago ;)

The New Year started together with the New Year Prime Contest (problemsmy description from 2013), as usual consisting of problems that were offered at Russian ACM ICPC-style competitions in 2014 but have NOT been solved by anybody. The contest will be running for another week, so you can still try your luck at the toughest problems of 2014: login link, you need an Open Cup login to participate. If you don't have one, you can email new.opencup[guess what]gmail[guess what]com asking for one. Here are the current standings.

Problem 43 "Nanobugs" is mostly a mathematical puzzle: you have n (at least 20 and at most 50) coins, some of which are fake. Your friend knows that either a or a+1 coins are fake (a is between 1 and 3, and is given). You know the fake coins exactly, but you don't want to reveal that knowledge to your friend. Instead you want to prove your knowledge to your friend by proving that there are exactly x (either a or a+1) fake coins without revealing the status of any particular coin - neither fake nor real. The only method you can use for your proof is a very limited subset equality testing device: it takes two non-interesecting subsets of coins of the same size, and tells whether both subsets have the same amount of fake coins or not. Can you see the way to use comparisons to prove the number of fake coins without revealing any particular fake or real coin?

Spending winter vacation doing what you like the most, together with people who share your interests, is also the central idea of the Summer Informatics School in Winter. Summer Informatics School itself (website in Russian) is organized during the summer school break, offering high school students to continue their education in algorithms and programming for 3 weeks, each day filled with 4 hours of studying and endless hours of fun events and sports together with other high school students who enjoy learning about algorithms. In addition to learning, the students find new friends and form a new community that is active well beyond the 3 weeks of school itself, and past students often become teachers later. I was never a student at this school, but I was a teacher three times - the picture on the left is from 2004, illustrating that I was judging a soccer game in addition to teaching algorithms. In the years past the school has been growing tremendously, and these days more than half of the winners of the Russian Olympiad in Informatics have a Summer Informatics School participant t-shirt.

The winter session, lasting for just 10 days since the winter school break is short, is happening for the seventh New Year in a row - it begins in late December and lasts until the second week of January. It gathers the same students who have participated in the preceding summer session, and it keeps the same study-and-have-fun-together format, but with a winter twist: many outdoor sports are replaced with museum visits and sightseeing, although this year cross-country skiing and ice skating are also covered. And of course, the New Year night is always something special!

I'm no longer participating in this school, but I still admire both the teachers and the students for the amazing community they have built - congratulations to all of you, and have fun in the remaining days of ЛКШ.Зима!

Also, since the post is very long, I'd like to reiterate that I want to improve my English writing, and thus will appreciate if you bring up any issues you notice with my English in the comments below. Thanks in advance!

No comments:

Post a Comment