A Sokoban week

Codeforces Round 889 opened the competitive programming weekend (problems, results, top 5 on the left, analysis). Radewoosh was the fastest to solve the first six problems, and even though the last one did not budge, it was enough for the first place. He was also able to hack his own, tourist's and one of the reference solutions for D after the round, further demonstrating his great understanding of the problems. Congratulations!

I liked the problemset a lot, because it felt like a problemset that I could have come up with myself :) The solutions for the harder problems involved a fair bit of experimentation, and more generally I did not get the (quite regular these days...) feeling of "how on Earth could one think of this setting for a problem or this solution idea", both the problem settings and the solution ideas seemed pretty approachable. Kudos to TheScrasse and dario2994!

I ended up in place 42 instead of place 10 because of an off-by-one error in B: I used bitset<200001> instead of bitset<200002>. I'm actually curious why this out-of-bounds access (querying element 200001 of bitset<200001>) causes a runtime error. Doesn't the implementation use an integer number of bytes, and therefore the actual number of bits has to be at least 200008?

The reason I could not go higher was my inability to solve problem C, which caused me to focus on problem F which I could actually solve and was trying to code. I've implemented a bruteforce, and printed all points for which the distance differed from the one obtainable from the obvious bounds (has to have the same parity and the sum of coordinates less than the sum of all jumps). For example, here is the list of points I got which have distance 12 but just according to parity and the sum of coordinates would have had a smaller distance:

Looking at the list of points, I've noticed a pattern: the points can be split into groups where some coordinates are fixed small ones (for example the group starting with 2 2 ...), and the remaining coordinates take all possible combinations with a given sum or within a given range of sums. This makes sense, as essentially we're saying that achieving a certain combination of small coordinates potentially wastes some of the small moves and may also take away some flexibility from the remaining coordinates because the small moves are not available there. And it seems that the largest "small" coordinate to take into account is 6, based on the point 1 6 6 51.

So what I tried to do during the round is to find the smallest and largest sum of remaining coordinates for each possible set of small coordinates for the first 15 moves, assume that all possible combinations of large coordinates between those bounds are valid, and further assume that the bounds just move by (s+1)+(s+2)+(s+3)+(s+4) when going from s moves to s+4 moves. It seemed logical to assume the same structure between s and s+4 because of how the parities of s*(s+1)/2 change. I could not finish coding the part that counted the actual answer to the problem (taking the given parallelepiped into account).

When I did finish coding it after the contest, it turned out that there were also two flaws in the above hypotheses. First, not all combinations of large coordinates with the sum between the smallest and the largest sum are valid. It turns out that for each particular sum, either all combinations with this sum are valid, or all are not, and the invalid sums are always close to the boundaries. It makes sense in retrospect since if we have spent, say, 1 and 2 on the small coordinates, then there is no way to achieve the sum of all others minus 1 or minus 2 with the rest, but we can achieve minus 0 and minus 3. It also turns out that the lower and upper bounds do not shift by the same amount when going from s to s+4, instead the lower bound moves slower, because the segment expands. This also makes perfect sense in retrospect, as s*(s+1)/2 grows non-linearly. Overall, finishing the code, then finding and fixing those two flaws took me about an hour after the contest. So I was not that close to getting it accepted during the round, but at least I was moving in the right direction :)

Here is problem C, which I had no idea how to even approach during the round, but which has the most beautiful solution: you have a set S of integers between 1 and M (M<=500). In one operation, you pick an element of the set uniformly at random, and increment it by 1. If the incremented element coincides with another element of the set, we keep only one copy, so the size of the set decreases by 1. If the incremented element exceeds M, we discard it, so the size of the set also decreases by 1 in that case. We are given the starting set S, and need to find the expected number of steps before it becomes empty.

Wow, this may be the longest I have ever written about one contest, and I haven't even started talking about problem E which stirred some controversy. As I said before, I quite liked the round :)

AtCoder Grand Contest 063 wrapped up the week on Sunday (problems, results, top 5 on the left, analysis). Huge congratulations to zhoukangyang for solving five problems — so far I cannot imagine how this is possible :)

