Wednesday, December 28, 2016

A black radius week

Last week was very calm, as most algorithmic competition websites have called it a year or are busy preparing special New Year-themed competitions.

Nevertheless, AtCoder held its Grand Contest 008 right on Christmas Day (problems, results, top 5 on the left, analysis). In breaking with AGC tradition, the problems were quite technical and tedious this time. Big congratulations to apiad who has managed to get all of them accepted and won!

I have spent all 110 minutes on the attractive-looking problem F, severely underestimating the amount of things that can go wrong in its solution (I got it accepted after about 5 more minutes of debugging after the end of the contest). The problem simply asks: given a tree with some subset of its vertices colored black, consider all subsets of its vertices defined as "all vertices at distance at most d from some black vertex a" (for all combinations of d and a), and return the number of different such subsets. When the same subset is defined through several combinations of d and a, it must still be counted only once.

(Moscow Christmas on the left - compare to last year :)) In my previous summary, I have mentioned an interactive Open Cup problem: you needed to give a checkmate to a lone king on a 8x8 chessboard using just one piece - the amazon, that can move both as a queen and as a knight. To makes things harder, you are playing blindfolded and do not know the king's position or moves. More precisely, you are given the initial position of the amazon, and need to output such sequence of at most 50 moves that the king that starts in any position that is not checked by the amazon and makes any legal moves will eventually be checkmated at some point in this sequence, and will not be stalemated before that.

There are multiple approaches described in the post-match discussion, highlighting the fact that the problem allowed one's creativity to shine. However, the solution described by Endagorion also allows to answer the extra question I posted last week: how short can such sequence of moves be if the amazon starts at a1?

It turns out this shortest sequence is "a1 a2 b3 b4 c5 c6 c5 d4 d3 d4 e5 e6 e5 f4 f3 e5 f6" (16 moves). And to prove this, Endagorion simply runs a breadth-first search over all reachable states of the game. The state of the game, in this case, is the position of the amazon plus the set of positions where the opposite king can be. At first glance it seems like we might get 64*264 states, but in practice the number of reachable states is much, much lower - most likely because the set of reachable squares for the king fills any unattacked area reasonably quickly, and thus we get much fewer possibilities (just 312400 states are reachable, and only 54520 of those are traversed before we find a way to checkmate definitely).

Thanks for reading, and check back in 2017! Happy New Year!

Sunday, December 18, 2016

An amazon week

On Wednesday, TopCoder SRM 703 - the first TopCoder round after the TCO - took place (problems, results, top 5 on the left). Endagorion has claimed the victory thanks for an amazingly fast solution for the 1000 - he submitted it in just over 7 minutes! It turns out that a similar problem has appeared before, and he could reuse most of the code. Nevertheless, congratulations on the flawless execution!

Codeforces Round 385 on Saturday has gathered 8 nutella-rated participants, including the top 3 (problems, results, top 5 on the left, analysis). Tourist has guaranteed himself the first place in just over an hour, but couldn't solve everything because of extremely tricky geometric problem D. Congratulations on the win!

Here's problem E which has propelled him to the top, in a slightly simplified form: you are given n words with total length up to m, and need to check whether there exists a cyclic string that has at least two different decompositions into those words, in O(nm) time. For example, for a set {"aa", "aba", "ba", "bab"} the cyclic string "ababa"="babaa" has two decompositions: "aba" + "ba", and "bab" + "aa".

Finally, Open Cup 2016-17 Grand Prix of Peterhof has (probably?) wrapped up 2016 for many ACM ICPC teams (results, top 5 on the left). Problem E was the most unusual and thus the most creative: you needed to give a checkmate to a lone king on a 8x8 chessboard using just one piece: the amazon, that can move both as a queen and as a knight. To makes things harder, you are playing blindfolded and do not know the king's position or moves. More precisely, you are given the initial position of the amazon, and need to output such sequence of at most 50 moves that the king that starts in any position that is not checked by the amazon and makes any legal moves will eventually be checkmated at some point in this sequence, and will not be stalemated before that. Can you figure out how to do it? How short can such sequence of moves be if the amazon starts at a1?

Thanks for reading, and check back next week!

Saturday, December 17, 2016

A dfs week

Codeforces Round 383 was the main event of the last week (problems, results, top 5 on the left, analysis).  TooDifficult has regained the second place in the overall rankings thanks to his victory; his 2017 ACM ICPC World Finals rival mnbvmar is now ranked sixth thanks to his second place in this round. Well done!

