A Christmas week

Last week got going with Codeforces Round 336 (problems, results, top 5 on the left). Nobody was able to solve the hardest problem, which allowed matthew99 to win by solving the remaining four problems in about an hour. Successful challenges by tourist and ACRush brought them closer, but it was barely not enough for the victory. Congratulations matthew99!

On Saturday, TopCoder SRM 677 (problems, results, top 5 on the left) featured problems by cgy4ever, which are usually very entertaining. I didn't manage to take part since I was on a plane during the time of the SRM. Maybe I'll still manage to solve the problems in the practice room, will then share the best one in a later post.

ACRush continued his impressive comeback by winning the second SRM in a row - great job! In my last post, I've mentioned him climbing into the third place in the all-time SRM victory stats, but I was somewhat expecting tourist to take that third place soon, as he was just two SRMs short. Well, now I'm not so certain :)

(Christmas in Moscow on the left) Finally, let's discuss the tough problem C from the previous week's Open Cup: two strings of 0s and 1s are considered equivalent, if one can be obtained from the other by repeatedly removing or inserting (anywhere in the string) the following substrings: 00, 111, 0101010101. For example, 100110 and 010011 are equivalent, since we can do the following sequence of transformations: 100110 --> 1110 --> 0 --> 0111 --> 010011. Given 4000 strings of total length at most 50000, find out the groups of equivalent strings among them.

The first approach that comes to mind is to build some kind of "reduction" process - in the example above, both strings could be reduced to just "0" by repeatedly removing the 00/111 substrings. However, it is very tricky since sometimes you have to first add something in order to be able to remove a bigger pattern. For example, if you have substring 001010101, then you can insert 111 to get 011101010101, then insert 00 to get 01100101010101, and finally remove the last 10 characters to get 0110. Building a system of reduction that always works is hard, and can probably only be accomplished by implementing a stress-test that will give you missing reductions with small lengths until you can catch all of them. Here's the description of such approach by darnley in Russian.

However, the problem becomes much more tractable if we bring in some powerful theory. One can notice that we have a presentation of a group with two generators and three relations here, and need to check if the given products represent the same element of the group. Which group is it? Well, the Wikipedia article referenced above actually has an answer: this is the group of rotations of an icosahedron, with 1 corresponding to a 120-degree rotation around a line passing through centers of two opposing faces, and 0 corresponding to a 180-degree rotation that swaps two opposing vertices. Now the only remaining challenge is to see how the vertices of an icosahedron are permuted by each of those two rotations, and the actual code simply boils down to multiplying permutations of 12 elements.

Reading the Wikipedia article more carefully, we can notice that the group is actually isomorphic to A₅, so there exist an even permutation of degree 2 and an even permutation of degree 3 with just 5 elements that will also work in the above solution. How do we find those permutations? Well, there's just one permutation of each kind up to renumbering of elements (two transpositions and a cycle of length 3), and we have to pick such two permutations that their product has degree 5. Now it's very easy to find two permutations that fit.

However, the Wikipedia article in question is not easy to find if you forget the right terms. What to do if you remember that this is related to groups but don't know about the icosahedral symmetry? We can approach the problem from the other side. Suppose we can come up with _any_ two permutations p and q such that p*p=e, q*q*q=e, and p*q*p*q*p*q*p*q*p*q=e. Then, we can multiply those permutations according to the sequences from the input, and in case two sequences resulted in different products we know that they're not equivalent. In case they resulted in the same product, we can't be sure (for example, if both p=e and q=e, this will always happen). But if we try enough (p, q) pairs, most likely we'll be able to differentiate. So we can use simple brute force to find a few such (p, q) pairs, and use them to compare our sequences!

Thanks for reading, and Happy New Year! Now on to the New Year Contest, let's see how many different languages I can remember in the remaining time :)

An icosahedral week

TopCoder SRM 676 was the first event of last week (problems, results, top 5 on the left). The match has once again provided ample challenge opportunities, but ACRush made sure he can relax during the challenge phase by being the only one to submit three correct solutions - congratulations! As a result, he has also moved to the clear third place in the all-time SRM victory stats.

Open Cup 2015-16 Grand Prix of Peterhof wrapped up the week on Sunday (problems, results, top 5 on the left). Problem C was very beautiful as it allowed several different approaches, and yet required a significant insight to come up with any of them. Here's what it was about: two strings of 0s and 1s are considered equivalent, if one can be obtained from the other by repeatedly removing or inserting (anywhere in the string) the following substrings: 00, 111, 0101010101. For example, 100110 and 010011 are equivalent, since we can do the following sequence of transformations: 100110 --> 1110 --> 0 --> 0111 --> 010011. Given 4000 strings of total length at most 50000, find out the groups of equivalent strings among them.

