An onsite week

Harbour.Space Scholarship Contest 2023-2024 on Codeforces was the main event of the week (problems, results, top 5 on the left, discussion, analysis). Radewoosh solved the first eight problems 20 minutes faster than everybody else, and therefore had all but guaranteed himself first place by the middle of the contest. Still, he kept his focus and managed to get problem I accepted as well with just 3 minutes to go. Huge congratulations!

I skipped this round and therefore cannot tell you much about its problems. Therefore, I'd like to use this post to talk about the upcoming onsite event that you might not be aware of :) I'm not referring to the IOI, which takes place next week in Szeged, Hungary, since I expect everybody interested in it to know where to find more information. Instead, I'd like to talk about the AtCoder WTF that takes place on September 8-9 in Tokyo, Japan.

When AtCoder announced its own onsite competition, the World Tour Finals, back in 2017, the world of onsite algorithmic competitions was quite packed. They have managed to host one edition of the WTF before the pandemic hit. All onsite competitions were cancelled or moved online during the pandemic, but instead of returning after global travel became relevant again, most were cancelled completely: Google Code Jam, TopCoder Open, likely Meta Hacker Cup. There were a few more Russia-based onsite competitions that are of course no longer a thing. ACM ICPC and high school olympiads such as the IOI are back in the onsite mode, but they have age upper bounds for participation.

AtCoder did not move the WTF online, instead they kept running the yearly qualification cycle, promising to invite the top 8 from each year to the onsite round in Japan when it becomes possible again. This is finally happening in two weeks! 18 finalists out of the maximum of 32 from the four qualification cycles will compete on the same problems over two competition days. This approach lies in contrast to the ACM ICPC approach where the finals for the 2022 and 2023 seasons are happening together in Egypt but the actual competitions will be kept separate. Which one do you think makes more sense?

I am really excited both for the competition (where to be honest I no longer stand a chance), and for the onsite event atmosphere. As an added twist, AtCoder have announced the online participation option for the future WTFs; I can't predict how this will work out, but when TopCoder did the same for TCO22, so few people decided to come onsite that they decided to cancel the onsite event altogether. Therefore this might be the last onsite event without the age upper bound ever :)

Thanks for reading, and check back next week!

An arborescence week

There was no contest that I'd like to mention this week, so let us come back to the AtCoder problem from the previous summary: you are given a connected graph where each edge is either red or blue, and each vertex is also either red or blue. You need to find a spanning tree in this graph such that for each vertex it has at least one adjacent edge of the same color as the vertex, or report that there isn't any.

The first step is to notice that all edges are of three types: type 2 are the edges where both ends have the same color as the edge, type 1 are the edges where one end has the same color as the edge, and type 0 are the edges where no end has the same color as the edge. We will also direct the type 1 edges from the vertex of the correct color to the vertex of the wrong color.

Clearly type 2 edges are the most useful for reaching our goal. In fact, if every vertex has at least one type 2 edge adjacent to it, then we can simply find the spanning forest among the type 2 edges. If it is a spanning tree, then we have solved the problem. If it is not connected, since we have already satisfied the color constraints, we can augment the forest to a tree using the remaining edges in any way.

What if there are some vertices that do not have type 2 edges adjacent to them? If there is a vertex with no outgoing type 1 edges, or in other words a vertex where all adjacent edges have the wrong color, then there is clearly no solution. So we only have to consider the case where some vertices have type 2 edges adjacent to them, and all remaining vertices have at least 1 outgoing type 1 edge. We will call the vertices with type 2 edges adjacent to them type 2 vertices, and the ones without them type 1 vertices.

The key remaining observation is that we cannot solve the problem using only type 1 edges. Each type 1 edge satisfies the color constraint for 1 vertex, but overall we have n vertices but only n-1 edges. So a logical idea is to start with the spanning forest of the type 2 edges that will cover all type 2 vertices, and then repeatedly try to find a type 1 edge that goes from a yet uncovered vertex to an already covered vertex (building something similar to an arborescence). If we manage to cover all vertices this way, then we can once again augment the resulting forest to a tree using the remaining edges. If we get stuck at some point, then there is no solution.