In my previous summary, I have mentioned an unsolved NEERC 2016 problem where your program explores a maze with at most 20 rooms which look exactly the same. Each room of the maze has the same amount m (also at most 20) of outgoing one-way passages which also look exactly like one another, arranged in a circle. The only way not to get completely lost in this maze is to use the fact that each room also has a movable rock. Initially there's a rock is in the center of each room. When you leave a room, you can put the rock next to any outgoing passage, and moreover, you can choose whether to put it to the left or to the right of this passage (that means that there are 2m ways to put it). If you ever arrive in this room again, you will see whether the rock is placed to the left or to the right of a passage - but since all passages look the same, you won't have any other information! So now you will be able express the number of the passage to take, and the number of the passage to move the rock to by the number in clockwise order starting from the one marked with the rock when you arrive. Your goal is to visit all rooms in at most 20000 steps.

The solution is explained with pictures in the published analysis PDF (problem I), but let me repeat the outline here. We will implement a depth-first traversal of our graph. However, depth-first traversal sometimes needs to go back, and we can't do that since the passages are one-way. However, since the graph is strongly connected (it looks like I forgot to mention this property in the problem statement summary), there's always some way to get back. The main idea is: when leaving the vertex for the last time, mark the passage that leads as high up as possible in the depth first search tree. This way when we find ourselves in an already processed vertex, we can just follow the marked passages to get back to the current depth first search path. And inside that path, we will mark the passages that lead down this path, so that when we return to this path, we can then get down to the vertex that's being currently processed by the dfs. We can use left/right positioning of the rock to distinguish the vertices on the path ("grey") and the already processed vertices ("black"). There are some more technical details to the solution, but all ideas are above.

I find this problem very appealing for multiple reasons, one of them being that the solution is "tight": the amount of information we can store in the visited rooms turns out to be barely enough to perform the traversal. How can one come up with such tight problems?

Monday, December 5, 2016

A maze week

Last week was quite a bit calmer than its predecessors. On Monday, Code Festival 2016 wrapped up the festivities with its Grand Final (problems, results, top 5 on the left, online mirror results, analysis). It was W4yneb0t's day, as he managed to deny tourist a somewhat expected victory by solving the same amount of problems, but a more expensive set of them. Big congratulatons!

I did not cover a lot of ACM ICPC regionals this season, but now is a good time to start :) ACM ICPC 2016-17 NEERC took place on Sunday in St Petersburg, Barnaul, Tbilisi and Almaty (problems, results, top 5 on the left). One of the main events of the year for most of ex-USSR algorithmic competition community, and the main event of their entire algorithmic competition career for many teams who practice for multiple years for this one chance to advance to the World Finals. One can experience a very wide spectrum of emotions just by watching the NEERC award ceremony where some teams are full of joy and are not at all shy to share that moment with everybody, while others ruminate over the far-reaching consequences of just one bad day. Nevertheless, the community stays very close and friendly, and kudos to everybody for keeping the spirit going! And last but not the least, congratulations to the team SPb SU Base on the victory!

Problem I was left unsolved in the onsite competition, and it's a pity since I find it really beautiful. It's an interactive problem where your program explores a maze with at most 20 rooms which look exactly the same. Each room of the maze has the same amount m (also at most 20) of outgoing one-way passages which also look exactly like one another, arranged in a circle. The only way not to get completely lost in this maze is to use the fact that each room also has a movable rock. Initially there's a rock is in the center of each room. When you leave a room, you can put the rock next to any outgoing passage, and moreover, you can choose whether to put it to the left or to the right of this passage (that means that there are 2m ways to put it). If you ever arrive in this room again, you will see whether the rock is placed to the left or to the right of a passage - but since all passages look the same, you won't have any other information! So now you will be able express the number of the passage to take, and the number of the passage to move the rock to by the number in clockwise order starting from the one marked with the rock when you arrive. Your goal is to visit all rooms in at most 20000 steps.

The problem statement is quite abstract, so I encourage you to read in full in the PDF (problem I), especially the sample input/output. After you understand what's going on, however, I find it really exciting to solve!

In my previous summary, I have mentioned a CERC problem that had to do with bipartite matchings. You were given a bipartite graph with at most 20 vertices in each part (40 together). A set s of its vertices was called nice if there existed a matching that covers it - in other words, such that for every vertex from s there was an adjacent edge that belongs to the matching. Note that it's not necessary for each end of the matching edges to be in s. Each vertex also had an integer weight. Your goal was to count the number of nice sets (out of at most 240 total sets) with total weight exceeding the given threshold t.

I won't describe its detailed solution, but I will mention the main idea that makes this problem tractable. At first sight, we have 240 sets which is way too much to handle one-by-one. However, it turns out that a set s consisting of some set x of vertices of the first part and some set y of vertices of the second part can be covered by a matching if and only if both x can be covered by a matching and y can be covered by a matching (but those don't have to be the same matching)! This idea allows to reduce the number of sets to consider to 220, which is tractable.

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