Finally, let me give the final pieces of the puzzle for the interactive string guessing problem from NEERC I've mentioned in two previous posts: the judges have a hidden binary string of 1000 zeroes and ones, and you have to guess it using at most 1500 attempts. For each attempt, you output some string of 1000 zeroes and ones, and the judge responds with one of three answers: either your guess is correct (and that means you've won); it's incorrect but _exactly_ half (500) of all characters are correct; all other incorrect situations grouped together.

Let's just make a random guess, 1000 random bits. What's the probability that we'll get 1000 matches? It's just 1/2**1000, a very, very small number. However, the probability that we'll get the other interesting answer - exactly 500 matches - is much higher, since there are many ways for the matches to happen. More precisely, it's C(1000, 500)/2**1000, which is about 2.5%! Which means that, on average, we'll get at least one "500" answer after just 40 random attempts.

After we get one "500" answer, we can do the following: let's flip exactly two bits in our string - bit 0 and bit x, for all values of x from 1 to 999. If the answer stays "500", it means that exactly one of bit 0 and bit x is correct, and in the other case they're either both correct or both incorrect. After doing this for all 999 pairs, we know the correct value of each bit if we assume that bit 0 is correct, and the correct value of each bit if we assume that bit 0 is incorrect, so we have just two remaining candidate strings to check, and one of them is guaranteed to give answer 1000.

In total, we're using about 1040 queries on average. Of course, on some testcases we might require more, but it's not hard to check that we're extremely unlikely to come even close to the allowed limit of 1500.

An interesting fact about this problem is that it's still not clear if any deterministic solution that fits into 1500 queries exists. Can you come up with one?

A 500+1000 week

The Dec 7 - Dec 13 week had two "usual suspects": a Codeforces round and a TopCoder round. Codeforces Round 335 took place a bit earlier on Wednesday (problems, results, top 5 on the left, editorial). TooSimple has climbed into a clear second place in the ratings after the amazing victory which included submitting problem E just 16 minutes into the contest - congratulations!

TopCoder SRM 675 happened on Thursday (problems, results, top 5 on the left). The top spot was decided in the challenge phase this time, and Milanin and Um_nik took advantage of this by climbing above the coding phase leaders tourist and ainu7 - great job!

Finally, let me give a small hint for the interactive string guessing problem from NEERC I've mentioned in the previous post: the judges have a hidden binary string of 1000 zeroes and ones, and you have to guess it using at most 1500 attempts. For each attempt, you output some string of 1000 zeroes and ones, and the judge responds with one of three answers: either your guess is correct (and that means you've won); it's incorrect but _exactly_ half (500) of all characters are correct; all other incorrect situations grouped together.

The first idea is to find a way to get at least one "500" answer. Then we can start getting information about individual characters by applying small changes to the string and checking if the answer stays 500. But how do we find at least one string that matches the hidden string in exactly 500 positions? Check the next week's summary to find out :)

A showdown week

The Nov 30 - Dec 6 week started with TopCoder SRM 674 on Tuesday (problems, results, top 5 on the left). The top fives this week have many people in common, as NEERC participants were going through the final preparations before the big contest. In the SRM, subscriber from the SPb ITMO team claimed the first place, and Um_nik from the Ural FU team claimed the third place, while xudyh in second place is also from a very strong ACM team from Tsinghua - which in shocking news is skipping the World Finals next year.

Codeforces Round 334 happened later on the same day (problems, results, top 5 on the left, editorial), and once again subscriber was at the top - congratulations! The third place went to Zlobober who's also representing a strong NEERC team - this time from Moscow SU.

Problem E in this round caught my attention, but I was a little bit too slow and finished my solution a few minutes after the end of the round. Here's what it was about: you're adding weighted edges one by one to an undirected graph, and after adding each edge we want to know the answer for the following question: what's the smallest number A such that there exists a subset of edges, such that each edge in the subset has weight at most A and each vertex is incident to an odd number of edges from the subset? There are 100000 vertices and 300000 edges.

There's a very nice post (spoiler alert!) on Codeforces describing various approaches to solving this problem. I've implemented something very similar to winger's approach, only splitting the larger of the two segments in half instead of always splitting the first segment in half. In general I think about this family of approaches for solving offline dynamic connectivity problems as "Burunduk1's master's thesis", although I'm not entirely sure if that is an accurate description :)

And finally, ACM ICPC 2015 NEERC itself took place on Sunday (problems, results, top 5 on the left, editorial, video broadcast recording in Russian, online mirror results). A few teams have battled for the top spot, but in the end the Ural FU team has managed to solve one problem more than everybody else, and will be one of the favorites for the 2016 World Finals in Thailand!

