Best problems of 2017

I have reviewed all problems I've highlighted this year in my blog, and also the problems sent by the readers in response to my question — thanks a lot for your input! I've distilled everything to a shortlist of five problems (in chronological order):

• The Open Cup problem about interactively proving the pigeonhole principle, by tunyash, with solution in this post.
• The AtCoder problem about moving two chips on a subset of a DAG, by sugim48, with solution in this post.
• The IPSC problem about picking optimal sequences of red and black cards to get the first match, by misof, with solution in this post.
• The AtCoder problem about assigning numbers to shared vertices of two trees so that all subtrees sum to +-1, by maroonrk, with solution in this post.
• The Open Cup problem about interactively exploring a maze on Mars with a communication delay, by Gassa, discussed in this post. 

What is the best problem of 2017?

As usual around New Year, snarknews is hosting the Prime New Year contest, which consists of problems given at top-level team competitions in 2017 but not solved by anybody there. If you like real challenge and don't have much to do during the holidays, here's your link :)

Guten Rutsch!

A sparse week

This week had the now traditional last contest of the year: Good Bye 2017 at Codeforces (problems, results, top 5 on the left, analysis, my screencast). The hardest problem H, after removing some layers, ended up being about finding a proper vertex coloring for a graph with n<=23 vertices with the smallest number of colors. My first thought was: surely for such classical problem the best approaches are well-known? However, it turned out that the algorithms I could remember were a O(3ⁿ) subset dynamic programming and various heuristics to speed up backtracking, both of which seemed too slow. Thanks to this paper I have now learned how to do this in O(n*2ⁿ), see point 4.2 "Inclusion-exclusion". Always nice to discover better approaches to classical problems!

In my previous summary, I have mentioned a TopCoder problem: you are given n=2000000 tasks, to be done in m=2000 days, at most one task per day (so most of the tasks will end up not being done). For each task you know three numbers: the segment of days when it can be done (from l_i to r_i), and the profit c_i from doing it. You need to pick the task to be done in each day in such a way that the total profit is maximized.