I've earned a respectable 345th place by solving two problems, and even that was not easy — I was stuck with a wrong (and more difficult to implement) approach in B for quite some time. I had no idea how to solve C after thinking about it for a long time, and I could not solve E or F after thinking about them for a bit. I solved D relatively quickly, but spent more than an hour implementing it. I had the solution for ready about 20 minutes before the end, but could not find all bugs in time.

Well, let's hope the bad results will all be spent during the regular AGCs and I will get to shine at the World Tour Finals in Tokyo in September :)

In following this post's tradition, here is problem C that I had no idea how to solve during the round: you are given N<=1000 pairs of integers (A_i,B_i), each integer between 0 and 10⁹. In one operation, you choose two integers x<y between 0 and 10¹⁸, and replace each A_i with (A_i+x) mod y (note that you apply the same x and y to all A_i). You need to make it so that A_i=B_i for all i after at most N operations, or report that it is impossible. 

In my previous summary, I have mentioned an EGOI problem: you are given a HxW grid (H,W <= 50), where some unknown cell of the grid contains an obstacle: a box that cannot be moved. You can send a robot onto the grid in order to determine the location of the box. In one visit, you give the robot a program consisting of characters <, >, ^ and v. The robot starts the visit at the cell (0,0), and then executes your program (> corresponds to moving one cell right, and so on). If a certain move is not possible, either because it would cause the robot to move outside the grid, or because the robot would end up in the cell with the obstacle, the corresponding command is ignored and the execution of the rest of the program continues. You do not observe the robot's movements; instead, you only receive the final coordinates of the robot after executing all commands from the program given for the visit. In the next visit, the robot will start from the cell (0,0) again. To get the full score in this problem, you have to determine the location of the box in just 2 visits. Bonus points (not really) if the total number of commands used throughout all visits is H*W+O(H+W).

When I was thinking about this problem, the key idea to deal with the unknown location of the box was to find such a sequence of moves so that if we have already found the box, then we would stay in the same place, and if not, we would continue looking for it. For example, suppose the box is directly to the left of the robot, and the grid boundary is reasonably far away. Then after performing the sequence of moves v<^>^ the robot returns to the same place, since the ^ move in the middle is blocked by the box. However, if there is no box next to the robot, performing this sequence would result in the robot moving one cell up. We can construct similar sequences for moving one cell down, to the left and to the right, while keeping the property that if the box is directly to the left of the robot, the robot stays in place.

This allows us to go looking for the box, and if we approach it from the right, then we will stay next to it forever, which allows to determine the location of the box from the final location of the robot by just subtracting 1 from the column.

If we know that the box is not on the boundary of the grid, then we can actually determine its location in just one visit: first we go right W-1 times, then move down once, so that we are in the cell (1,W-1). If the box is in the cell (1,W-2), then we are already directly to the right of it, as we need for the above approach. So from this point on we move only using the special sequences mentioned above, to avoid losing the box if we have already found it. First we use the "down" sequence H-3 times, so that if the box is in the column W-2, we find it and stick to it. Then we use the "left" sequence once, then the "up" sequence H-3 times, then the "left" sequence once, and so on.

How do we deal with the boundary? Since the boundary has not so many cells, my approach was to try different ways of going through those cells, and to see if the final location will tell us enough information if one of those cells contained an obstacle. After a couple of experiments, the following approach bore fruit: during the first visit, we go right W-1 times, then down H-1 times, then left W-2 times.

If there was an obstacle in row 0, we hit it when going right, so we went right at most W-2 times, and therefore we end up in the cell (H-1,0). If there was an obstacle in cell (R,W-1) for any R>0, we hit it when going down, so we end up in the cell (R-1,1). If there was an obstacle in cell (H-1,C) for any 0<C<W-1, we hit it when going left, so we end up in the cell (H-1,C+1). Finally, if we did not hit any obstacles we end up in the cell (H-1,1).

It means that if the obstacle was on the right or bottom boundary, we already know its location, if it's on the top boundary, we know it's there but don't know the exact location, and if it's on the left boundary or inside the grid, we still do not know anything. Dealing with the top boundary is easy: during the second visit we just go right W-1 times and see where we stop.

