Monday, March 11, 2019

A painful week

TopCoder SRM 752 was the first round of the last week (problems, results, top 5 on the left, analysis). rng_58 maintained his advantage in the race for the third TCO19 spot and was quite close to increasing his lead even further as he was just 4 points behind the first place before the challenge phase, and pashka was outside the top 10. However, tourist found 100 challenge points and won (congratulations!) and pashka found 50 challenge points and jumped into exactly 10th place, meaning that both rng_58 and pashka got 4 tournament points for this round.

Codeforces held its Round 545 early on Friday (problems, results, top 5 on the left, analysis). Only sunset was able to solve very tricky problem F, so even exceeding the memory limit in problem C (thanks to implementing an asymptotically optimal solution but with a huge constant both for time and memory) did not change the outcome. Congratulations on the win!

Open Cup 2018-19 Grand Prix of China wrapped up the week (results, top 5 on the left, analysis). All problems were solvable in this round, but all of them required quite a bit of thinking and quite a bit of coding, and also, as zeliboba quite succinctly formulated, had a few somewhat unnecessary corner cases. Team Past Glory still prevailed in those tricky conditions with the last problem accepted at 4:59. Well done!

Problem E in this round reminded me of my earlier post where I tried to describe a way to find dynamic programming states semi-automatically. The problem went like this: let's define f(x) as the smallest non-negative number that can be obtained by placing + or - before each digit in the decimal representation of x, and computing the resulting sum. How many numbers x between l and r have f(x) equal to 0, 1, ..., 9? l and r have at most 100 digits, and there are 10000 testcases to solve in 2 seconds.

The idea to use dynamic programming is on the surface, but it's completely unclear how to achieve a manageable number of states. Do you see a way to find a small state space algorithmically?

Thanks for reading, and check back next week!

Sunday, March 10, 2019

An oracle week

Last week had an Open Cup round for the fourth week in a row. Open Cup 2018-19 Grand Prix of America allowed teams from all over the world to participate in NAIPC 2019 (problemsresults, top 5 on the left, NAIPC results, analysis). Just 3.5 hours were enough for team Past Glory to wrap the problemset up, a good 40 minutes before other teams could do the same. Congratulations on the win!

In my previous summary, I have mentioned two (in some sense three :)) problems. The first group was from the AtCoder World Tour Finals: consider an infinite 2D grid, where each cell can be either black or white. Initially, exactly one cell was black, and then we repeatedly applied the following operation: take some integers x and y, and invert the color of three cells: (x, y), (x+1, y) and (x, y+1). You are given the set of black cells in the final state of the grid. There are at most 105 black cells in C1 and at most 104 in C2, and each black cell has coordinates not exceeding 1017 by absolute value. Your goal is to find the coordinates of the only cell that was black originally. In problem C1 you know that its y-coordinate was 0, and in C2 there are no further constraints.

A typical idea in this type of problem is to come up with an invariant that is not changed by the operation and that can be efficiently computed for source and target positions. A typical invariant that plays well with inversions is boolean or bitwise xor. Let's say that a white cell is a 0, a black cell is a 1, let's also pick some set of cells S, then our invariant will be their bitwise xor (in other words, the parity of the number of black cells in S).

Not any set S works, though: we must make sure that for each invertible triple (xy), (x+1, y) and (xy+1) either 0 or 2 cells belong to S, to make sure the xor does not change when we invert the triple. Suppose that for some row y=y0 the set S contains exactly one cell (x0,y0). The triple (x0,y0), (x0+1,y0), (x0,y0+1) must have 0 or 2 cells in S, and since (x0,y0) is in S but (x0+1,y0) is not, (x0,y0+1) must be in S. Applying a similar argument, we find that in the row y=y0 exactly two cells must be in S: (x0,y0+1) and (x0-1,y0+1). Then we can compute which cells must be in S in the row y=y0+2, and so on.

We can realize by looking at the resulting pattern, or by understanding what the process really is, that in general a cell (x0-k,y0+n) is in S if and only if C(n,k) is odd. And that, in turn, is true if and only if n&k=k, where & denotes bitwise and. There are still multiple ways to extend the set S to rows with y<y0, so to avoid thinking about that we will always pick very small y0 that is below all interesting points.