There were many nice problems in the problemset, but my favorite is problem J. The judges have a hidden binary string of 1000 zeroes and ones, and you have to guess it using at most 1500 attempts. For each attempt, you output some string of 1000 zeroes and ones, and the judge responds with one of three answers: either your guess is correct (and that means you've won); it's incorrect but _exactly_ half (500) of all characters are correct; all other incorrect situations grouped together. At first sight it seems impossible to make any progress when you only get interesting replies if you guess exactly 500 characters correctly, but it turns out this information is enough to guess the hidden string very fast.

Thanks for reading, and check back soon for the Dec 7 - Dec 13 week summary!

A week during NEERC

Tune in right now for the ACM ICPC 2015 NEERC broadcast: video in Russian, current standings, prediction contest favorites, online mirror starting in 7 minutes. I will be joining the video commentary team around 3 hours into the contest!

Codeforces Round 333 happened on Tuesday (problems, results, top 5 on the left). TooSimple got a clear first place thanks to solving all problems fast, and doing that in the reverse order. Had he chosen the more standard easiest-to-hardest sequence, his score would be 470+1115+1025+1464+1580=5654, just 1 point above izrak's second place! More generally, the Codeforces format has the score of each problem lose a constant fraction of its total points every minute. As a result, the optimal order of solving the problems is in decreasing order of points-per-minute (maximum points for the problem divided by the time required to solve it). For TooSimple the points-per-minute values were: A – 33, B – 104, C – 69, D – 91, E – 100. So the optimal order would actually be B, E, D, C, A – it would’ve yielded 1190+2130+1528+865+316=6029 points.

I’ve tried a new competition format at Croatian Open Competition in Informatics (COCI) Internet Contest #3 on Saturday (problems, results, top 5 on the left). More precisely, the format is not entirely new: it’s the almost forgotten old IOI format, but limited to 3 hours. You can submit your solutions at any time, and they’re judged only after the end of the contest, with independent scoring for each testcase your solution passes, so slow and partially correct solutions still score some points.

Competing without a scoreboard felt quite strange, it was probably the first time in the 13 years since IOI 2002 for me. The problems were somewhat “professional”, so the contest was a good training. Here’s the problem that was worth the most points: you’re given an NxN field with non-negative integers in each cell, and need to place exactly K non-overlapping dominoes so that the sum of the 2K covered cells is the maximum possible.

Normally covering with dominoes is reduced to dynamic programming on a ragged boundary, but in this problem N was up to 2000, so that was out of question. On the other hand, K was just up to 8, so different approaches came into play. Can you see how to solve this problem?

Another interesting question about this problem is: does it matter that we require exactly K dominoes, not “at most K dominoes” as one would normally expect? More precisely, do there exist such K and N, such that 2K<=NxN, and a NxN field of non-negative integers, such that we can get a higher sum by placing K-1 dominoes than by placing K dominoes?

ACM ICPC 2015 NWERC on Sunday was the penultimate European regional contest (problems, results, top 5 on the left, online mirror results, analysis videos). The first place went to the University of Helsinki team Game of Nolife, who have managed to escape the huge time penalty they’ve accumulated by solving one problem more than the second-placed team – congratulations!

Thanks for reading, and check back later for this week's summary!

And to repeat: tune in right now for the ACM ICPC 2015 NEERC broadcast: video in Russian, current standings, prediction contest favorites, online mirror starting in 7 minutes. I will be joining the video commentary team around 3 hours into the contest!

Another week with no problems

Gennady came back strong last week, winning two competitions. The first one was TopCoder SRM 673 (problems, results, top 5 on the left). Yet again he's solidified his coding phase lead with a successful challenge - great job!

Open Cup 2015-16 Grand Prix of Europe took place on Sunday, using problems of the ACM ICPC CERC regional (problems, results, top 5 on the left, CERC results, its top 5 below on the left). The top 5 online teams were above the top onsite team, although of course there's less pressure onsite when you're already leading by a problem or two :)

Congratulations to the University of Warsaw team on the very clear onsite victory! As usual with ICPC regionals, it's not clear how many teams will advance to the World Finals. Is this information already public?

And finally, another European regional SWERC 2015 showed some really close competition, with the top two teams separated by mere seconds (results, top 5 on the left). This time I'm pretty sure that at least two teams will be invited to the World Finals :)

Thanks for reading, and check back in several days for this week's summary, where I've finally solved some problems myself and can share them :)

An educational week

I've already shared my impressions about the TopCoder Open 2015 Semifinal and Final rounds; however, this week had another noteworthy event:

Educational Codeforces Round 1 has tried to realize the "only solutions that can truly handle all possible cases should score points" aspiration by allowing 24 hours of challenges, including the ability to stress-test, after the round has ended (problems, results, top 5 on the left, experiment description, experiment analysis). I haven't been participating myself, but from the surrounding blogs it looks like the experiment was quite successful, with many contestants contributing tricky testcases after the round has ended. What are your impressions from this format?

Thanks for reading, and check back next week!

A pre-week

After the TCO dust has settled, let's take a quick look at the pre-TCO week.

Open Cup 2015-16 Grand Prix of Siberia took place on Sunday (problems, results, top 5 on the left). In yet another reshuffle of top Russian teams, the SPbSU Base team got the top spot thanks to almost flawless correctness stats: only one incorrect submission per 11 problems! Such clean stats were once the trademark quality of another famous SPbSU team, the SPbSU 4 that won the world championship in 2014 (for example, here are the stats of the last Petrozavodsk training camp before the said world championship - the "Dirt" column is the fraction of incorrect attempts to correct attempts), so the SPbSU Base team has picked the right example to follow :)

