This week in competitive programming

The week started with Codeforces Round 225 on Monday (problems, results, top 5 on the left). I didn't take part, so I can't tell much about the problems; SPb SU 4 have reminded everybody that they're the team to beat at this year's ICPC World Finals, taking the first and the third place in this contest.

On Tuesday, TopCoder SRM 605 took place (problems, results, top 5 on the left). I didn't take part as well; the winner, semiexp, is now seventh in the world; in another round of ICPC World Finals news, Lidia Perovskaya comments in my earlier post that very strong University of Tokyo team that includes the SRM winner semiexp and two-time TCO winner rng_58 is not going to the World Finals this year.

Finally, two rounds of SnarkNews Winter Series have ended this week. Round 3 (results, top 5 on the left) featured, among others, the following nice problem. You are given a string with 10000 characters. Consider all 2¹⁰⁰⁰⁰ ways to pick a subset of its characters. Some of them result in different strings, some result in equal strings. For each distinct string that we can obtain that way, we count the number of ways to obtain it, and need to find the sum of squares of those counts modulo a large prime. The problem required a beautiful insight to solve, and the only contestant to get it was tourist.

Round 4 (results, top 5 on the left) reiterated on a somewhat well-known but still beautiful idea in the following knapsack problem: you are given 100 'small' numbers, each up to 10⁵, and 1000 'large' numbers, each at least 10¹⁰ (and at most 10¹⁷). For each large number, you need to find the minimum amount of small numbers (each small number may be used more than once, each usage counts) that sums to this large number. I don't know how to solve this problem fast enough if large numbers were, say, around 10⁸, but I've solved it when they're at least 10¹⁰ - can you?

Thanks for reading, and see you next week!

This week in competitive programming

There were no Codeforces or TopCoder rounds this week. However, SnarkNews Winter Series 2014 Round 2 has finished on Wendesday (top 5 on the left, full results), so let me share a nice problem from that round. We want to assign integers starting from 2 to (an infinite amount of) users and groups of users of our service in such a way that:

• each user is assigned a different positive integer number.
• each group (set) of at least two users is assigned a positive integer number that is different for all groups and is different from all user's numbers.
• each integer more than one is assigned to either a user or a group.
• the number for each group is the product of the numbers of the users in that group.

The problem then asked to find the users belonging to the group with the given number. It did not claim this explicitly, but it implicitly relied on the fact that there's exactly one way to choose which numbers belong to users and which belong to groups so that all above conditions are satisfied. Can you figure it out?

Thanks for reading, and see you next week!

This week in competitive programming

This week TopCoder came back from holidays with two SRMs. SRM 603 (problems, results, top 5 on the left), on Monday, featured a problem requiring a Fast Fourier Transformation implementation. It's funny that searching for [topcoder fast fourier transformation] brings up an old post from this very blog. A problem requiring FFT appeared on TopCoder almost 5 years ago, and I was regretting that I don't have a library of prewritten algorithms that has FFT in it. Fast forward 5 years, and the feeling is exactly the same :) Given that TopCoder Open now allows libraries of prewritten algorithms, it makes more sense to start assembling one.

SRM 604 (problems, results, my screencast, top 5 on the left), on Saturday, featured a nice dynamic programming on trees problem: you are given a tree with some vertices having a token in them, and some not. You need to move the tokens in such a way that they occupy a connected set of (different) vertices, and the total distance travelled by tokens is as small as possible (full problem statement). The solution to this problem can be very tedious, but it can also be simple if you make an important observation.

Moreover, intuitively it feels that this problem should be solvable greedily. Any ideas?