Now we just need to deal with the case where the obstacle is inside the grid or on the left boundary. We have described the approach for the obstacle inside the grid above, but one can notice that it also works for the left boundary if we end up walking through column 1 using the "down" sequences. This happens automatically if W is even, and if W is odd, we can change the direction once to achieve this, for example we can start from (H-2,W-1) instead of (1,W-1) in the very beginning. Therefore we can find the box during the second visit in this case as well.

This solution uses about 5*H*W moves, because our sequences for "down" and "up" have 5 moves each. However, one can process the "down" and "up" moves in batches: to move up many times, one can do v<^^^...^^^>^, which brings the number of moves per cell of the grid to 1, notwithstanding a linear number of additional moves: H*W+O(H+W) (the number of moves during the first visit is linear, so it does not change anything). I like it because it's asymptotically optimal: it is not hard to prove that we must try to enter each cell except maybe one at least once, so we need at least H*W-2 moves in any solution.

A few days later, I've noticed a different way to look at my solution: if we forget about the boundaries of the grid for a second and assume it is infinite (but the box is still within the given rectangle), then under certain assumptions the problem is equivalent to the following: the box is actually movable (like in the Sokoban game), and we need to bring it to a concrete location no matter where it starts. To see this eqivalence, we can say that every time we try to move towards the box and can't, we can shift the coordinate system by 1 instead, which means that the immovable box has effectively moved :) And I think the solution is much easier to find in this equivalent formulation.

Note that the author's solution is completely different: it needs to divide the grid into two halves! However, it also has the property of using only H*W+O(H+W) moves in total. Did you end up using an approach that differs from both?

Thanks for reading, and check back next week!

An EGOI week

EGOI 2023 in Lund, Sweden was the main event of the week (problems, results, top 5 on the left, discussions). Congratulations to all participants and especially to the medalists!

This was the third overall and the second onsite edition of the European Girls' Olympiad in Informatics, and I'm very happy to support this great event. I was onsite as a problem author, but my problem did not end up being used for the competition, therefore my contribution this time was not very significant. Still, being there and feeling the awesome onsite programming contest atmosphere again finally gave me enough motivation to restart this blog :) I was also very impressed with Lund, even though we mostly explored its playgrounds.

Of the problems that did make it to the problemset, I'd like to highlight problem C from the first day: you are given a HxW grid (H,W <= 50), where some unknown cell of the grid contains an obstacle: a box that cannot be moved. You can send a robot onto the grid in order to determine the location of the box. In one visit, you give the robot a program consisting of characters <, >, ^ and v. The robot starts the visit at the cell (0,0), and then executes your program (> corresponds to moving one cell right, and so on). If a certain move is not possible, either because it would cause the robot to move outside the grid, or because the robot would end up in the cell with the obstacle, the corresponding command is ignored and the execution of the rest of the program continues. You do not observe the robot's movements; instead, you only receive the final coordinates of the robot after executing all commands from the program given for the visit. In the next visit, the robot will start from the cell (0,0) again. To get the full score in this problem, you have to determine the location of the box in just 2 visits. Can you see how to do it? Bonus points (not really) if the total number of commands used throughout all visits is H*W+O(H+W).

Codeforces Round 887 wrapped up the week (problems, results, top 5 on the left, analysis). Even rainboy was not able to solve the last problem, but the remaining five provided enough of a challenge even for the top participants. Rebelz was a bit faster but made one wrong submission on E, which proved decisive as it dropped them two points behind jiangly. Congratulations to both on the great performance!

As this blog has been dormant for quite some time, it is a good time to ask: what do you think about the format? Do you have suggestions on what I should remove, add, or do more often? Of course, I don't promise to follow the suggestions, but I will consider :)

Thanks for reading, and check back next week!

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.

An incremental week

TopCoder SRM 822 was the first event of the last week (problems, results, top 5 on the left, analysis). The hard problem did not require too many algorithmic insight, but the implementation and tiny details were extremely tricky to get right. As a result, only bqi343 managed to make it work and he won the SRM ahead of four challenge phase masters. Well done!