An 8-connected day

TopCoder Open 2015 Finals concluded yesterday (problems, results, also on the left, editorial, discussion). This round had a few extremely nervous moments and a happy ending. It started in a usual manner with a 250 that's not difficult algorithmically but requires careful coding. After submitting it in about 10 minutes, I had to choose whether to go for the 600 or for the 1000. Without tourist in the final round my motivation for alternative strategies was much weaker, as increasing the variation at the expense of the expectation was not desirable. Kuniavski has submitted the 250 with higher score than myself, so there was still some motivation to go for the 1000, but I've still decided to go with the 600 hoping to beat kuniavski by solving it faster than him. This problem has later resolved itself because he has resubmitted his 250 for a much smaller score.

That's where things stopped going so smoothly. For quite some time, I had no idea how to solve the problem. After experimenting with a few testcases on paper, I had a plan: each 8-connected set of obstacles has to have a very specific form, and we can determine the direction of jumps along its boundary uniquely. That, in turn, lets us determine the direction of jumps one square further diagonally, and so on, so now we need to check whether those "projections" from different 8-connected sets of obstacles contradict.

This was possible to implement in the remaining time, but it would be extremely error-prone, so I've started the implementation with a random testcase generator and a maximum matching based slow solution to compare with. I've continued to implement the actual algorithm, and with about 10 minutes to go I had it passing the testcases from the problem statement, and most of 1000 randomly generated cases - but not all of them.

I've debugged a failing case on paper, and realized that my logic that checks for contradictions between projections is not strict enough. It was not clear how to fix it properly, and there was about 5 minutes remaining in the round at this point, so I've decided that my solution is probably completely wrong and started to re-read my 250 solution to check for errors.

But then, with about 2 minutes to go, qwerty787788 has submitted his solution for the 600, jumping to the first place. That has switched me to a different mode of thinking: what's a possible fix for my solution for the 600 that I could implement in 2 minutes? I've decided to try making the contradiction checking logic more strict by simply commenting out the specific part of code that caused no contradiction to be reported in the failing case - and was extremely surprised to see the new solution pass all 1000 randomly generated cases! It was extremely important to have the testcases and the testing framework ready by then, as everything happened in a matter of seconds, and I submitted my solution with about 20 seconds to go in the coding phase.

(Photo on the right from the official website) After the coding phase ended, I've ran my solution on 9000 more random cases - and it failed one or two of them :( Because of this, I was quite certain that my 600 solution would fail the system test, and thus started preparing for the challenge phase under the assumption that I have only 225 points. Having debugged my solution a day later, I know that the only bug was in the first part - I was sometimes incorrectly declaring a 8-connected set of obstacle cells to have a bad form, and the bug could only be triggered when such a set wrapped around at least one full cycle in a spiral-like manner. As 8-connected sets of obstacles play no part to the reference solution, it was very hard for the problemsetters to include such testcases into the system test, and thus the solution has actually survived them - but I didn't expect that after seeing it fail the stress testing.

As the challenge phase started, I've learned that all submitted solutions were quite long and hard to check, so challenging seemed hopeless, right until Kankuro challenged qwerty787788's 250-pointer. Now both Kankuro with 265 points and qwerty787788 with 233 points were slightly above my projected result of 225 points, so I've started desperately looking for a challenge. Unfortunately, I couldn't find any flaw in the remaining solutions. The tensions were eased a bit by Kankuro's own 250 failing a challenge from kuniavski, but qwerty787788 still stayed with 233 points until the end of the challenge phase.

After the end of the round, I learned from Egor that the 600 can be solved in a very simple way - I was missing the crucial observation that diagonals are completely independent and can be handled separately, so all the 8-connected-figure complexity was not necessary. I've also learned that qwert787788 had a correct solution, but he only checked it against the example cases and nothing else and thus it was likely to fail. The system test revealed that it did indeed fail, and that my solution unexpectedly passed - but the latter didn't really matter then.

Now I'm deeply regretting the fact that I forgot to turn on the screencast recording before the round started, as it would definitely be valuable to have this experience recorded, so I'm using this blog entry as such recording :)

Thanks a lot to TopCoder, to admins, problemsetters, event planners and organizers, to Jessie, Tim, Makoto and Gaoyuan personally, to the other Algorithm competitors, and to everybody who was watching! See you all at TopCoder Open 2016!

TopCoder Open 2015 Finals Finals

TopCoder Open 2015 Onsite Semifinal Round is over (problems, results, top 5 on the left, editorial, my screencast - might still be processing). The round turned out to have a beautiful but very hard 1000-pointer, so (in retrospect) the right strategy was to solve the first two problems, and then make sure the solutions are correct, most probably via stress-testing. However, many competitors including myself and tourist hoped to get the 1000, and thus failed to test the 250 and 500 properly. I was lucky that my solutions still passed (thanks to the wishes for luck in comments!), while tourist unfortunately had his 500 solution fail - very sorry for that, and better luck next year.