But why is this correct? We have proven that we need at least one type 2 edge, but why is it always correct to take ~all of them? This is a very typical situation for problems involving the spanning trees, as they all usually end up relying on some kind of greedy argument, so one could just bet on intuition here in my opinion. Still, here is the formal proof: consider the situation where our solution gets stuck. At this moment, the set S of uncoverted vertices contains only type 1 vertices, and there is no type 1 edge going from this set to the set of covered vertices. But then how could S be covered in any other solution? Since we have at most |S|-1 edges within S, and only edges within S can cover its vertices, one of them will have to remain uncovered in any tree.

Thanks for reading, and check back next week!

An apiad week

AtCoder Grand Contest 064 was the main event of the week (problems, results, top 5 on the left, analysis, my screencast, race standings). apiad's usual strategy worked spectacularly well this time, as after spending two hours on E he was able to solve just enough easier problems to win the round, while those who started with the four easier problems did not have two hours remaining for E and could not figure out all details. Congratulatons on the victory!

I was one of those starting with the four easier problems. Somewhat unexpectedly, I did not get stuck in them and did actually have a bit more than an hour remaining for E, and made some significant progress on paper: I realized that if the sum of all a_i is zero, and the sum of all b_j is zero, and we can place the n² negated sums -(a_i+b_j) in the matrix in such a way that every column and row has exactly one of each a_i and b_j, then the sum of the 2n-1 cells in a cross, which is the sum of the row plus the sum of the column minus the middle cell, will be exactly a_i+b_j. I've then realized that if the sum of all a_i plus the sum of all b_j is divisible by 2n-1, then we can get both of those sums equal to zero with some constant shifts. Finally, I've correctly hypothesized that in case it's not divisible by 2n-1, then we can only achieve score n²-1, and figured out how to do so with some more constant shifts for the first row and the first column.

Therefore the only remaining step was to place the n² negated sums -(a_i+b_j) in the matrix in such a way that every column and row has exactly one of each a_i and b_j. This does not depend on the values of a and b, so this simply needs to be done once for every n. It seemed quite doable as it felt like a more advanced derangement, and derangements are quite dense. I've tried some random placements and noticed that I can find such a placement for odd n, but not for even n. And this is pretty much how far I've got in an hour :)

Judging from the editorial (which I do not understand), it seems that for even n we need to use more degrees of freedom, therefore while I enjoyed coming up with my approach, I needed another huge step to finish the solution, and therefore needed at least another hour.

I found problem B to be a cute test of how well one understands the spanning tree mechanics (it is amazing how many nice problems can be derived from a relatively simple concept of a spanning tree, and the fact that it can be found greedily!): you are given a connected graph where each edge is either red or blue, and each vertex is also either red or blue. You need to find a spanning tree in this graph such that for each vertex it has at least one adjacent edge of the same color as the vertex, or report that there isn't any. Can you see a way to do it?

Thanks for reading, and check back next week!

A power of two week

There were no contests that I'd like to mention this week, but we still have two cool problems C from the previous summary to discuss. First, let us talk about a Codeforces problem: 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.

When I was thinking about this problem, I have convinced myself that any solution will need to keep track of the number of elements in the set S as we divide the probabilities by that number on each step, and unlike multiplication, division does not lend itself to some nice linearity of expectation arguments. Well, it turns out it does :)

Consider two adjacent numbers from the initial set S. How do they move? Well, either the lower number increases by 1, in which case it might actually merge with the higher number, or the higher number increases by 1, in which case it might disappear if it exceeds M, and then the lower number will also disappear after a few more steps. What is the expected number of steps that the lower number makes? Here comes the stunning observation: we do not actually need to know anything about the rest of the set S to compute this expected number of steps! No matter what happens to the rest of the set, every time one of those two numbers moves, it will be the lower number with probability 50%, and the higher number with probability 50%. So we can implement a relatively standard dynamic programming to compute the expectation.