Now it is very easy to compute our invariant for the input set of cells: we need to count the parity of the number of such (x,y) in the set that (y-y0)&(x0-x)=x0-x. But we know that the operations do not change the invariant, and that initially we had only one cell (xA,yA). This means that we have an oracle that can tell us whether (yA-y0)&(x0-xA)=x0-xA for any two numbers x0 and y0 such that y0<=yA.

In problem C1, we know that yA=0, so we can just pick y0 in such a way that -y0 has all bits set except one, and then the oracle will effectively tell us the corresponding bit of x0-xA, so we can determine xA in logarithmic number of queries.

In problem C2 the things are not so simple. However, suppose we have found some x0 and y0 such that (yA-y0)&(x0-xA)=x0-xA, in other words we made our oracle return 1. Now we can go from the highest bits to the lowest bit, and by calling our oracle 3 additional times checking what happens if we add 2k to x0 and/or subtract 2k from y0, we can determine the k-th bit of yA-y0 and x0-xA, then setting both to 0 and proceeding to the lower bits, and eventually recovering yand xA.

The tricky part lies in the initial step of making the oracle return 1 for something: the probability of n&k=k for random n and k is roughly 0.75number_of_bits, which is way too low to just stumble upon it. This is how far I got during the contest, so the remaining magic is closely based on the official editorial and my conversations with Makoto.

Instead of running the oracle for the set S with just one cell (x0,y0) in the row y=y0, we will run it with the set S which has all cells (x0,y0) in the row y=ywhere x0 mod 3=u, l<=x0<=r, where y0u, l and r are the parameters of the oracle. This requires counting the number of xsatisfying the above criteria and also the constraint (y-y0)&(x0-x)=x0-x for each black cell in the input, which can be done by a relatively standard dynamic programming on the bitwise representation of x0.

As we know, this will give us the parity of the amount of such x0 that x0 mod 3=ul<=x0<=r, and (yA-y0)&(x0-xA)=x0-xA. A crucial observation is: no matter what y0 we pick, if is very small and r is very large, then for at least one u from the set {0, 1, 2} this oracle will return 1! This can be proven by induction by yA: when yA=y0, (yA-y0)&(x0-xA)=x0-xA only when x0=xA, so the oracle will return 1 when u=xA mod 3 and zero in the other two cases. When yincreases by one, given our C(n,k)-like propagation, every xfor which the oracle returns 1 contributes one to itself and x0+1, which means that we go from parities (a, b, c) for the three remainders modulo 3 to parities (a+b, b+c, a+c), so from (1, 0, 0) to (1, 0, 1), and then to (1, 1, 0), and then to (0, 1, 1), and then to (1, 0, 1) and so on, and never get (0, 0, 0).

This means that in at most three attempts we can make this complex oracle return 1. Now (more magic incoming!) we can do a binary search: if for (y0, u, l, r) the oracle returns 1, then it must return 1 for exactly one of (y0ulm) and (y0um+1, r). This way we can find a single cell (x0,y0) for which the oracle returns 1 in a logarithmic number of requests to the complex oracle, and then switch to using the simple oracle and proceed with reconstructing the answer as described above, completing the solution of C2.

I have also mentioned an Open Cup problem: you have some amount x of money between 0 and 1. You're playing a betting game where in one turn, you bet some amount y, and with probability p (p<0.5) your amount of money becomes x+y, and with probability 1-p it becomes x-y. Your bet must not exceed your current amount of money. Your goal is to reach amount 1. So far this setup is somewhat standard, but here comes the twist: your bets must be non-decreasing, in other words at each turn you must bet at least the amount you bet in the previous turn. In case you don't have enough money for that, you lose. What is the probability of winning if you play optimally? More precisely, what is the supremum of the set of probabilities of winning of all possible strategies? Both x and p are given as fractions with numerator and denominator not exceeding 106, and you need to return the answer using division modulo 998244353.

You can find my approach to solving it in this Codeforces comment.

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

Wednesday, February 27, 2019

A WTF week

AtCoder World Tour Finals 2019 in Tokyo headlined the last week (problems, results on the left, open round results, my screencastanalysis). The last three problems turned out too difficult to solve during the contest, so it all came down to speed on the first three. yutaka1999 was the fastest, but his five incorrect attempts gave the competitors 25 minutes to overtake him, and apiad did just that and won the first ever AtCoder World Tour. Congratulations!