The five finalists will have the final battle very soon - the Final Round starts in about 45 minutes. The problem values are 250. 600 and 1000. Wish me some more luck :)

TopCoder Open 2015 Finals

The final round of the 2015 TopCoder Open, the oldest and one of the most prestigious international competitive programming tournaments for individuals, takes place today in Indianapolis (on the left: a small public library inside a city park). There will be two rounds: the Semifinal round, where 12 contestants participate and 5 advance to the finals, from 10:00 TopCoder time to 12:00 TopCoder time (other timezones), and the Final round for those 5, from 15:00 TopCoder time to 17:00 TopCoder time (other timezones).

TopCoder will be doing live coverage on Facebook, and on Twitch (this one is scheduled to start one hour after the beginning of each round, covering the end of coding phase and the challenges).

Wish me luck!

A week with stabilizers

Open Cup 2015-16 Grand Prix of Ekaterinburg took place last week (problems, results, top 5 on the left). Congratulations to the XZ team on their first win of the season! The results were decided by problem H, which asked to count how many different permutations can be generated by a given set of permutations of order at most 15, and thus boiled down to a beautiful but a bit obscure algorithm: the Schreier–Sims algorithm. In my view, the most important result of this round is an elementary description of the Schreier-Sims algorithm by Andrey Halyavin and Maxim Akhmedov (in Russian).

Problem A was the nicest in my opinion. You're given 10000 points on the plane such that no three points lie on the same line. You have to build a triangulation of this set of points, and then answer 100000 requests of the form: which triangle of triangulation covers the point with the given coordinates? You're free to pick any triangulation, so the goal is to pick such one that allows answering these requests quickly.

Thanks for reading, and check back soon for this week's summary!

An inverse topological week

ACM ICPC 2015 NEERC Moscow Subregional happened on Sunday of the previous week, both onsite as an ACM ICPC round and online for everybody (results, merged results, top 5 on the left). Team Ababahalamaha from the Moscow Institute of Physics and Technology had a standout performance and solved all 12 problems with half an hour to go - amazing!

The most surprising problem in this contest was problem K. You were given a graph, and needed to topologically sort it. And between the possible topological orders, you needed to pick the one where the first vertex is as early as possible, if there are still several choices - the one where the second vertex is as early as possible, and so on.

This problem has two possible approaches. One is somewhat standard, involving advanced data structures and quite tedious to implement. The other one is very simple, but hard to notice. Can you see the latter?

ACM ICPC 2015 SEERC also happened last weekend (problems, results, top 5 on the left, report). While the domination of the Ukrainian teams has become a norm there, the winning team is still somewhat a surprise: Zaporizhzhya National Technical University. Congratulations!

Coming back to last week, TopCoder SRM 672 took place on Wednesday (problems, results, top 5 on the left). Despite failing the hard problem, xudyh has won and continued his meteoric rise through the rankings, and is now the seventh in the world!

ACM ICPC 2015 NEERC Northern, Eastern, and a few other subregionals took place on Saturday using the same problemset (problems, Northern results, merged results, top 5 on the left). The battle between the top Russian teams continued, with yet another team on top this time - congratulations to team Dandelion from the Ural Federal University!

And finally, Codeforces Round 327 wrapped up the competitions on Sunday (problems, results, top 5 on the left). This time it was Endagorion who won despite failing the hardest problem, and continued his climb towards the top of the ranking - way to go!

Last week, I've mentioned a complex dynamic programming problem from a recent TopCoder SRM: consider a grid with 13 rows and 30 columns, with each cell having an arrow pointing either right or down. We go row-by-row starting from the top row, and within each row we go column-by-column starting from the left column, and place dominos (2x1 tiles) on the grid. Whenever we encounter a cell without a domino, we look at its arrow. If it's pointing to the right, and there's an empty cell to the right, we place a domino on those two cells. If it's pointing down and there's an empty cell down, we place a domino on those two cells. If there's no empty cell in the direction of the arrow, we try the other direction (down for right, and right for down). If both directions don't work, we don't place any domino on this cell. Assuming the direction of all arrows is picked uniformly randomly out of all 2^13*30 possibilities, what's the expected number of placed dominoes at the end of this process?

This type of problem lends itself naturally to a dynamic programming solution. Let's place the dominoes as described in the problem statement. After we've completed a few rows, we can notice that most dominoes we placed don't affect the rest of the placement anymore. More precisely, only the dominoes that stick out to the area that's yet to be processed matter for further computation - see the picture on the left. So we can use dynamic programming where the state is: the number of completely processed rows, the number of cells processed in the first incomplete row, and whether each of the cells directly below the processed ones is empty.

