Tuesday, February 25, 2014

This week in competitive programming

On Tuesday, Codeforces ran its 230th round (problems, results, top 5 on the left). The problems were quite technical and not as exciting, but they can still provide valuable practice should you need some.

On Friday, Facebook has gathered top 25 (well, it turned out to be top 23) contestants in its headquarters in Menlo Park to find the next owner of a large block of concrete also known as the Hacker Cup (results, top 5 on the left). As I understood, four problems requiring advanced data structures to be solved in O(n*polylog(n)) were given, but some contestants managed to squeeze through with optimized O(n2) solutions. The most successful use of this unexpected approach was by second-placed Tomek who used it in 3 problems out of 4 - but still nothing could stop Gennady from winning. Congratulations!

Open Cup is becoming a weekly tradition this winter, with fourth consecutive round this Sunday. Among other interesting problems, here's one that is mathematically brilliant in my opinion: consider a n times m grid. We can fill it with numbers from 1 to n*m in row-major order, or in column-major order. These two grids of numbers define a permutation of numbers between 1 and n*m. How many cycles does it have? n*m is up to 1014.

Thanks for reading, and see you next week!

No comments:

Post a Comment