A Berlekamp-Massey week

TopCoder SRM 824 was the first event of this week (problems, results, top 5 on the left, my screencast, TCO race standings). I had some kind of blackout and could not solve the medium, which in retrospect was quite standard. However, the hard was also quite standard and straightforward for me, while many others failed to get all details correctly, so the end result was not so bad. Still, I could not really compete with Um_nik and mhq who solved all three problems. Well done!

Open Cup has returned from its winter break with the Grand Prix of Kyoto on Sunday (results, top 5 on the left). Team USA1 continued their domination of this Open Cup season, finishing all problems a good hour before any other team, and with just one incorrect attempt to boot. Very impressive!

Our team struggled quite a bit with the two mathy problems H and M, until Google and OEIS came to the rescue. In problem M, I found the answers to a simplified problem in OEIS, noticed a linear recurrence as one of the methods to compute it, and then hypothesized that the answers to the full problem can also be determined using a linear recurrence :) And in problem H, I had to do a quick dive into some mathematical concepts that were new to me.

I have found problem J the most beautiful in this round: you are given a string of length n (n<=200000) with characters +, - and ?, and two numbers a and b. You can replace each ? character with either + or -. Then you need to find a balanced substring of the string, which means a substring of length a+b that has exactly a + characters and b - characters, in any order, and remove it from the string (the parts before and after the substring being removed become adjacent to each other). Then you need to find a balanced substring in the remaining string, and remove it from the string, and so on. You goal is to replace the ? characters in such a way that the number of times you can remove a balanced substring is maximum possible (this number of times will never exceed n/(a+b) since we would run out of characters). How to find this maximum number of times?

In my previous summary, I have mentioned a Codeforces problem: you are given a single integer n. You start with a sequence of numbers 1, 2, 3, ..., n. In one step, you can take any two numbers x and y, and replace them with x+y and |x-y|. Your goal is to make all numbers equal, and you also need to make those equal final numbers as small as possible, and you need to do all this in at most 20n steps.

I was not sure how to even approach this problem, so I started by implementing a brute force solution that found me the answers for all values of n up to 15. The brute force returns that for n=3,4 we can make all numbers equal to 4, for n=5,6,7,8 we can make all numbers equal to 8, and for n=9,10,11,12,13,14,15 we can make all numbers equal to 16. This naturally suggests that we need to target the smallest power of two that is at least n. I did not prove this fact during the contest, but there exists a very simple proof.

Apart from this observation, looking at the way the brute force achieved the goal helped me learn a couple of tricks that are useful for the solution. First of all, when we have a 0, then we can double any number: (0,x)->(x,x)->(0,2x). Second, the solution often makes many smaller powers of two, and then makes them all equal using this trick.

So now we need to convert all numbers into powers of two, not necessarily equal ones. Suppose 2^k is the smallest power of two bigger than n (we assume n is not a power of two, as for that case we can just use the solution for n-1 without touching the number n at all). We can apply the operation to n and 2^k-n, n-1 and 2^k-(n-1), and so on, 2^k-1+1 and 2^k-1-1. This way, we will get many copies of 2^k as sums, and from the differences we will get numbers 2n-2^k, 2n-2^k-2, ..., 6, 4, 2. And we also have the remaining numbers which we did not touch, those are 2^k-1 and 1, 2, ..., 2^k-n-1. 2^k and 2^k-1 are already powers of two so we don't need to do anything. And for the two chains 1, 2, ..., 2^k-n-1 and 2, 4, 6, ..., 2n-2^k-2, 2n-2^k we can just apply the same algorithm recursively: directly for the first chain, and doing a recursive call for 1, 2, 3, ..., n-2^k-1 and multiplying all results by two for the second chain.

This way we will convert all numbers into powers of two not exceeding 2^k. It turns out that for n>=3 at least two of those powers will be equal and less than 2^k, which allows us to use the (x,x)->(0,2x) step to get a zero, and then use this zero to keep multiplying all numbers by two until we have only one zero and many 2^k, and finally use the (0,x)->(x,x) step to get rid of the zero.

Thanks for reading, and check back next week!

A global week

Codeforces Global Round 19 was the only round of this week (problems, results, top 5 on the left, analysis). tourist and Um_nik were pretty close, but Um_nik's two wrong attempts on E have set him back both in terms of points and in terms of contest time, so tourist came out on top. Congratulations!

Also well done to Maksim1744 for being the only other contestant to solve all problems. I have solved problem G at roughly the same time as him, but have more or less given up on solving H in the remaining time, while he persevered and was rewarded with the third place.

I think problem F, while a bit standard, was quite educational, so I encourage you to check it out as a good practice opportnity. However, since the last problem I described in this blog was also of this kind, let me instead focus on the very original problem G: you are given a single integer n. You start with a sequence of numbers 1, 2, 3, ..., n. In one step, you can take any two numbers x and y, and replace them with x+y and |x-y|. Your goal is to make all numbers equal, and you also need to make those equal final numbers as small as possible, and you need to do all this in at most 20n steps. Can you see a way? At least for me, it was quite helpful to experiment on a computer instead of just solving on paper.