I was pretty quick with solving A and C1, but then tried to solve B, C2 and E in parallel, switching often from one to another, instead of focusing on just one of them as it was not clear at that point that solving just one more would be enough for a good result. By the time I managed to come up with a solution for B, it was already too late to catch apiad and yutaka1999.

I found the problems C1 and C2 the most exciting. Consider an infinite 2D grid, where each cell can be either black or white. Initially, exactly one cell was black, and then we repeatedly applied the following operation: take some integers x and y, and invert the color of three cells: (x, y), (x+1, y) and (x, y+1). You are given the set of black cells in the final state of the grid. There are at most 105 black cells in C1 and at most 104 in C2, and each black cell has coordinates not exceeding 1017 by absolute value. Your goal is to find the coordinates of the only cell that was black originally. In problem C1 you know that its y-coordinate was 0, and in C2 there are no further constraints. Can you see a way to solve at least C1?

TopCoder SRM 751 followed on Friday (problems, results, top 5 on the left, analysis). Only rng_58 and pashka submitted all three problems, but the challenge phase did not leave them unscathed, and IH19980412 emerged in the first place thanks to three successful challenges, including one on rng_58 himself. Well done!

Open Cup 2018-19 Grand Prix of Bytedance presented problems from the team Moscow SU: Red Panda on Sunday (results, top 5 on the left, analysis). There were several nice problems in this contest, and problem C was the one I've enjoyed solving the most.

You have some amount x of money between 0 and 1. You're playing a betting game where in one turn, you bet some amount y, and with probability p (p<0.5) your amount of money becomes x+y, and with probability 1-p it becomes x-y. Your bet must not exceed your current amount of money. Your goal is to reach amount 1. So far this setup is somewhat standard, but here comes the twist: your bets must be non-decreasing, in other words at each turn you must bet at least the amount you bet in the previous turn. In case you don't have enough money for that, you lose. What is the probability of winning if you play optimally? More precisely, what is the supremum of the set of probabilities of winning of all possible strategies? Both x and p are given as fractions with numerator and denominator not exceeding 106, and you need to return the answer using division modulo 998244353.

Finally, Codeforces Round 542 wrapped up the week on Sunday evening (problems, results, top 5 on the left, analysis). Three contestants solved all problems correctly, and there wasn't much challenge activity, so everything was decided by the problem solving order and speed. mnbvmar was the fastest to solve everything, and did (the slightly faster to solve) problem E before problem D unlike the others. Congratulations on the victory!

Last week I have mentioned another Open Cup problem: there's a hidden not necessarily convex polygon with n vertices (n<=200). Your goal is to find its area, but the only thing you can do is to pick a subset of its vertices by their numbers (the vertices are numbered in the order they appear along the polygon), and the system will tell you the area of the convex hull of the chosen points. You can retrieve the convex hull areas for at most n*(n-1)/2 subsets before you need to give back the area of the hidden polygon.

During the contest we tried to invent a solution based on representing the area of the polygon as the sum of signed areas of triangles using one of its vertices as the base point. We could not figure out a way to deal with "signed" part: we need to determine the orientation of each triangle, and while in most cases we can determine orientation of triangle ACD given the orientation of triangle ABC and ability to ask convex hull area queries, we could not see a way to make it work in all cases. Is there one?

The approach that works involves a completely different idea: first, let's find the area of the convex hull of all vertices. Since our polygon is not necessarily convex, then we need to subtract something from it.

For each particular vertex, we can find whether it lies on the boundary of the convex hull or not by checking if the area of the convex hull of all vertices except this one is smaller. Now we know which vertices do not lie on the convex hull of everything.

Now let's take segments of consecutive vertices that do not lie on the convex hull, together with one vertex of convex hull before and after such segment. We claim that those are precisely the polygons whose areas we need to subtract from the area of the big convex hull to find the answer.

The only remaining step is to recursively apply the same algorithm to find the areas of those smaller polygons.

Thanks for reading, and check back next week!

Monday, February 18, 2019

A snack week