If the grid had 30 rows and 13 columns, we'd have around 30*13*2¹³ states - something we can definitely process in a fraction of a second. However, the grid in this problem had 13 rows and 30 columns instead, and thus the above approach is too slow as it has around 13*30*2³⁰ states.

Here's how to speed it up: instead of processing cells in row-major order, let's process them by diagonals as pictured on the left. It's not hard to check that this, in fact, gives exactly the same result in terms of which dominoes are placed where. However, when we process the cells in this order, we have to remember the state of at most 14 cells, and thus the total number of states is around 13*30*2¹⁴, which is small enough.

Thanks for reading, and check back next week!

A week with 13x30

Codeforces Round 325 was the first of two Codeforces rounds this week (problems, results, top 5 on the left). Um_nik has won his second Codeforces round thanks to finishing five problems with more than 30 minutes to go - impressive! Of course, subscriber's bug in problem A has also contributed - better luck next time for him.

TopCoder SRM 671 took place on Wednesday (problems, results, top 5 on the left). The top 5 of the round matched the current top 5 by rating almost exactly - just Burunduk1 did not participate, and snuke has managed to grab the fourth place instead.

I think such high correlation might be due to the fact that the hard problem was an interesting application of advanced dynamic programming, a very "professional" problem. Consider a grid with 13 rows and 30 columns, with each cell having an arrow pointing either right or down. We go row-by-row starting from the top row, and within each row we go column-by-column starting from the left column, and place dominos (2x1 tiles) on the grid. Whenever we encounter a cell without a domino, we look at its arrow. If it's pointing to the right, and there's an empty cell to the right, we place a domino on those two cells. If it's pointing down and there's an empty cell down, we place a domino on those two cells. If there's no empty cell in the direction of the arrow, we try the other direction (down for right, and right for down). If both directions don't work, we don't place any domino on this cell. Assuming the direction of all arrows is picked uniformly randomly out of all 2^13*30 possibilities, what's the expected number of placed dominoes at the end of this process?

Had the grid 13 columns and 30 rows, the dynamic programming would be pretty standard. But how do we deal with the transposed grid?

Codeforces Round 326 happened one day later (problems, results, top 5 on the left). With this victory, qwer continued his rocket-like rise through the rankings, with four new "titles" in last four rounds - I'm wondering what comes next :)

Finally, this week had quite a few important ACM ICPC selection rounds. ACM ICPC 2015-16 NEERC Southern subregional (problems, merged results, top 5 on the left, onsite results), together with an online contest on the same problemset three days later, gave us a chance to compare curent ACM ICPC teams where at least some of them were in real competition mode. Moscow State University team Trinity came out on top this time, getting problem M accepted with just 1 minute to go.

Does anybody know if team Excited who placed second is a real ACM ICPC team this year?

ACM ICPC 2015-16 NEERC Moscow subregional and SEERC still haven't published the results, so I'll come back to them next week.

And finally, let's come back to the Running City urban orienteering puzzles I've published in my last post.

The first one was:
1 + 6 = 7
1 + 3 = 2
3 + 6 = 4
4 + 6 = 5
Find a house with bas-relief sculptures at the northern end of the 4th. How many bas-reliefs with sheafs are there on the street facade?

The number referred to colors of the rainbow, and addition stood for mixing two paint colors: red + indigo = violet, and so on. "The 4th" referred to the Green street, or улица Зелёная.

The second one was:
The older brother got a highway, a street, and an alley (albeit an old-fashioned one). The middle sister got an avenue and a street, not too bad as well. The younger brother, however, got just one little alley. Find house number 6 on the younger brother's alley, and count the number of mosaics on the facade.

Here, the answer was the capitals of the Baltic states: there are Tallinn highway, Tallinn street, Reval (the old name of Tallinn) alley, Riga avenue, Riga street and Vilnius alley in St. Petersburg. When solving this puzzle, our team employed programming: we've parsed a list of all streets of St. Petersburg, and found the intersection of the highway and street names which turned out to be surprisingly small, then looked at them one by one until Tallinn "clicked".

Thanks for reading, and check back next week!

A week with sheafs

The biggest contest of last week for me was not a programming one: Running City 2015 took place in Saint Petersburg on Saturday (Bronevik-pro category: problems in Russian, results in Russian, top 5 on the left, all categories: problems in Russian, winners in Russian). This is an urban orienteering contest, where teams compete against one another to visit as many control points in the city as possible as fast as possible. However, it's not just about running, commuting or driving: first, the organizers try to pick interesting control points, so that you see interesting places and learn a lot about the city, so it's also a sightseeing tour in a sense. More importantly (at least for me), some control points are not simply given to you on the map or as a street adress; instead, they are given to you as puzzles. Only after solving the puzzle you know where you should go.

The puzzles are in Russian and often involve play on Russian words and/or Russian cultural context, but here's one from this year's contest that's somewhat international:

1 + 6 = 7
1 + 3 = 2
3 + 6 = 4
4 + 6 = 5
Find a house with bas-relief sculptures at the northern end of the 4th. How many bas-reliefs with sheafs are there on the street facade?