And then, as you have probably guessed by this point, thanks to the linearity of expectation the answer to the problem can be computed as the sum of those expected numbers of steps over all pairs of adjacent numbers in the input, plus the expected number of steps for the highest number (which is just M+1 minus that number).

The really unexpected aspect of this solution for me is that we end up only ever dividing by 2, even though on the surface it looks like we need to divide by numbers up to |S|. Having learned this from the editorial, I immediately remembered one thing that I considered doing during the contest: can we try to reconstruct the answers to the sample cases in the fraction form from the values modulo 1000000007 that are given in the problem statement (750000009, 300277731 and 695648216)? Knowing the solution, I realized that those fractions would have a power of two in the denominator, and that might have been just the clue I needed to solve this problem.

I've tried doing this now, and it turns out this reconstruction is not so easy. Just trying to find a fraction with the smallest numerator and denominator yields:

750000009 = 15/4
300277731 = 26062/39247
695648216 = 35459/32906

Which is clearly incorrect for the last two cases, as the answer cannot be less than 1 or so close to 1. Adding some reasonable boundaries on the value of the fraction (it must be between 10 and 50 for the last two cases), we get:

750000009 = 15/4 = 3.75
300277731 = 133137/8642 = 15.40580884054617
695648216 = 133345/10938 = 12.19098555494606

Which actually looks plausible, but is still incorrect as we know from the above. However, we know from the problem statement that the denominator cannot have prime factors greater than |S|, which in our case is 5. Adding that constraint produces:

750000009 = 15/4 = 3.75
300277731 = 1241063/65536 = 18.937118530273438
695648216 = 582323/32768 = 17.771087646484375

Which looks even more plausible, to the point that it might be correct (I did not check), and in any case might have delivered the key hint about only ever dividing by 2.

Now, some questions to the reader :) Do you routinely try to convert the sample answers from the "modulo prime" form to the fraction form? Did it ever help you solve a problem? Do you have some tricks on how to do this more reliably? If the problemsetters are reading this, did you consider this trick when choosing the samples for this problem?

Now, on to an AtCoder problem: 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.

During the round, I guessed correctly that this is almost always possible, except for the cases like A₁=A₂, but B₁≠B₂. However, I could not find a nice way to reorder the numbers. I was thinking mostly about operations where y is bigger than the biggest number, to have at least some control over what is happening. In that case, by choosing the appropriate x, we can split the numbers into two parts and interleave those parts, but that does not give us enough control to achieve an arbitrary ordering.

One other thing that came to mind when thinking about this interleaving operation is that it can only make the numbers closer to each other, but not pull them apart. However, when no interleaving actually happens, in other words when we just do a cyclic shift of the numbers, then we are not reordering, but we can pull the two halves apart as much as we'd like.

This is how far I've got during the round, and it turns out that this is the right direction, but I missed one final trick. Here is a working plan: in the first N-1 operations, we do N-1 cyclic shifts, which allows us to create almost arbitrary gaps between pairs of adjacent numbers, but still keeps the cyclic order intact. And then in the N-th operation we do a massive reodering and everything falls into place.

Knowing the plan, it is relatively easy to figure out the details. Assuming the last operation uses x=0 and some y=Y that is bigger than all B_i, we just need to make A_i=Y*k_i+B_i. And now we can choose k_i in such a way that the cyclic order of those A_i coincides with the initial cyclic order of A_i, moreover we can choose any particular cyclic shift of this cyclic order, which then makes planning the first N-1 operations easy. You can find more details in the editorial.

However, it is still unclear to me how I could have arrived at this final trick without just "seeing" it out of nowhere. Even though the operation used in this problem is simple, the space of ways to use it is endless, and it was hard for me to somehow narrow down the search. For many problems, it is more or less clear where the difficulty lies and that you must use a certain resource optimally to arrive at the solution, and this helps cut less promising directions quickly when trying to solve the problem. However, in problems like this one, one cannot be sure that the direction is correct until they see a full solution.

To the 174 people who solved this problem during the round: how did you arrive at the solution? Is there some intermediate reasoning step that makes the last leap of faith smaller, or is it just small enough for you as it is?

Thanks for reading, and check back next week!

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!