On Friday, the first round of SnarkNews Winter Series 2014 has ended (see my old post for details about this contest) (results, my screencast, top 5 on the left). The rules have changed since that post, though - the current rules are available under TCM/Time heading at the Yandex.Algorithm page. Short version is: when you submit a problem, you can choose whether you want instant feedback or not, and you get a penatly time bonus if you don't require instant feedback (but of course your solution can fail in the end and then you'll get nothing for this problem). For example, in the top 5 shown on the left, tourist sent all 6 problems without feedback, Egor sent three problems with feedback (all were accepted on the first attempt, so he could've send all six without feedback and get a better result) and three without, and so on.

Such rules add an extra dimension to the competition, increasing randomness, but not in a bad way, as it's still rewarding good strategies.

Finally, on Sunday, Codeforces Round 223 took place (problems, results, my screencast, top 5 on the left). Problem C was nice because it asked a very simple-looking question, yet answering it required some creative thinking. Here's how it went: for a string consisting of opening and closing parentheses, we can find the smallest number of characters to be removed from the string such that the remains are a correct parentheses sequence. Now you're given a string with a million parentheses, and need to find the above number for hundred thousand given substrings of that string.

Thanks for reading, and see you next week!

P.S. Comments and suggestions on improving the weekly digest are welcome.

This week in competitive programming

Happy New Year!

Last week was mostly holidays, but it still featured a programming competition. Codeforces ran its last round of 2013 on Monday (problems, results, my screencast, top 5 on the left). The problems were not bad but not too exciting in my opinion, but in the aftermath of the round a nice formula for creating nasty problems was born :)

Some more exciting problems are still open to be solved at New Year's Prime Contest (see my last year's description for details). Here's this year's link (Russian), PDF with problems, and the current standings. Problem 5 is still not solved by anybody, although its problem statement is not very clear, which might explain why nobody tries to solve it. I've particularly enjoyed problem 2, which goes as follows: you are given a 2000x2000 matrix of zeroes and ones, and need to find the number of permutations of its columns that result in a matrix where ones in each row are consecutive (see the PDF for details). Squeezing it into the time limit might not be too exciting, but coming up with any polynomial solution certainly is. I'm also the author of problem 31.

And finally, I want to share a picture of a New Year's gift from my dear wife Irina: it's a bed cover made from old T-shirts, mostly from programming contests. This might be a bit too personal for this blog, but I hope it's enough of a programming contest artifact :)

Thanks for reading, and see you next week!

This week in competitive programming

2117 programmers took part in Codeforces Round 221 on Tuesday (top 5 on the left). I didn't, so I can simply share the links to problems and results, and congratulate the winner Touma_Kazusa for whom this was just the third Codeforces round!

2075 programmers took part in TopCoder SRM 602 on Saturday (problems, results, my screencast, top 5 on the left). The 250 problem was simple dynamic programming, the 550 was a tricky case study with simple data structures, and 1000 was a mostly mathematical problem to be solved on paper. The 550 possessed an interesting property: despite being a very tricky case study when N is up to 100000, it allowed a very simple solution when N is around 5-10 that can be implemented in just a couple of minutes. That's why after submitting it, I've implemented that simple solution and compared it against my solution on thousands of random testcases. It helped discover a silly bug and I had to resubmit losing quite a few points, but I would've lost much more had my solution failed the system test. My point is that even in very short contests, like TopCoder, there are situations for such stress-testing against a simple solution.

2493 programmers took part in Codeforces Round 222 on Sunday (problems, results, my screencast that was unfortunately truncated after about an hour when I've locked my computer, top 5 on the left). The problems were fairly standard, but the last one required a great deal of accuracy. I'd like to highlight the easiest problem, though. The task was: given a connected set of cells on the grid and a number K, remove K cells from the set so that it remains connected. It is quite straightforward and can be solved in many ways, but it still requires some logical thinking and the statement is very easy to understand. I think this is a very good easy algorithmic problem.

One other peculiar fact about this week's Codeforces rounds is: today's top 5 are all from ex-USSR, while 4 out of Tuesday's top 5 are from China and Japan. There are several possible explanations. First, Tuesday's round was 1.5 hours later so it was less convenient for people in eastern timezones. Second, top 5 in a round is so random that there's nothing to explain at all. Third, one of the round's problems might be similar to a problem from an older contest that was only popular in a certain region. But these are the boring explanations :) Wouldn't it be interesting if different styles of education present in Russia vs Japan vs China led to different sets of skills that would in turn lead to such country-specific contest results? Has anybody seen more careful analysis of country distribution in algorithmic programming contest results?

This week in competitive programming