CodeChef SnackDown 2019 onsite finals early on Saturday was the main event of the week (problems, results, top 5 on the left). Team ovuvuevuevue enyetuenwuevue ugbemugbem osas looked to have pretty good winning chances when they were the first to solve 8 problems with a couple of hours still left in the contest, but they could not make further progress in the remaining time. Team Dandelion solved the ninth problem with about five minutes remaining to go on top, but team pastry was working on the same problem and could still overtake them on penalty time. It turned out that they were comparing their solution locally against a slower but simpler one, and there were still cases of disagreement as the end of the contest was approaching. With nothing left to lose, they submitted whatever they had 30 seconds before the end of the round — and it passed the system test. Congratulations to team pastry on the super narrow victory!

Later that day, Codeforces hosted its Round 539 (problems, results, top 5 on the left, analysis). The participants of the Codechef finals occupied most of the top spots in this round as well. wxhtxdy was the only contestant to solve all problems, but as his solution to E turned out to be incorrect, Um_nik emerged in the first place. Congratulations to Um_nik on the win!

Finally, the Open Cup 2018-19 Grand Prix of Belarus wrapped up the week (results, top 5 on the left). Team MIT THREE won the second round in a row, this time solving three in the last hour including two hardest ones in the last fifteen minutes. Amazing persistence once again, well done!

Problem A was a very nice interactive one: there's a hidden not necessarily convex polygon with n vertices (n<=200). Your goal is to find its area, but the only thing you can do is to pick a subset of its vertices by their numbers (the vertices are numbered in the order they appear along the polygon), and the system will tell you the area of the convex hull of the chosen points. You can retrieve the convex hull areas for at most n*(n-1)/2 subsets before you need to give back the area of the hidden polygon.

Thanks for reading, and check back next week!

I will also try to post something here and/or on Twitter about the first ever AtCoder World Tour finals in Tokyo on Thursday — already looking forward to the event!

Monday, February 11, 2019

A tourist week

Codeforces hosted its Global Round 1 on Thursday (problems, results, top 5 on the left, analysis). tourist and Um_nik were quite close, both finishing the problem-solving part around 1:20 mark and having some challenge fun thereafter. However, in the end the challenges did not affect the standings, and tourist stayed in first place. Congratulations!

TopCoder SRM 750 followed a day later (problems, results, top 5 on the left, analysis). This time tourist managed to get a commanding lead thanks to solving the 1000-pointer in just 8 minutes, while rng_58 needed 22 minutes and others even more. Well done!

Finally, the Open Cup returned on Sunday with the Grand Prix of Gomel (results, top 5 on the left). This was the first of seven consecutive Open Cup Sundays stretching right up to the ICPC World Finals, and that will provide a good preview as many top-rated ICPC teams are competing. The team from MIT earned the first place with just four minutes remaining, solving two of the hardest problems in the last hour. Amazing performance!

In the previous summary, I have mentioned a TopCoder problem: you are given a 9x47 grid of zeroes and ones. In one step, you can take any cell that contains a one, and another cell that is either in the same row but to the right or in the same column but to the bottom from the first cell, and flip both of them (so one changes to zero, and zero changes to one). You are given the initial and the final state of the grid, and need to produce any (not necessarily the shortest) sequence of operations that transforms one to the other with at most 947 operations.

When we apply this operation to a one and a zero, we're effectively moving the one to the bottom or to the right. By applying this operation several times, the one can move to the bottom and to the right. Moreover, the opposite is true: for any position to the bottom and to the right, we can move the one there in exactly two operations. If the cell in the middle (in the same row or column as both source and target cells) contains a zero, then we just move the one twice in a straightforward manner. If the cell in the middle contains a one, then we can first move that one to the target, and then move the one from the source to the middle cell, restoring the one there.

Finally, the other option of applying the operation to a one and a one, or moving a one onto a one in two operations as described above, results in both ones disappearing. Now we're in a very nice position: we understand the full structure of the problem, and have described everything that is possible in a very concise manner, which allows to see the solution.

More precisely, we need find a "source" one in the initial grid to the left and/or to the top for each one from the final grid, which might also leave some ones in the initial grid unused. Note that if the number of unused ones is odd, there's no solution since all operations preserve parity, and if the number of unused ones is even, we can always get rid of them by moving each to the bottom-right corner in at most two operations.

This observation leaves us with a matching problem which can actually be solved greedily because of the special structure of the graph. If we traverse the ones from the final grid in row-major order, we can simply always pick the rightmost yet-unused one in the initial grid to the left and/or to the top from the current position. This can be proven by a typical exchange argument: let's look at the first time in this row-major traversal when the optimal solution uses a different one to cover the final one in the current position, and uses the greedy choice to cover something else. We can swap the assignments of those two ones and still obtain a valid solution.