Thanks for reading, and check back next week!

A Gomory-Hu week

TopCoder SRM 823 was the only round of this week (problems, results, top 5 on the left, analysis, TCO race standings). neal_wu and ksun48 were leading after the coding phase, but it all went downhill for them during the challenges. First, ksun48, who was less than 50 points away from the first place, made a quick challenge and earned -25, making neal_wu clear first with more than 50-point gap. A couple of minutes later, Kevin earned another -25. Then Neal decided to take the matters into his own hands and got a -25 of his own, which meant that while Kevin was still more than one successful challenge away, SSRS_ now needed just one +50 to take the first place and the 5 TCO race points, which he duly did closer to the end of the challenge phase. Congratulations on the victory! Neal and Kevin made two more unsuccessful challenges each, ending the round with quite bizarre -75 and -100 challenge points respectively.

In my previous summary, I have described a solution to a Codeforces problem. I'm not going to paste it here since it's very long, so please read the previous summary for context :) As the first step of my solution, I'm constructing another tree where the longest path queries become LCA queries, and then construct an inorder traversal of the new tree to answer LCA queries via RMQ queries.

tourist has pointed out this awesome comment to me, which shows that I did not really have a full understanding of what's going on when writing my solution. Indeed, let us look at the construction process of the new tree more closely and forget about future LCA queries for a second, just trying to keep the property that in the new tree the largest edge weight between any two vertices is the same as in the old tree. Then we can see that whenever we attach two subtrees to a newly created node, we don't really have to use the roots of the subtrees for that, and can use any node instead (because all edges within the subtrees have smaller weight than the currently processed edge, it does not matter which within-subtree edges will end up being used for the paths between the subtrees). And this allows us to keep all subtrees as chains, and connect them to form bigger chains, ultimately creating one big chain.

So it turns out that for any tree, we can construct a chain on the same vertices such that the maximum edge weight on the path between any two vertices is the same in the tree and in the chain, and of course the latter can be found using range-maximum queries. This chain is more or less equivalent to the inorder traversal of the auxiliary tree that was built in my solution, but I think constructing it explicitly is more beautiful and demonstrates a better understanding of the mechanics of the problem.

In an attempt to demonstrate an even better understanding of the mechanics, it seems to me that this construction is somewhat related to the Gomory-Hu construction. In fact, this construction seems to suggest that the Gomory-Hu tree can always be replaced by an equivalent Gomory-Hu chain! However, there seems to be no mention of a "Gomory-Hu chain" on the Internet, so I'm probably missing something here?

Update: Maxim Babenko has clarified the matters here: in the Gomory-Hu tree, for any pair of vertices not just the size of the minimum cut between them is equal to the size of the minimum cut in the original graph (as Wikipedia claims), but also the minimum cut itself (as a partition of the vertex set into two). In a Gomory-Hu chain the size of the cut is indeed still the same, but not the cut itself.

Thanks for reading, and check back next week!

An AlphaWeek

Codeforces Round 768 on Thursday was the first event of last week (problems, results, top 5 on the left, analysis). Um_nik has solved the hardest problem F so much faster than everybody else that his gap at the top of the scoreboard is enormous, almost as if he has solved a seventh problem :) Very impressive!

CodeChef January Lunchtime 2022 followed on Saturday (problems, results, top 5 on the left, my screencast, analysis). I haven't solved IOI-format contests for quite some time, but I have dived right in, taking advantage of the fact that there is no penalty for incorrect submissions and wasting way too much time waiting for submission results :) For this reason, or maybe because I just had too many small bugs to find and fix, gennady.korotkevich and maroonrk were out of reach, getting to 500 points much faster. Well done!

In my previous summary, I have mentioned a Codeforces problem: you are given a tree with vertices numbered from 1 to n, initially all colored white. The tree edges have weights. You need to process a sequence of queries of three types:

1. Given l and r, color all vertices with numbers between l and r black.
2. Given l and r, color all vertices with numbers between l and r white.
3. Given x, find the largest edge weight in the union of the shortest paths from x to all black vertices.

Both the number of vertices and the number of queries are up to 300000.

The first step in solving this problem is relatively standard: let's learn to effectively find the largest edge weight on a path in a tree. We will build an auxiliary new tree where the inner nodes correspond to the edges of our tree, and the leaves correspond to the vertices of our tree. We start by having just n independent leaves. Then we iterate over all tree edges in increasing order of weight, and for each edge we find the new trees containing its ends, then make a new tree vertex corresponding to this edge and make the two trees we found its children. This can be accomplished using a disjoint set union data structure.

You can see an example of an initial tree and a new tree corresponding to it on the right. Now, it turns out that the edge with the largest weight between any pair of vertices in the initial tree corresponds to the least common ancestor of those vertices in the new tree.

So in the new tree, the query of type 3 can be seen as finding the shallowest least common ancestor between the given vertex x and the black vertices, and it's not hard to notice that if we write down the vertices of the new tree in dfs in-order (in a similar fashion to how LCA is reduced to RMQ), then we just need to find the first and last vertices from the set {x, black vertices} in this order, and take their LCA.

