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(n²) 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 10¹⁴.

Thanks for reading, and see you next week!

This week in competitive programming

There were no contests on weekdays this week, but the weekend was rather busy. On Saturday, the last online round of the Kotlin Challenge took place, top 25 qualifying to the onsite finals in St. Petersburg (problems in Russian, results mostly in Russian, top 5 on the left). Problem B was of the "constructive" type, which is quickly becoming popular in today's contests: instead of optimizing some function, you were asked to provide any answer that fits a given constrainst, with the constraint given with a lot of leeway, allowing many completely different answers. The problem went as follows: you need to print any string with length N consisting of the first K lowercase English letters such that no letter is repeated twice consecutively and no substring is repeated three times consecutively. N is up to 5000, K is up to 26. What approach have you found?

Overlapping with the Kotlin challenge was TopCoder SRM 609 (problems, results, top 5 on the left). I couldn't solve it because of the overlap, so I can't tell you much about the problems. However, it's amazing that Gassa could both qualify for the onsite in Kotlin Challenge and place in top 5 in the SRM - great job Ivan!

On Sunday, the Grand Prix of Udmurtia of the Open Cup continued the run of three consecutive Grand Prix weekends (results, top 5 on the left). The contest was full with problems that nobody could solve, and one of them (problem F) went as follows: you need to write a program that does the same as the given black box. The black box takes a string and outputs a string, there are several examples given, and there's a special problem Q that is the black box: you can send inputs there and learn about the outputs. Not many teams attempted to solve this problem during the contest, but it might be a very interesting task in the upsolving.

And finally, late on Sunday Codeforces ran Rockethon 2014 (problems, results, top 5 on the left). I was too tired to take part, so I can only admire tourist (yet again :)) who managed to win the first place both in the Open Cup and in this contest.

Thanks for reading, and see you next week!

This week in competitive programming

Before we dive into this week, let's finish the last week's review. Late last Sunday, SnarkNews Winter Series 2014 Round 5 came to an end (results, top 5 on the left). Unlike last round, submitting problems blindly turned out the be the best strategy in this round, and Egor easily won using it. One of the nicer problems was: you are given three bitstrings (strings of zeroes and ones) of length 100000. How many bitstrings have the same Hamming distance to all three given bitstrings (you need to output the answer modulo 10⁹+7)?

With this round, the entire Winter Series came to an end (results, top 5 on the left). tourist won with a big margin, mostly due to his flawless all-blind performances in the first two rounds.

The week proper started with two rounds on Monday. TopCoder SRM 607 (problems, results, my screencast, top 5 on the left) featured a very difficult hard problem, which nobody could solve, so everything came down to challenges. My strategy for the challenge phase was to look for incorrect DPs in the second problem, more specifically, I looked for DPs that don't seem to have "number of nested segments" as a DP parameter that can go up to 5000. This worked to find three incorrect solutions quickly, but it also had two false positives: two solutions had this parameter only go to 3000, but it turned out that they only stored the parameter divided by 10 (since the remainder of its division by 10 was reconstructable).

After a couple hours' break, Codeforces Round 228 gathered most of the same crowd (problems, results, my screencast, top 5 on the left). And exactly like in the earlier TopCoder round, the hardest problem was not solved, although this time several contestants came close, and the match results were decided on challenges. I couldn't get any, so I couldn't get into the top 5. The round had excellent problems, and I encourage you to try solving them all. Let me highlight problem D: given an integer k up to 10⁹, how many sets of non-negative integers exist such that all numbers in the set are at most k, and that for any two numbers in the set their bitwise xor is also in the set (you need to output the answer modulo 10⁹+7)?

On Thursday, the Petrozavodsk winter camp for ACM ICPC teams preparing for the World Finals came to an end (results, top 5 on the left). This amazing event is not just one contest, but rather nine contests spread over the past two weeks, together with lectures and winter Karelia sightseeing. tourist won the first place in the overall standings, ahead of the three three-person teams who will take part in the World Finals in June, but SPb SU 4 remain the main contender for the ICPC championship.

On Friday, TopCoder SRM 608 (problems, results, top 5 on the left) continued tomek's return to active participation in programming contests - and he's made it into the top 5 for the third SRM in a row. The medium difficulty problem asked an unusual question. We're given a directed graph, and the number of walks of length n in this graph is denoted as f(n). What is the smallest non-negative integer k such that f(n)=O(n^k) (big-O is explained in detail in Wikipedia)?

On Saturday, the Challenge 24 Electronic Contest (problems, results, top 5 on the left) has selected 27 teams that will join the last year's top 3 in Budapest for the actual 24-hour competition. Since my team has already qualified via placing in top 3 last year, we didn't participate. Psyho, one of the winning team's members, has shared his impressions on his blog. Bruce Merry did the same.

And finally, on Sunday, the Nothern Grand Prix of the Open Cup (results, top 5 on the left) featured a problemset from Andrew Stankevich. The problems are not published yet, and I don't want to spoil the contest for those who didn't see those problems yet, so I won't go into detail about them - I'll just say that the problemset was great, interesting and diverse.

Thanks for reading through this very long post (did you? :)), and see you next week!

P.S. I realize that I've been only writing about contest results and interesting problem statements lately, and didn't have time to explain problem solutions. I hope to get back to explaining solutions in the near future!

This week in competitive programming

On Thursday, TopCoder SRM 606 has woken the European competitors very early in the morning (problems, results, top 5 on the left). I've slept through it, so I can't tell you much about the problems.

On Sunday, the Open Cup has resumed after the holiday break with the Grand Prix of Saratov (problems, results, top 5 on the left). The round had several nice problems requiring some creative thinking, but here's one that's easy to explain and not so easy to solve (you can find the full problem statement using the above link, this is problem G): you are given an R times C grid, where both R and C are powers of two, at least 4 and at most 256. Since R and C are powers of two, so is RC, let's say RC=2^N. You need to place some subset of the first N letters of the alphabet into each cell of the grid in such a way that all subsets are distinct (there's just enough subsets for all cells), and that for each letter, the figure formed by the cells containing that letter is 4-connected and "without holes" (its boundary should be a simple non-self-touching polygon).

Here's an example for a 4 times 4 grid:

AB..	ABCD	ABC.	A.C.
AB.D	A.CD	A..D	A...
.BCD	.BC.	.B.D	.B..
..CD	..C.	...D	....

Here's the figure formed by letter D in that grid - it's connected and without holes. The same is true for all other letters:
.D..
DDD.
D.D.
D.D.

Good luck with solving this problem, and see you next week!