A Makoto week

TopCoder Open 2016 Final fell on the Nov 21 - Nov 27 week (problems, results on the left, analysis by Bruce). The final results have all finalists sorted by rating, with one notable exception: rng_58 has completely dominated the field, already winning on the first two problems but also adding the 1000-pointer to make it clear that others don't stand a chance. Extremely well done! With this result, Makoto is 3 out of 3 for TCO finals.

Here's what the 1000-pointer was about. You are given an undirected graph with at most 14 vertices. You make at most 50000 copies of this graph, without any edges between them, to obtain a bigger graph (with at most 14*50000 vertices). Then, you replace the resulting graph with its complement: for each pair of vertices connected by an edge, you remove that edge, and for each pair of vertices that don't have a connecting edge, you add one. How many Hamiltonian paths does the complementary graph have, modulo 998244353?

Codeforces resumed its contests after a month-long break with Round 381 on Wednesday (problems, results, top 5 on the left, analysis). TooDifficult continued his streak of victories, adding this round to the last two TopCoder SRMs. Amazing consistency!

On Saturday, a brand new international onsite competition called Code Festival and ran by AtCoder took off in Tokyo. It has featured a diverse set of competitions, with the Code Festival 2016 Final being the closest to traditional rounds (problems, results, top 5 on the left, online mirror resultsanalysis). Only current and recent university students were allowed to join, nevertheless the field was top-notch. Facing very tough competition, tourist rose to the challenge and won in style by being the only one to solve all tasks. Congratulations!

Open Cup 2016-17 Grand Prix of Europe on Sunday has completed the run of 5 consecutive Open Cup weekends (problems, results, top 5 on the left, CERC results on the same problems, analysis). This time ITMO 1 was head and shoulders above everybody, winning 11-9 (11-10 if you take CERC into account) - really unbelievable result! My team in particular got stuck after solving 8 problems in 3 hours, and couldn't solve any of the remaining 4 tasks in the last 2 hours. Also notable is Makoto solving 9 problems single-handedly. He was really on a roll that week :)

Problem B in this round relied on a sound yet not widely known theoretical fact. You were given a bipartite graph with at most 20 vertices in each part (40 together). A set s of its vertices was called nice if there existed a matching that covers it - in other words, such that for every vertex from s there was an adjacent edge that belongs to the matching. Note that it's not necessary for each end of the matching edges to be in s. Each vertex also had an integer weight. Your goal was to count the number of nice sets (out of at most 240 total sets) with total weight exceeding the given threshold t.

Finally, Codeforces Round 382 wrapped up the week on Sunday night (problems, results, top 5 on the left, analysis). The coders in places from 3rd to 5th could've grabbed the first place if they could simply finish solving all problems in time, and that seems to have been quite doable, with more than 30 minutes left for Haghani and overtroll, and more than an hour left for MainDullMoeHand for just one problem - but they couldn't, and jcvb submitted his last problem with just 5 minutes to go to claim the victory. Well done!

In my previous summary, I have mentioned the problem that threw TCO 2016 Semifinal 2 into turmoil. You are given 1000 positive integers up to 1018. You need to find any subset of those integers with the following two properties:

  1. Bitwise and of all integers in the subset is zero.
  2. For any two integers in the subset, their bitwise and is not zero.

The problem statement sounds so simple, and yet the solution is very hard to spot, so let me describe it. Since the bitwise and of all integers in the sought subset is zero, for every bit (position in the binary representation) at least one of the numbers in the subset doesn't have it set. Here comes the key idea: if there exists any such subset, then there exists such subset and a bit such that exactly one of the numbers in the subset doesn't have this bit set. Why? Because when for each bit at least two numbers don't have it, we can remove any number from the subset without violating properties 1 or 2.

Now the problem becomes polynomial instead of exponential. Let's iterate over which bit will be present in all numbers except one, and which number will not have it. Which other numbers could we take into the subset? The numbers that have the chosen bit set and also have non-zero bitwise and with the chosen number. Property 2 will then always hold since all of those numbers have the chosen bit and thus non-zero bitwise ands, And for property 1, more numbers is always better, so we can afford to just take all numbers described above! We just need to check if their overall bitwise and (together with the first chosen number) is zero, and if yes, we have found our answer.

One reason this solution seems quite hard to spot is that it operates in a counter-intuitive manner. On the first step, we're reducing our subset to achieve the desired property. But on the second step, we're actually expanding it back.

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

Sunday, December 4, 2016

An and-clique week