Now we are ready to turn our attention to the queries of type 1 and 2. Consider the array where the i-th element contains the in-order traversal times of the i-th vertex of the original tree in the new tree. Then in order to answer queries of type 3, we need to be able to find the minimum and maximum value in this array over all black vertices. So, we need a data structure that supports the following operations:

1. Given l and r, color all vertices with numbers between l and r black.
2. Given l and r, color all vertices with numbers between l and r white.
3. Find the minimum and maximum value of a_i among all i that are colored black.

Given the range update and range query nature of this subproblem, it is reasonable to use a segment tree with lazy propagation to solve it. Indeed, the AtCoder library provides a general implementation of such data structure that allows one to plug an arbitrary operation inside it. You can check out the documentation for the details of how to customize it, but in short we need to come up with a monoid and a set of mappings (in effect, another monoid) acting on the elements of the first monoid in such a way that the distributive law applies, the range update is applying a mapping to all elements from a range, and the range query is multiplying all elements in a range in the first monoid.

This all sounds abstract, fine and dandy, but how to put our real problem into these algebraic terms? First of all, let's come up with the second monoid, the one that corresponds to the range updates (queries of type 1 and 2). This monoid will have just three elements: neutral, white and black, and the multiplication in this monoid will simply be "if the left argument is not neutral, then take it, otherwise take the right argument", which makes sense since the last color applied to a vertex overrides all previous ones.

Now, what should the first monoid be, the one that corresponds to the range queries? Since we need to find the minimum and maximum value of all elements that are colored black, it's logical to first try to have an element of the monoid store those minimum and maximum, with the natural operation that takes the minimum of the minimums and the maximum of the maximums.

However, it turns out that we can't make the whole system work: how would a "black" range update act on such a pair? It turns out we're missing information: the new maximum of all black elements should be equal to the maximum of all elements, because all of them are colored black after the range update, and we don't store and propagate this information yet.

So here's our second attempt at the range query monoid: its element stores four numbers: the minimum and maximum values of black elements in the corresponding segment, and the minimum and maximum values of all elements in the corresponding segment. The operation is also defined naturally, and we now have enough to define how "black" and "white" range updates act on it.

To summarize, both monoids that we use in our lazy segment tree are not very common:

1. One where elements are quadruples of numbers, with the operation taking minimum of two numbers and maximum of the two others.
2. The other with just three elements and a weird multiplication table.

I realize that this explanation is very abstract and can be hard to follow. Here's an excerpt from my submission that defines the lazy segtree, maybe it will help:

1. struct State {
2. int minOn = INF;
3. int maxOn = -INF;
4. int minAll = INF;
5. int maxAll = -INF;
6. };
7.  
8. State unitState() {
9. return {};
10. }
11.  
12. State combine(State x, State y) {
13. State r;
14. r.minOn = min(x.minOn, y.minOn);
15. r.maxOn = max(x.maxOn, y.maxOn);
16. r.minAll = min(x.minAll, y.minAll);
17. r.maxAll = max(x.maxAll, y.maxAll);
18. return r;
19. }
20.  
21. State apply(int x, State s) {
22. if (x == 0) return s;
23. if (x == 1) {
24. s.minOn = s.minAll;
25. s.maxOn = s.maxAll;
26. return s;
27. }
28. assert(x == -1);
29. s.minOn = INF;
30. s.maxOn = -INF;
31. return s;
32. }
33.  
34. int combine2(int x, int y) {
35. if (x != 0) return x; else return y;
36. }
37.  
38. int identity() {
39. return 0;
40. }

...

1. 
   

atcoder::lazy_segtree<State, combine, unitState, int, apply, combine2, identity> lazytree;

I was pretty happy with myself when I figured this out, even though that maybe just implementing a lazy segtree without explicit mathematical abstractions might've been faster :)

Finally, it turns out that last week the submissions (1, 2, 3) generated by AlphaCode were submitted to Codeforces. I got to take a look at them a couple of days before the publication, but I was not involved in any other way, so I was just as impressed as many of you. Of course, I think this is just the first step and we're still very far from actually solving problems with ML models.

I found this submission to be the most helpful to understand the current state of affairs: the part before "string s;" is quite meaningful, and the model had to have a decent understanding of the problem statement to generate that loop. However, I cannot see any logical justification of the loop after "string s;", which seems to be a pretty arbitrary loop :) The reason the whole solution still works is that after the first part, in case the length of the result string is n-1 we need to append any of the two characters a, b to it, and an arbitrary loop can generate an arbitrary character.

This solution seems to suggest that the model can translate instructions from the problem statement into code implementing them, and also sometimes make small logical steps by the virtue of statement-guided random exploration. While this seems enough to solve easy Div 2/3 problems, I think the model needs to improve a lot to generate a solution of the type that I'd appreciate enough to mention in this blog :)

Nevertheless, this has still advanced the state of the art by leaps and bounds, so congratulations to the AlphaCode team!

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