Thanks for reading, and check back next week!

Sunday, February 3, 2019

A mumbling week

TopCoder SRM 749 was the main event of this week (problems, results, top 5 on the left, my screencast with mumbling). All three problems were quite tricky, and passing the sample cases did not really mean that much. As he often does, rng_58 excelled in such circumstances and claimed the first place with a sizable margin — congratulations!

The only other contestant to solve the hardest problem, pashka, was actually unable to figure out the proper algorithmic solution in time; so he decided to take his chances and treat the problem as a general hamiltonian cycle problem and solve it with a simple but powerful heuristic, just like I did in 2014. It seems that participating in IOI 2002 has finally paid off for both of us :)

The medium problem was quite nice in this round. After removing some unnecessary complications, the statement boiled down to: you are given a 9x47 grid of zeroes and ones. In one step, you can take any cell that contains a one, and another cell that is either in the same row but to the right or in the same column but to the bottom from the first cell, and flip both of them (so one changes to zero, and zero changes to one). You are given the initial and the final state of the grid, and need to produce any (not necessarily the shortest) sequence of operations that transforms one to the other with at most 947 operations.

Thanks for reading, and check back next week!

Sunday, January 27, 2019

A Galois week

Codeforces returned this week with its Round 534 on Tuesday (problems, results, top 5 on the left, analysis). mnbvmar won not just thanks to being the only contestant to solve the hardest problem E, but also thanks to being much faster than his peers on the first three problems, which might've been the key to unlocking the strategy of solving E instead of D. Well done!

TopCoder SRM 748 on Saturday wrapped up the second stage of the race to TCO19 (problems, results, top 5 on the left, my screencast, analysis). tourist was the only one able to solve the hard problem, but he also had the fastest time on both the easy and the medium. Congratulations on the very convincing victory!

The hard problem has introduced me to the concept of nim multiplication which, on one side, allows solving products of coin turning games, and on the other side, together with the nim addition — bitwise xor — induces a finite field of characteristic 2 over the nimbers less than 22n for any n. I find this sudden appearance of finite fields exceedingly beautiful :)

The Wikipedia article implies that for computing the nim multiplication, we just need the following two facts:

  1. The nim product of a Fermat power of two (numbers of the form 22n) with a smaller number is equal to their ordinary product;
  2. The nim square of a Fermat power of two x is equal to 3x/2 as evaluated under the ordinary multiplication of natural numbers.

It took me quite some time to understand how to compute the nim multiplication using those facts, but now I think I got it, so I'll try to explain (also, does anybody have a link to where this is explained nicely? I could not find one).

First, suppose we know the nim products of powers of two. Then we can use the fact that we have a field to compute all other products by representing the multipliers as xors (nim-sums) of powers of two, for example (where all additions and multiplications are the nim ones): 3*6=(2+1)*(4+2)=2*4+2*2+1*4+1*2=8+3+4+2=8+4+1=13.

Now, the above rules allow to multiply Fermat powers of two, but we need to learn to multiply arbitrary powers of two. Here we once again use the binary representation, this time of the exponent, to represent any power of two as a (both nim and ordinary) product of Fermat powers of two, and then rely on associativity of multiplication to rearrange the Fermat powers of two in sorted order. If they're all distinct, then we can go from smallest to largest to learn that their product is equal to their ordinary product according to the first rule above; and if a Fermat power is repeated, then we use the second rule above to effectively decompose the problem into two. If we always apply the second rule to the smallest repeated power, I think we never end up with more than two occurrences of any power in our intermediate computations.

Here's an example: 2048*128=(256*4*2)*(16*4*2)=2*2*4*4*16*256=(1+2)*4*4*16*256=4*4*16*256+2*4*4*16*256=(2+4)*16*256+2*(2+4)*16*256=2*16*256+4*16*256+2*2*16*256+2*4*16*256=2*16*256+4*16*256+(1+2)*16*256+2*4*16*256=2*16*256+4*16*256+16*256+2*16*256+2*4*16*256=4*16*256+16*256+2*4*16*256=16384+4096+32768=53248.

Those two ideas can be combined to obtain a single algorithm as described in the exercise 4 at the bottom of page 14 in this article from 1978.

Thanks for reading, and check back next week!