The Nov 14 - Nov 20 week was busier. TopCoder SRM 702 on Tuesday was the last chance to practice before the TopCoder Open weekend (problems, results, top 5 on the left, analysis). xudyh won the second SRM in a row, and was the only one to solve all three problems. Congratulations!

The onsite event of TopCoder Open 2016, one of the main tournaments of the year, started with Semifinal 1 on Saturday (problems, results on the left, analysis by Bruce). Top 3 advanced to the final round next Monday, and everything was essentially decided by the speed on the 500-pointer. The problem statement was extremely simple: one needs to construct any weighted directed graph with at most 20 vertices that has exactly the given amount k of different minimum cuts. k is up to 1000.

Open Cup 2016-17 Grand Prix of Dolgoprudny took place early on Sunday (problems, results, top 5 on the left). Team Past Glory retook the ground they lost to ITMO 1 in the overall standings a week ago - well done!

Finally, TopCoder Open 2016 Semifinal 2 determined 3 more finalists (problems, results on the left, analysis by Bruce). Unlike the first semifinal, which went more or less normal, this round was very unusual. For the first 10-15 minutes none of the participants, and almost none of the observers, could figure out how to solve the easiest 250-pointer problem. Because of that, the advancement in this round hinged on the ability to give up on a problem and clear one's head before the next one. It's worth mentioning that the 500-pointer was also in no way obvious. Congratulations to Enot on successfully navigating the tricky round and coming out on top!

Here's the problem that puzzled everybody. You are given 1000 positive integers up to 1018. You need to find any subset of those integers with the following two properties:

  1. Bitwise and of all integers in the subset is zero.
  2. For any two integers in the subset, their bitwise and is not zero.
Can you see the key solution idea?

In my previous summary, I have mentioned an easy problem: you are given an n times n grid of uppercase English characters, where n is at least 3. This grid was built in the following way: first, we fill it with n different characters in such a way that each row and each column has exactly one occurrence of each character. Then, we replace exactly one character in the entire grid with another character. Your goal is to figure out which character has been replaced, and what was there originally.

Here's a solution that's very easy to implement. First, we count the number of times each letter appears in the grid, and find letters that appear at least twice. Those are the original letters. Then, for each row and column of the grid we check if they contain at least one appearance of those letters. We will find exactly one row and exactly one column that will be missing one of those letters - and those are precisely the row, column and letter that we need to output.

Thanks for reading, and check back later for more!

Saturday, December 3, 2016

A cosplay week

The Nov 7 - Nov 13 week woke up late with AtCoder Grand Contest 007 on Saturday (problems, results, top 5 on the left, analysis). The problemset seems quite well-rounded, offering competitors a choice of different strategies. cospleermusora has figured out the winning strategy this time - start with the three hardest problems since they're worth a lot more points, and then solve whichever easy problems there's time for. Great idea and execution!

Open Cup 2016-17 Czech Grand Prix took the usual Sunday spot (results, top 5 on the left). The ITMO 1 team won again and started to create quite a gap at the top of the overall standings. Amazing performance!

Problem J in this round was very easy, and yet it required some thinking to avoid too many special cases in code. You are given an n times n grid of uppercase English characters, where n is at least 3. This grid was built in the following way: first, we fill it with n different characters in such a way that each row and each column has exactly one occurrence of each character. Then, we replace exactly one character in the entire grid with another character. Your goal is to figure out which character has been replaced, and what was there originally.

In my previous summary, I've mentioned an interactive Open Cup problem: the judging program has a hidden non-degenerate triangle. The coordinates of its vertices are integers not exceeding 1000 by absolute value. You're allowed to make at most 1000 queries, and your goal is to determine the coordinates of the vertices of the triangle. In each query, you choose a line (more precisely, a half-plane), and you're told the areas of the two parts this line splits the triangle into (one of them can be 0 if it doesn't intersect the triangle).

Here is the solution of our team, which we've created together with Michael Levin: first, we figure out the bounding box of the triangle, using binary search with horizontal and vertical half-planes. At least one of the corners of the bounding box is a vertex of the triangle, which we can find using a 45-degree half-plane which cuts off just one small corner from the bounding box.

When we know a vertex and a 90 degree angle containing the rest, we can use binary search by angle using lines passing through this vertex to find the lines containing the two sides. Finally, we can find the remaining two vertices by binary searching along one of the lines with half-planes parallel to the other line.

This solution has 4 steps, with the first and last step sharing the same binary search problem (given a direction, find the first half-plane with this direction that has non-zero intersection area), so one needed to implement 3 different functions for the interaction. On the good side, the solution doesn't have any special casing at all.

Do you know a simpler approach?