I was almost there with the hard problem, my solution had the same phases as the one from the official analysis, but I did not manage to even make it work on samples in time.

Codeforces Round 767 followed on Saturday (problems, results, top 5 on the left, analysis). I did not like the long statement of A and I did not immediately see the solution to B, so I've started solving the (relatively) easier problems in a weird order: D1, D2, C, A. When I solved these four, I saw that tourist already had all of them + problem B solved, so it became clear that I needed to go for the harder problems if I wanted to have a shot at the first place. We solved E roughly at the same time which did not change the situation, so I went all in on F, but unfortunately did not manage to finish in time.

At the end of the contest, my solution for F had just one bug: when comparing fractions a/b and c/d, I compared a*d-b*c with zero without taking the signs of b and d into account :( To be fair to tourist, his solution to F also needed just a few more minutes. Congratulations on the win! As he pointed out after the round, I would have probably won the round if he did not participate, since then I would have solved B instead of F.

I want to mention problem E, not because it was particularly exciting, but because I want to share an interesting trick from my solution: 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.

In the past few months, I've become a lot more proficient using AtCoder's general lazy segtree algorithm, and prefer using it to rolling a custom lazy segtree implementation for every problem. However, in problems like this one it can be quite challenging to express the lazy propagation as a monoid + a set of mappings. All the more satisfaction when you actually manage to do it :) Can you see the trick? I'll describe my solution in the next summary.

CodeChef January Cook-Off 2022 wrapped up the week on Sunday (problems, results, top 5 on the left, analysis). tourist has solved all problems in less than an hour (out of 2.5 hours available) and won in a very convincing fashion. Great job!

In my previous summary, I have mentioned a CodeChef problem: you are given a permutation of length 200000, and need to tell if it's possible to split it into two disjoint subsequences in such a way that both parts have the same number of incremental maximums (numbers that are bigger than all previous numbers in the part).

The first observation is somewhat natural: let's look at the incremental maximums of the original permutation. If their number k is even, then it's easy to find the required split: let's find the (k/2+1)-th incremental maximum, and let the first subsequence consist of all numbers before it, and the second subsequence of this number and all following number. Then each of the subsequences will have exactly k/2 incremental maximums, and those will be exactly the incremental maximums of the original permutation.

We can also notice the following "reverse" observation: each of the incremental maximums of the original permutation will be an incremental maximum of one of the two subsequences. But of course the subsequence may have additional incremental maximums. Let's call the incremental maximums of the original permutation the big ones, and all others the small ones.

Notice that we can always get rid of a small incremental maximum without affecting any other big or small incremental maximums: just move it to the other subsequence (where it will be hidden by the big incremental maximum that was hiding it in the original permutation), together with any additional small incremental maximums that appear when we remove this one.

Therefore if there is a solution to this problem where both subsequences have small incremental maximums, we can keep removing one from each until one of the subsequences has only big ones. So without loss of generality we can only look for solutions where the second subsequence has only big incremental maximums.

In a similar spirit to the above argument, we can also introduce new small incremental maximums by moving them from the other subsequence. Therefore the set of incremental maximums of the first subsequence can be any increasing subsequence of the original permutation.

Therefore the problem has been reduced to the following: does there exist an increasing subsequence of the given permutation such that it contains exactly k-m out of k big maximums, where m is its length?

Now we can assign a weight of 2 to all big maximums, and a weight of 1 to all other numbers, and our question simply becomes: "does there exist an increasing subsequence of weight k?"

Finally, we can notice that we can always decrease the weight of a subsequence by 2 by simply removing some elements, so it's enough to answer the question "what is the maximum weight of an increasing subsequence which has the same parity as k?" And this question can be answered by adapting a O(n*log(n)) algorithm for the longest increasing subsequence.

Notice how we first obtained a working understanding of the solution space here — that we can have any two disjoint incremental subsequences of the original permutation that cover all big maximums as the sequences of incremental maximums of the two parts — and then the actual algorithmic solution was not that hard to see.

Thanks for reading, and check back (hopefully) tomorrow for this week's summary!