Here "4th" refers to a street, but not literally called "4th", but rather referring to "4" in the equations above. Counting bas-reliefs with sheafs serves two purposes: first, it's a good way to prove that you've actually found the right spot in the city that doesn't require a judge to always be there, and second, it helps you verify that your solution to the puzzle is correct - if there are no bas-reliefs with sheafs in the place you come to, you need to think again :)

Here's another puzzle from this year's contest, which requires more local knowledge, but at the same time is more typical for the contest as it requires to match one's ideas with the actual city streets:

The older brother got a highway, a street, and an alley (albeit an old-fashioned one). The middle sister got an avenue and a street, not too bad as well. The younger brother, however, got just one little alley. Find house number 6 on the younger brother's alley, and count the number of mosaics on the facade.

The competition has a lot of categories, differing in difficulty (some require just 4-5 hours, some 10+), allowed means of transportation (only walking, walking and running, public transportation, no restrictions which effectively means driving), and the style of control points (given as an address, or as a puzzle). I'm usually participating in the difficult no-transportation-restrictions all-control-points-as-puzzles category, called "Bronevik-pro", but I think it's great that they provide categories to everybody's taste - i.e., I can totally understand how many competitors find it exciting to look for ways to find creative ways of using public transportation and the best order of passing control points in the "Atlant" category.

Most of their competitions happen in Russia, but they do have some international presense (planned for 2016: Helsinki, Milan, Istanbul), and to the best of my knowledge the international competitions have some categories in English, so if you notice your city on the event list, I think it's worth participating in :)

TopCoder SRM 670 took place during the Running City (problems, results, top 5 on the left). In addition to the highest score from coding, tourist has managed to gain +150 from challenges, although it turned out to be not even necessary for this vey convincing victory - great job!

Sunday was the day for Open Cup 2014-15 Grand Prix of SPb (results, top 5 on the left), The Nizhny Novgorod SU team has won their second Grand Prix of the season, matching Past Glory's achievements - way to go!

This round had many nice problems, but let me mention the most difficult one, problem C. Consider an undirected graph without repeated edges (but possibly with loops) with n vertices. Such graph is called Eulerian if and only if there's a cycle that traverses each edge exactly once. How many Eulerian graphs with n vertices exist, up to isomorphism? n is up to 60, you need to output the answer modulo 10⁹+7.

Last week, I've mentioned an old problem that I couldn't understand my own solution for. The problem was: given an amount, and a set of coin denominations such that for every two denominations one divides the other evenly, how many ways are there to assemble the given amount?

After some time, I think I've figured my solution out :) Let's create a graph interpretation for our problem. We'll create a directed graph with n "layers", each layer corresponding to one coin denomination. For a layer corresponding to denomination x, there are vertices corresponding to amounts 0, x, 2x, ... For each vertex there's an arc to the next highest amount in the same layer. Additionally, for each vertex except those on the first layer there's an arc to the same amount on the previous layer - the one corresponding to the next smallest denomination. The picture on the left illustrates the graph corresponding to denominations 1, 2, 4 and 12.

We can notice now that the ways to assemble the required amount a correspond to the ways to go from vertex 0 on the n-th layer to vertex a on the first layer: every time we make a horizontal move inside the layer corresponding to denomination x, we take one coin of denomination x. Because we're only allowed to move horizontally or upwards, we will enumerate the coins in non-increasing order, and thus each way to assemble the required amount will be counted exactly once.

Now we'll use dynamic programming to find the number of ways to reach amount p on layer q. To transition from amount p to amount p+1, we need to consider horizontal movement, which doesn't change the layer, and also upwards movement, which means we should add the number of ways to reach layer q to the number of ways to reach each smaller layer, assuming layer q has a vertex at the amount p+1. If we write all answers for one p as a vector, transitioning from p to p+1 corresponds to multiplying this vector by a matrix, and there are n different matrices in play, depending on the highest denomination that divides p+1. Finally, fast matrix exponentiation allows us to multiply those matrices fast enough.

Hopefully the code (requires TopCoder login) makes more sense now:
public int solve(long coins_sum, long[] values) {
    int n = values.length;
    long[][][] oneCycle = new long[n][][];
    oneCycle[0] = unitMatrix(n);
    for (int i = 1; i < n; ++i) {
        long curBy = values[i] / values[i - 1];
        oneCycle[i] = multiply(extraMatrix(n, i), pow(oneCycle[i - 1], curBy));
    }
    long[][] total = unitMatrix(n);
    for (int i = n - 1; i >= 0; --i) {
        long fullCycles = coins_sum / values[i];
        coins_sum %= values[i];
        total = multiply(pow(oneCycle[i], fullCycles), total);
    }
    long res = 0;
    for (long x : total[0])
        res += x;
    return (int) (res % MODULO);
}

private long[][] extraMatrix(int n, int start) {
    long[][] res = unitMatrix(n);
    for (int i = 0; i < start; ++i)
        res[i][start] = 1;
    return res;
}