In contrast to last week, this week was quite light on programming contests. Late on Saturday, the final online round of the Facebook Hacker Cup took place (my screencast, top 5 on the left). Several things went wrong at the same time for me. First, I've spent an hour on the easiest problem by making a somewhat classical mistake: the problem statement had a constraint n_i<=4, and I immediately started thinking about solutions that rely on that constraint. It turned out that the correct solution works fine even for large values of n, and is much, much simpler that what I came up with during that hour. Then, I've implemented the solution for the third problem with the correct big-O asymptotic complexity, but without caring too much about the constant factor, and couldn't reduce the constant factor under the pressure of the last 30 minutes of the contest. I've made a desperate attempt to still run my solution against judges' input, but it timed out as expected.

When two problems go wrong at the same time, getting into the top 25 in the world is too hard, so congratulations and good luck to everybody who made it to the onsite finals!

On Sunday, TopCoder SRM 601 took place (problems, results, my screencast, top 5 on the left). Both the medium and the hard problems required tricky dynamic programming: the solution that comes to mind right after reading the problem has too many states in dynamic programming, so you have to somehow reduce the state space. While both problems look a bit artificial and thus not as exciting to solve, they are a good way to practice advanced dynamic programming if you want to (medium, hard).

Thanks for reading, and see you next week!

This week in competitive programming

 This week was very busy with contests. The week started with the second quaterfinal of the Kotlin challenge (problems in Russian, results in Russian, top 5 on the left). The round didn't go as smoothly as the first one, and the system had some downtime, so there will be a third quarterfinal to compensate those affected.

Then, Codeforces Round 219 took place on Friday (problems, results, top 5 on the left). Three out of four properties of an ideal contest held:
1) nobody solved all problems;
2) each problem got solved by somebody;
3) there's no problem solved by everybody.
The only missing part is
4) there's no contestant with zero problems solved.
But I guess the latter is quite hard to achieve in the Codeforces setting.

Saturday started with TopCoder SRM 600 which featured a T-shirt giveaway because of the round number (problems, results, my screencast, top 5 on the left). The screencast features two very long and probably boring situations: first, for the last 20 minutes of the coding phase I couldn't understand why my solution doesn't pass one of the samples, but couldn't. It turned out I was missing the fact that two lines can intersect in a point with non-integer coordinates, and it's unclear to me now how one can ignore this fact for so long. But even more disturbingly, during the last 13 minutes of the challenge phase I couldn't come up with a testcase for the medium problem with answer zero, but where there's exactly one way to reach zero. There's really no excuse for that.

Later that day, the second round of Facebook Hacker Cup happened (my screencast, top 5 on the left). With the format of competition penalizing very heavily for one's mistakes, the right strategy seemed to be to write two solutions for each problem, one fast and one slow, and compare them on many small testcases to make sure the fast solution is correct. That plan worked out well - but one may wonder if that strategy would be too slow to get into the top 25 in Round 3.

Just about 8 hours after the end of the Hacker Cup, on Sunday, the next stage of the Open Cup took place (top 5 on the left). The problems turned out to be too easy and the winner solved all of them in just over 2 hours. One must note the performance of the second-placed XZ team: I believe this is the first full team (as opposed to teams of just one person) regularly participating in the Open Cup from the Bay Area and from the USA in general. The convex hull of all participating teams on the globe (is there even such a thing on a sphere?..) just got bigger.

Later on Sunday, TopCoder SRM 600.5 took place (problems, results, top 5 on the left). It was a very unusual match, with 4 hours of coding and second and third problems being harder than the usual 'hard' problems from TopCoder. However, only those two problems got solved, with the grand total of 10 accepted submissions for about a thousand contestants and 4 hours.

The third problem was amazingly simply stated, and I still have no idea how to solve it (full problem statement). You are given a graph with N vertices numbered from 1 to N, where vertices A and B are connected by an edge if and only if abs(A-B) is in the given set S. How many connected components are there in this graph? N is up to 10¹⁸, S has up to 50 elements, each up to N. Any ideas?

Let me finish this very long post with a non-scoreboard picture, taken in Barcelona which I visited for 4 days and where I've solved most of the contests mentioned above: