A run twice week

The 2nd Universal Cup Stage 15: Macau took place last week, but its results were not public when I wrote the last summary (problems, results, top 5 on the left, analysis). Similar to the previous stages, this seems to have originated as an ICPC regional contest, but this time the top onsite team got quite high place 11 on the Universal Cup scoreboard (still with 9 problems, which seems to be a universal constant) — I guess we need to keep an eye at the Peking University team at one of the upcoming World Finals :) Congratulations to USA1 and HoMaMaOvO, the clear top 2 in the overall standings as well, on solving everything!

The 2nd Universal Cup Stage 16: Run Twice followed this Saturday (problems, results, top 5 on the left, analysis). The round featured 11 problems in the relatively new run-twice format (announcement), which I think is an awesome idea that extends the boundaries of what an algorithmic contest problem can be. The new format did not bring a new winner, as team HoMaMaOvO solved everything with an hour to go. Well done!

I did not participate in this round, but I checked out the problems because the topic was so interesting, and I'd like to highlight problem F: your program is executed twice. In the first run, you are given a graph with n=1000 (note that it is not n<=1000, but exactly n=1000) vertices, and 2000<=m<=5000 edges. It is guaranteed that this graph was generated randomly by adding a uniformly random non-existing edge m times. You can make at most 5 changes to this graph, where one change is adding an edge between two vertices not connected by an edge, or removing an edge. The first run of your program ends there. The graph with your changes applied is then shuffled (randomly permute vertices, edges, and ends of an edge), and is given as input to the second run of your program. The trick is that your program is not told whether it is the first run or the second run, and instead needs to detect it itself. In other words, you need to apply such changes in the first run that you'd be able to detect that the graph was changed from a random one in the second run. Do you see a way?

In continuing another great Open Cup tradition, Universal Cup is holding a Prime Contest this and next week. Given the higher amount of Universal Cup rounds, the Prime Contest appears practially infinite with problem numbers going up to 167, and nevertheless 36 out of 39 problems have already been solved, and even more amazingly 26 of those were solved by the same team! There are still 5 days left and 3 problems have not yet been solved, so maybe this is your chance — but remember that those problems are not for the faint-hearted :) You need an Universal Cup login to participate, and I believe you can get one via the registration form.

Codeforces Good Bye 2023 wrapped up the competitive year (problems, results, top 5 on the left). The round was not received well (1, 2, 3), but nevertheless congratulations to ksun48 on being the only one to solve everything and therefore getting a clear first place!

Thanks for reading, and check back in 2024.

An odd knapsack week

Pinely Round 3 on Codeforces took place on Saturday (problems, results, top 5 on the left, analysis). Quite a few people got the first 8 problems correctly, some with more than half of the contest time left, but the last two problems proved to be quite tough to crack. Only zh0ukangyang got problem I right, and only maroonrk got problem H right, therefore earning the first two places. Congratulations!

Quite interestingly, this time there was no contestant who successfuly solved H or I after skipping one of the easier problems (so rainboy sadly scored 0 :(), which goes to show that such strategy looks amazing when it works, but also carries huge risks :)

As for my contest, I wasted way too much time on F and G, and therefore did not spend any meaningful amount of time on H and I.

In problem F, when trying to generalize my solution from F1 to also solve F2 I got a quadratic-time solution that seemed like it could be sped up by using fast convolution; however, I could not immediately see how, and the number of accepted solutions indicated that there is something simpler there. In the end, I got the worst of both worlds: I did not find the simpler solution, but I also did not pull myself together to write down the quadratic formula explicitly on paper. When I did this after the end of the round, I have quickly upsolved it using fast convolution since we were summing up a product of various factorials and inverse factorials of amounts that depend either on u, or v, or on u+v (where u and v are the nested loop variables that yield quadratic running time).

In problem G, I wasted about half an hour when my initial solution got TLE, even though its complexity was O(n). It constructed a suffix array instead of using the z-function though, so I guess the lesson learned here is that for practical purposes the O(n) suffix array construction should be treated as O(nlogn), as I assume the constraints were so high (n=10⁷) precisely to cut off O(nlogn) solutions. In the end I was able to replace the suffix arrays usage with z-function.

Having read maroonrk's solution for H (spoilers, do not click if you want to try solving yourself first!), I regretted a lot that I did not have time left to try solving it as the problem was amazing. Here is the problem statement: you are given an array of size 3*10⁵. In one operation, you can take any segment of this array of even length, and swap the 1st and 2nd numbers in that segment, the 3rd and 4th numbers, and so on. You need to sort the array in at most 10⁶ operations. You do not need to minimize the number of operations. Can you see a way?

In my previous summary, I have mentioned an AtCoder problem: you are given up to 100000 positive integers A_i, each up to 10⁹. Your goal is to split each A_i into two non-negative integer parts A_i=B_i+C_i so that there is no way to choose exactly one of B_i or C_i for each i such that the sum of chosen numbers is equal to exactly half of the sum of all A_i (that sum is guaranteed to be even).

When solving this problem, the first observation I made is that it is in fact hard, likely impossible, to check in a reasonable time if a given split into B_i or C_i satisfies the requirements or not, as it requires solving a pretty large instance of the knapsack problem. This may be the reason that the problem does not require to print a certificate, just a Yes/No answer.

This naturally leads to the following question: for which splits into B_i or C_i we can reasonably easily prove that achieving exactly half is impossible? To make such proof easier, it makes sense to split all even numbers exactly in half such that B_i=C_i: then we know for sure those numbers' contribution to the sum, and there are fewer possibilities to check. However, if all numbers are even and we do this for all numbers, then it would be possible to achieve exactly half of the total sum (in fact, it would be impossible to achieve anything else :)). But then we can do this even split for all numbers except one, and for one number (say, A₁) we set B₁=0 and C₁=A₁. Then we get exactly half from all other numbers, but if we choose B₁ then the sum is slightly less than exactly half of the total, and if we choose C₁ it is greater. Therefore we have solved the problem for the case where all A_i are even (the answer is always Yes).

What can we do about odd numbers? They cannot be split exactly in half, but we can try to build on the above construction: let us split all odd numbers almost in half, such that B_i+1=C_i, and split one number, the biggest one (assume we reorder the numbers and it is A₁), as B₁=0 and C₁=A₁. Now if the amount of odd numbers is less than A₁, then we still cannot achieve exactly half, because if we choose B₁, even taking C_i from all odd numbers will still leave us short of half of the total, and if we choose C₁, we overshoot. There is a slight complication that happens when A₁ is odd, as then we should not count it towards the amount of odd numbers we split almost in half; however, since the total amount of odd numbers is always even (because the sum is even), this does not affect our comparison and we can still compare if A₁ is strictly greater than the total amount of odd numbers.

This criterion was my first submission, however, it got WA. As I did not have any immediate ideas for other situations where achieving exactly half is clearly impossible, I implemented a brute force solution and stress-tested it against this one. The smallest counterexample it produced was: 1, 3, 3, 3. In this case we set all B_i=0 and C_i=A_i and there is no way to achieve the required sum of 5 from some subset of 1, 3, 3, 3. The first idea after seeing this was that divisbility by 3 is somehow a factor; however, quite quickly I realized that we can slightly generalize the construction from the first submission above: we take all odd numbers, sort them, and split them into two parts of odd size. In the part containing the smaller numbers, we set B_i+1=C_i, and in the part containing the bigger numbers, we set B_i+D=C_i, where D is the smallest of those bigger numbers. Now if the size of the part with smaller numbers is less than D, then we always fall short of half of the total if we choose more B_i's than C_i's in the part with the bigger odd numbers, and we always overshoot otherwise.

This solution passed the stress-test against the brute force for small constraints, therefore I submitted it and it got accepted. I did not bother proving it formally since the stress-test was proof enough, but the intuition is somewhat clear: now we say No only if there are at least two odd numbers up to 1, at least four odd numbers up to 3, at least six odd numbers up to 5, and so on until we run out of odd numbers, and the total amount of odd numbers is at least the biggest number. I did not write down all details, but the following method likely works to achieve exactly half in this case: we first go through all even numbers, and then through all odd numbers in decreasing order. If the sum we accumulated so far is bigger than half of total of the numbers processed so far, we take the smaller one of B_i and C_i, otherwise the bigger one. We can now prove by induction that after processing all odd numbers except the x smallest ones, the current sum differs from half of all processed numbers by at most (x+1)/2, which means that in the end it is exactly equal.

Thanks for reading, and check back next week!

A three-step week

The 2nd Universal Cup Stage 13: Shenyang took place last week, but its results were not public when I wrote the last summary (problems, results, top 5 on the left, analysis). The first two places in this round coincide with the first two places in the overall Universal Cup standings, and they were also the only teams to solve 12 problems. So I guess one could say this round went exactly as expected :) Congratulations to USA1 and HoMaMaOvO!

This round used the problemset from an ICPC regional contest, and the best team from that contest is only on place 23 in the scoreboard with 9 problems solved, which underscores how the Univesal Cup gathers the best teams in the world.

The 2nd Universal Cup Stage 14: Southeastern Europe took place this Saturday (problems, results, top 5 on the left, overall standings, analysis). Team HoMaMaOvO got the second place just like last week, but the winner was different: team 03 Slimes got 11 problems solved at just 1:43 into the contest, and therefore had all the time in the world to solve the 12th. Congratulations on the win!

This round has also used the problemset from an ICPC regional contest, but this time the best team from the onsite round placed a bit worse — at place 36, with 9 problems solved.

Finally, AtCoder Grand Contest 065 wrapped up this week (problems, results, top 5 on the left, overall standings, analysis). There was a huge gap in difficulty and in scores between the first four problems and the last two, therefore in this round it could actually be a very good strategy to start with one of the two difficult problems to be able to properly estimate how many easier problems one can squeeze in the remaining time. mulgokizary and newbiedmy executed this strategy successfully to place 3rd and 4th, well done! Of course, it's even better if one can solve the four easier problems and one difficult one, as zhoukangyang and ecnerwala did :) Congratulations to them as well!

The round went quite well for me, in a large part thanks to the fact that I was able to quickly find this page for problem D, and this paper for problem F. However, while the implementation for D is pretty straightforward with the linked formula, one still needs to make a few more steps on top of the linked paper to get F, and I managed to get stuck in those steps: by the end of the round, my solution returned 125405280 instead of 128792160 for n=10 :(

While solving problem C in this round, I followed a quite typical pattern, at least for AtCoder problems: come up with a reasonably simple sufficient but not clearly necessary condition, implement it, submit, get WA, implement a stupid solution and run a stress test, find a case where the solutions differ, come with another, also reasonably simple sufficient but not clearly necessary condition, implement it, run stress test with larger cases, find a bug in the implementation, fix it, pass stress test, submit, get AC :) I think seeing the diffs found by stress test was instrumental for me to discover the correct solution idea. For those who solved this problem during the round or want to upsolve now, were you able to do it without the stress test?

Here's that problem's statement, aptly titled "Avoid Half Sum": you are given up to 100000 positive integers A_i, each up to 10⁹. Your goal is to split each A_i into two non-negative integer parts A_i=B_i+C_i so that there is no way to choose exactly one of B_i or C_i for each i such that the sum of chosen numbers is equal to exactly half of the sum of all A_i.

This round has seemingly concluded (even though a man can hope: maybe one more AGC in 2023 will pop up as a Christmas present? :)) the AtCoder Race Ranking 2023 (top 14 on the left). Therefore it seems that I have barely missed qualifying to the World Tour Finals in Japan. Amazingly, the cutoff for the top 12 did not change at all in this round, as Um_nik has kept his final qualifying place while being outside of the top 30 in the round. It means that even the fourth place would have been enough for me to qualify. Not making a wrong attempt on C (or convincing Gennady to skip this round to increase my chances) would have gotten me the fifth place, but to get fourth I really had to solve either E or F. Well, I will try harder next year, and huge congratulations to the 12 finalists!

In my previous summary I have mentioned a Hacker Cup problem: two players are playing a nim-like game, starting with two piles of stones. In one move, a player first chooses one of the remaining non-empty piles, let's say this pile has k stones. Then they can take between A_k and B_k stones from this pile, and they also must create a new pile with C_k stones (1 <= A_k <= B_k <= k, 0 <= C_k < k). Since 1 <= A_k and C_k < k, this game will eventually terminate, and the player unable to make a move loses the game. Your goal is to find for each size (between 1 and n) of the first of the two initial piles the smallest size of the second initial pile that leads to a losing position, and print the sum of those n sizes. n is up to 2 million.

The first step in solving this problem is pretty straightforward. As the games on each pile are independent, we can use the Sprague-Grundy theorem, therefore we just need to find the nimber for a pile of size k for each k. Denoting this nimber as N_k, from the game rules we get that N_k=mex(N_i⊕N_Ck over all i between k-B_k and k-A_k).

So we need some data structure that can find mex on a range, with the added twist that all numbers on the range are first xored with some constant. Finding things on a range is typically done with a segment tree, but to find mex even without the xor-constant complexity would require to propagate a lot of information along the tree.

The key step to progress further in solving this problem is to actually forget about the ranges for now, and focus on the xor-constant part. Suppose we just have a static set of numbers, and need to answer questions: what is the mex of all those numbers xored with a given constant? In this case it is reasonably clear what to do: we need to determine the mex bit-by-bit from the highest bit to the lowest bit. Suppose we want to find the k-th bit having already found out that the answer is equal to r for bits higher than k, in other words we know that the answer is in range [r,r+2^k+1), and need to tell if it is in range [r,r+2^k) or  [r+2^k,r+2^k+1). Because bitwise xor is applied independently to high and low bits, we simply need to know if there is at least one number missing in our set from the range [r⊕s,r⊕s+2^k), where s is the bits k and higher from our constant. And finding if a number is missing on a range can be done with a balanced tree or again with a segment tree. Note that even though we forgot about the ranges, the ranges have reappeared: instead of ranges on k, we now have ranges on N_k.

Now let us reintroduce the ranges on k. First, let us consider only half-ranges: suppose A_k=1 for all k. Then in the above bit-by-bit solution we need to find out if there is at least one number missing from a given range on a suffix of N_k. This can be done by modifying the segment tree approach: let us use a segment tree that, instead of just remembering if a certain number has appeared or not, will remember is rightmost appearance. Then we can find the minimum of those appearances on the needed range, and compare it to k-B_k. In fact, since all ranges of nimbers that we query are aligned with the powers of two, each query will exactly correspond to one of the nodes in the segment tree, and therefore can be done in O(1) (but an update still needs to touch O(log(n)) nodes).

What to do about the other side of the range on k, in other words when A_k>1? Here comes another relatively standard trick: since we only look at indices up to k-A_k, we could have executed this query when we were processing k'=k-A_k+1, and at that moment this query would be a half-range with only the left boundary, which we can handle using the procedure described above. So we would like to already compute N_k when processing k'=k-A_k+1, however we cannot do that since we might not know N_Ck at that point yet if C_k>k-A_k. This naturally points us towards persistent data structures: we can modify our segment tree to be able to not just query what is the minimum on a range, but to also to query what was the minimum on a range at any previous state of the data structure, in particular when k'=k-A_k+1.

There are several standard ways to do it, one of which is to actually store a tree as a set of immutable nodes with each node pointing to children, and every time we need to change the value in a node we would actually clone the node with the new value instead, together with its path to the root. This way we only create O(log(n)) additional nodes per operation, so the total memory usage is still acceptable at O(n*log(n)), but now since all nodes are immutable we can simply query any old root of the tree to get the minimum on a range at a point in the past.

I think this problem is educational since it has three steps of "unwrapping the present", as we first solve an easier version of the problem and then gradually add back the full complexity. Each particular step is more or less a well-known trick, but one still needs to find which simplifcation of the problem to tackle first, and for that it is vital for those well-known tricks to really be "in RAM", as well as to have a good intuition about what is not solvable at all, so that one can explore many directions and find the correct three-step path. If one has to think for half an hour to solve each particular step, there is really no chance to find the correct sequence of three steps in time, as there will necessarily be other promising directions that won't lead anywhere but waste a lot of solving time.

Thanks for reading, and check back next week!

A 17107 week

TopCoder SRM 851 was their first round after a long while (problems, results, top 5 on the left). Only three contestants got the 1000 right. Out of those, snuke had a small lead after the coding phase despite a resubmit on the 1000, and he managed to extend the lead with an active challenge phase (+2-2). Well done!

Meta Hacker Cup 2023 Final Round was the last but also the most important event of the week (problems, results, top 5 on the left, analysis). The scoreboard was quite exciting to watch during the round, as different people went for completely different orders of tackling the problems (and also for creative ways to avoid thinking too much about cacti!). The order did not matter in the end as only Gennady managed to solve all problems, which was actually necessary for him to claim the first place from Benq who had a better penalty time. Congratulations Gennady on winning the 5th Hacker Cup title!

As I saw the point values for the problems, the optimal strategy seemed obvious: problem A with its 19 total points effectively has weight 2 for the penalty purposes, so assuming the 19 points accurately reflect its difficulty, it is much better to solve it in the beginning. Combine this with the fact that it was a constructive problem, the type I typically enjoy solving, and you can guess what I did for the first 2 hours of the 4-hour round :) I think the main reason it took so long was that I was constantly quite close to a working solution, and therefore it always seemed that I need just one more small trick, so I went for small tricks instead of rethinking the approach. I ended up accumulating a lot of those small tricks: in addition to k->2k and k->2k+1 steps that everyone likely used, my solution also used k->4k-1, k->8k-1, ... (therefore using the A=A-1 primitive that the official analysis dismissed so easily :), and also k->3k and k->3k+2; to accommodate such a wide variety of possible steps, I chose the cells to include into the labyrinth outside of the main path dynamically based on the type of the next primitive I needed.

Even though spending 2 hours on this problem ruined my (mostly theoretical anyway) chances for a good result, I am still grateful to the organizers for not setting the tightest possible constraints and therefore allowing alternative approaches like mine.

One of the problems that I could not crack in the remaining time even though I was very close, and that I think is quite educational despite having a very ugly statement, is Problem E: two players are playing a nim-like game, starting with two piles of stones. In one move, a player first chooses one of the remaining non-empty piles, let's say this pile has k stones. Then they can take between A_k and B_k stones from this pile, and they also must create a new pile with C_k stones (1 <= A_k <= B_k <= k, 0 <= C_k < k). Since 1 <= A_k and C_k < k, this game will eventually terminate, and the player unable to make a move loses the game. Your goal is to find for each size (between 1 and n) of the first of the two initial piles the smallest size of the second initial pile that leads to a losing position, and print the sum of those n sizes. n is up to 2 million.

Thanks for reading, and check back next week for the results of the most important round of December, the last AGC of the year! Thanks to Um_nik now I know that 12 people (up from 8) qualify to the WTF, which means that even the second place will probably do ;)