Thanks for reading, and check back tomorrow for this week's summary and for answers to the Running City puzzles!

A week with old self

// This post is for Sep 28 - Oct 4 week. I'm sorry for the delay!

Monday was the day of TopCoder SRM 669 (problems, results, top 5 on the left, Egor's screencast). It would seem that Egor has found renewed motivation in my publishing of his screencasts in this blog: two weeks ago he jumped onto the leaving TopCoder Open train during the challenge phase, and this time he won the SRM easily - great job!

The most interesting aspect of this match for me was about the hard problem. You're given an infinite amount of coins of each denomination from 1, M, M², M³, ..., and a given amount X, up to 10¹⁸. M is up to 1000. How many ways are there to assemble this amount using the given coin types?

I didn't have much time left for this problem, but I also didn't have any good ideas how to approach it. After the match has ended, we've found out that a more difficult version of this problem has appeared in SRM 527 four years ago: in that problem, the denominations were not fixed to powers of a single integer, and the only constraint was that for every two denominations one divided the other evenly. Back in 2011, both I and Egor have solved the problem, but neither I nor him remembered anything about it :)

That's when things started to be a little surreal. I've opened my solution (requires TopCoder login) from that match - and I couldn't understand how it worked! After some time and effort, I've finally figured it out, and I'll tell more in the next week's summary - but in the meantime, can you understand it? Here's the main part of the code:

public int solve(long coins_sum, long[] values) {
    int n = values.length;
    long[][][] oneCycle = new long[n][][];
    oneCycle[0] = unitMatrix(n);
    for (int i = 1; i < n; ++i) {
        long curBy = values[i] / values[i - 1];
        oneCycle[i] = multiply(extraMatrix(n, i), pow(oneCycle[i - 1], curBy));
    }
    long[][] total = unitMatrix(n);
    for (int i = n - 1; i >= 0; --i) {
        long fullCycles = coins_sum / values[i];
        coins_sum %= values[i];
        total = multiply(pow(oneCycle[i], fullCycles), total);
    }
    long res = 0;
    for (long x : total[0])
        res += x;
    return (int) (res % MODULO);
}

private long[][] extraMatrix(int n, int start) {
    long[][] res = unitMatrix(n);
    for (int i = 0; i < start; ++i)
        res[i][start] = 1;
    return res;
}

Codeforces Round 323 took place on Saturday (problems, results, top 5 on the left). Ecnerwal has continued his great form that helped him qualify for the TopCoder Open, and won this round, but both ikatanic and uwi finished extremely close, within 7 points of the first place - congratulations to all three!

And finally, Open Cup 2015-16 Round 3, the Grand Prix of Eurasia, happened on Sunday (problems, results, top 5 on the left). The problemset was mostly easy, but still team Past Glory has achieved an amazing feat, solving the first 10 problems in just 1 hour and 23 minutes! Of course, winning the round after that was almost guaranteed. Congratulations!

Thanks for reading, and check back tomorrow for last week's summary!

A week with a Japanese surprise

The Open Cup held a surprise second round, the Grand Prix of Japan, last Sunday (results, top 5 on the left, overall standings). Past Glory team returned to, well, past glory with a very convincing victory - congratulations!

Problem B, while not very difficult algorithmically, presented a nice implementation challenge: one could write the code in 10 minutes, but could also spend an hour or more. You were given 3000 boosters with integer coordinates up to 10⁹, each pointing in one of four cardinal directions. You can start at any booster, fly in the direction in points to the next booster (if any), then fly in the direction that booster points, and so on. As soon as you leave a booster, it disappears, so you don't change your direction when you pass through its point again. What is the maximum number of boosters you can visit if you choose your starting booster properly?

In my previous post, I've mentioned the medium problem from TCO 2015 Round 3B: you are given 200000 cookies (3 types pictured on the left), with two players taking those cookies in turn one by one. Each cookie has some value for the first player, and some possibly different value for the second player. It is known that the second player always takes the cookie with highest value for him, and when there are several, with the highest value for the first player among those. The first player, on the other hand, is more flexible. He can take any cookie, and his goal is to maximize the total value of the cookies he gets in the end to him minus the total value of the cookies the second player gets in the end to the second player. What is the optimal strategy for the first player?

I won't tell you the full solution, but I will give you a key hint. Let's forget about the goal of the first player, and simply ask ourselves: which subsets of cookies can he achieve? Let's also order the cookies by second player's priorities: first by decreasing value for the second player, then by decreasing value for the first player. It's clear now that the second player will take either the first or the second cookie in this order on the first move, one of the first four cookies on the second move, and so on. In fact, the first player can achieve any subset that has the following properties: at most one cookie from the first two, at most two cookies from the first four, at most three cookies from the first six, and so on.

This is not the full solution yet, but we've effectively removed the game from the problem - now we just have a question about some subsets of our set, and this question is much easier to answer.

Thanks for reading, and check back next week!