This can be naturally viewed as a weighted maximum matching problem, which thanks to the transversal matroid can be solved by trying to add tasks to the matching in decreasing order of profit, trying to find the augmenting path each time, and only resetting the "visited" state of each vertex once the matching is increased (this is called "Kuhn's algorithm" in the Russian-speaking community, but I couldn't find an authoritative link for it). Since the matching is only increased m times, we process each edge of the graph at most m times. The problem is that we have O(n*m) edges, so the total running time seems to be O(n*m²). However, we can notice that for each task that we end up not adding to the matching we process its edges only once (since we will never visit it in subsequent iterations), so the number of actually revisited edges is O(m²), and the running time is only O(n*m+m³), which is of course still too slow.

But now we can use another relatively standard trick: let's reduce the number of "active" edges from O(m²) to O(m*logm) in the following manner: instead of a matching problem we'll now have a flow problem, and we'll add auxiliary vertices between left and right parts. The vertices will correspond to segments. First, we'll pick the middle point b=m/2, and add vertices corresponding to segments [1,b], [2,b], ..., [b-1,b], [b,b], and infinite capacity edges in this manner: [1,b]->[2,b]->...->[b,b]; [1,b]->1; [2,b]->2; ..., [b,b]->b. The idea is that if we add an edge from some vertex in the left part to a segment [a,b], then the flow can then go to any vertex in the right part between a and b using those infinite edges, and only to those vertices. We handle the other half in a similar way: [b+1,b+1]<-[b+1,b+2]<-...<-[b+1,m-1]<-[b+1,m]. These two sets of segments already allow to handle any task that can be done in days b and b+1 using only two edges: to [l_i,b] and to [b+1,r_i].

We can then apply the same procedure recursively to segments [1,b] and [b+1,m]: for example, we'll pick the middle point c=b/2, and build the auxiliary vertices [1,c]->[2,c]->...->[c,c] and [c+1,c+1]<-[c+1,c+2]<-...<-[c+1,b], and so on. Overall we'll have logm sets of m auxiliary vertices each (one per level of recursion), with two outgoing edges for each vertex, and every task can now be handled with at most two edges to auxiliary vertices instead of O(m) edges to the right part. This approach resembles the centroid decomposition of a tree when applied to a chain; we could also have used the sparse table to achieve the same result.

Now our graph has O(mlogm) active edges, and additional O(n) edges that are visited only once, so the total running time is O(n+m²*logm), which is fast enough.

That's it for the contests of 2017 — thanks for reading, and check back tomorrow (hopefully) for the best problems of 2017!

A quadratic week

Last week had a relatively high density of contests, so much that two of them collided: Codeforces Round 453 and TopCoder SRM 726 took place at the same time on Tuesday. The Codeforces round started 25 minutes earlier, so we'll begin with it (problems, results, top 5 on the left, analysis). dotorya had chosen a seemingly suboptimal order to solve the first four problems, as A and B required disproportionately much time relative to their value, but he was faster than the competition and thus still ended up in first place — well done!

TopCoder SRM 726 at roughly the same time attracted the second half of the community (problems, results, top 5 on the left, my screencast). The hard problem has proved decisive: you are given 2000000 tasks, to be done in 2000 days, at most one task per day (so most of the tasks will end up not being done). For each task you know three numbers: the segment of days when it can be done (from l_i to r_i), and the profit c_i from doing it. You need to pick the task to be done in each day in such a way that the total profit is maximized. This is naturally reduced to a weighted maximum matching problem, but surely it will time out with 2 million vertices in the graph — or will it?

Codeforces ran another round, Round 454, on Saturday (problems, results, top 5 on the left, analysis). All problems were tractable this time for moejy0viiiiiv and Radewoosh, and in case of the former with 30 minutes to spare. Congratulations on the victory!

In my previous summary, I have mentioned an Open Cup problem: you are given an integer n with at most a million digits. You need to determine if it's a perfect square or not. You don't need to actually find the square root.

As is often the case in problems with a Yes/No answer, it suffices to find an algorithm that always finds one of the two answers correctly, and the other with a certain probability that is greater than zero. We can then apply it repeatedly until the probability of not finding the correct answer is exponentiated to become essentially zero.

Let's pick a prime number p. If n is a perfect square, then n mod p is always a quadratic residue. If not, then assuming p is picked randomly the probability of n mod p being a quadratic residue is roughly 0.5, since roughly half of all numbers mod p are quadratic residues (this is merely handwaving; can anyone prove this probability estimation formally?).

So we can pick, say, 30 random prime numbers, and check if n is a quadratic residue modulo each of them. If at least one says no, then the overall answer is no, otherwise it's yes. Checking if a number is a quadratic residue modulo p is done by checking if n^(p-1)/2=1 (mod p).

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

A Newton week

The Dec 11 - Dec 17 week contained the last Open Cup round of the year: the Grand Prix of Peterhof (problems, results, top 5 on the left). The deciding problem H required the ability to find the exponent a formal series fast, and the teams that were able to do so claimed the first two places — congratulations to the Moscow IPT team and to SPb Havka-papstvo!

I found the relatively easy problem J very nice. You are given an integer with at most a million digits. You need to determine if it's a perfect square or not. You don't need to actually find the square root. Can you see how to get this problem accepted on the 8th minute of the contest?

Thanks for reading, and check back soon!

A correlation week

The Dec 4 - Dec 10 week was another of the calm ones, so let's use this post to discuss the interactive NEERC problem I mentioned in the previous one: you work with a device that takes an a as input and computes a^d mod n using the following pseudocode:

1   modPow(a, d, n) {
2     r = 1;
3     for (i = 0; i < 60; ++i) {
4       if ((d & (1 << i)) != 0) {
5         r = r * a % n;
6       }
7       a = a * a % n;
8     }
9   }

However, instead of receiving the result of the computation, you only receive the time it took the device to execute it, which is computed in the following way: only the multiplications on lines 5 and 7 take nonzero time, and multiplying x by y modulo n takes (bits(x)+1)*(bits(y)+1), where bits(x) is the length of the binary representation of x without leading zeroes.

You know the number n but not the number d, and your goal is to find d after sending at most 30000 requests to the device. You know that n and d were chosen in the following way: first, two prime numbers p and q with bits(p)=bits(q)=30 were picked independently and uniformly at random. Then n was computed as p*q. Then the number m=(p-1)*(q-1) was computed. Then d was picked uniformly at random between 1 and m-1 inclusive, such that it is coprime with m.

The official analysis has a pretty detailed description of the intended solution starting from page 8, so let me just recap it here briefly;

• We're going to just send 30000 random queries.
• Lowest bit of d is always 1, let's determine the second lowest.
• If it's also 1, then we multiply a by a², otherwise we don't.
• For queries where a and/or a² have less bits than usual, the overall modPow time will also be less than usual, but only on average, so we can't just tell from one a.
• However, the correlation between the time to multiply a by a² and the overall modPow time over all 30000 queries can tell us this bit with extremely high certainty.
• We can then determine the next bit in the same manner, and so on.
• This Wikipedia page also describes the same idea.

This solution is very easy to code and generalizes well to bigger constraints, but it might be hard to intuitively feel if 30000 queries gives enough certainty. Egor has suggested another approach which is a bit harder to code but easier to believe that it works (but we have not actually tried to implement it): instead of sending random queries, we will send queries such that one repeated square of them is very small modulo n, say, at most 10 bits. Such a query will give much more signal on whether this repeated square is used in the multiplications, since multiplying 10 by 60 bits, compared to multiplying 60 by 60 bits, is about 3000 nanoseconds faster, and standard deviation of modPow computation time if we just feed it random inputs is on the order of 1700, so the middle point is roughly one standard deviation away from each expectation. If we try, say, 49 such numbers for every bit, then we'll have seven standard deviations and will always guess correctly, so we need only 60*49 which is about 3000 queries to find all bits.

Of course, finding a number that has few bits in a certain power modulo n is a hard task in itself, but here n is small enough that we can factorize it using Pollard's rho algorithm, and after that we just need to invert the said power modulo phi(n) to be able to find the root of this power of any number, including ones with few bits.

Thanks for reading, and check back for more!

A timing week

The Nov 27 - Dec 3 week started with TopCoder SRM 724 (problems, results, top 5 on the left). snuke, sugim48 and Swistakk had more coding phase points but this round was ultimately decided during the challenge phase, as the easy problem allowed for a lot of incorrect approaches.

On Saturday, Codeforces Round 449 gave ACM ICPC 2017-18 NEERC contestants the last chance to practice, although I'm not sure if many of them did (problems, results, top 5 on the left, analysis). In a somewhat unusual outcome, MrDindows has won the round with less problems than the second place, thanks to an extremely fast solution to the hardest problem — congratulations on the victory!

He's managed to pull this off thanks to being able to squeeze a "naive" quadratic solution under the time limit in a problem with n=100000. This is no small feat, as demonstrated by the fact that just one other contestant was able to do it at all, even within the full two hours. Thankfully he has explained how he was able to achieve this, so that we all can learn the tricks and/or deepen our understanding of compilers!

On Sunday, the said ACM ICPC 2017-18 NEERC took place in St Petersburg (problems, results, top 5 on the left, analysis, broadcast in Russian). The competition was very tight, and Moscow IPT 1 team has earned the first place with 10 minutes to go, in no small part thanks to solving the tricky problem K with just two attempts, whereas the only two other teams to get it accepted required 10 and 14 attempts. Congratulations!

I have set problem H for this round, which was unfortunately the only one left unsolved. This is an interactive problem where you work with a device that takes an a as input and computes a^d mod n using the following pseudocode:

1   modPow(a, d, n) {
2     r = 1;
3     for (i = 0; i < 60; ++i) {
4       if ((d & (1 << i)) != 0) {
5         r = r * a % n;
6       }
7       a = a * a % n;
8     }
9   }

However, instead of receiving the result of the computation, you only receive the time it took the device to execute it, which is computed in the following way: only the multiplications on lines 5 and 7 take nonzero time, and multiplying x by y modulo n takes (bits(x)+1)*(bits(y)+1), where bits(x) is the length of the binary representation of x without leading zeroes.

You know the number n but not the number d, and your goal is to find d after sending at most 30000 requests to the device. You know that n and d were chosen in the following way: first, two prime numbers p and q with bits(p)=bits(q)=30 were picked independently and uniformly at random. Then n was computed as p*q. Then the number m=(p-1)*(q-1) was computed. Then d was picked uniformly at random between 1 and m-1 inclusive, such that it is coprime with m.

Surprisingly, just knowing the time the computation takes for a few requests is enough to extract the value of d. Can you see how to do it?

Thanks for reading, and check back later today!

A directly opposite week

Code Festival 2017 onsite for university students and recent graduates ran by AtCoder was the biggest event of the Nov 20 - Nov 26 week. It consisted of multiple rounds, but the main and rated one was the Final (problems, results, top 5 on the left, parallel round results, analysis). The problemset has provided a lot of variety, and the people at the top had quite different sets of problems solved. tourist was quite a bit faster than others — big congratulations on the victory!

The Open Cup continued its weekly cadence with the Grand Prix of Europe on Sunday (problems, results, top 5 on the left, CERC results on the same problems). Team japan02 had 10 problems solved even before the last hour, but could not make further progress and allowed ITMO 1 to steal the victory with two minutes to go — congratulations to both teams solving 10 problems, and to the Warsaw team who got 10 at the onsite round, also with a last-minute accepted submission!

In my previous summary, I have mentioned an interactive Open Cup problem happening on the faces of a cube with each face divided into n times n cells (n<=300). You are located on some cell on some face of the cube, facing one of the four cardinal directions, and your goal is located on some cell on some face of the cube, but you don't know where you are located and where the goal is located. All you can do is to issue commands left, right or forward, with the first two causing you to rotate in place by 90 degrees, and the last one causing you to move one cell in the direction you're facing, with moving through the sides of the cube handled in the natural way. For each move forward, the system tells you whether your new cell is closer, farther or at the same distance from the goal as the old one. The distance is defined as the Euclidean distance between the centers of the cells. You need to stop moving at the goal cell after using at most 100n commands.

The solution that we got accepted looked like this: first, we try to move closer to the goal whenever we can, until we reach a cell from which all four moves don't give us a "closer" reply. This can be coded with a simple loop without the need to remember the coordinates or to even represent the sides of the cube, and will always converge in O(n) steps.

Then, we're either in the goal cell or in the cell directly opposite it on the opposite face. We don't know the size of the cube, but even without it in order to transition from one to the other we can walk forward while we're not seeing a "closer" answer, and then keep moving forward while we're seeing "closer" answer. If we were in the opposite cell, we will reach the goal. If we were in the goal, then we'll either be in the opposite cell, or in the goal again after making a full loop. To distinguish the cases, we can compare the number of moves in the "not closer" state to the number of moves in the "closer" state. In case the former is bigger than the latter, we started our forward walk in the goal, and we will undo all those moves to go back to the goal. In case the latter is bigger, we're done.

It takes some case studying and convincing oneself that this approach works in various corner cases as well, but after that the actual implementation is just a few lines.

Thanks for reading, and check back for more!