A double prix week

Before I cover the last week, I need to mention the 4th Universal Cup Stage 5: Nanjing, which happened the week before and which I forgot to cover (problems, results, top 5 on the left, analysis in Chinese). Even having only 2 out of 3 teammates did not stop team USA1 from winning by a whole problem. Congratulations!

The Universal Cup can't stick to the plan of having rounds only every other week, so Stage 6: Shenyang took place last week (problems, results, top 5 on the left, analysis in Chinese). The first two places look suspiciously similar to the previous round, but for the veteran teams Polish Mafia and Almost Retired Dandelion who also solved everything this was the best result of the season. Well done!

Codeforces Round 1066 wrapped up the week (problems, results, top 5 on the left, analysis). Some of the Universal Cup stars were also strong this time, but they were complemented in the top 5 by jiangbowen and PEIMUDA who were not at the very top in the team rounds. Congratulations on the nice individual performance!

Thanks for reading, and check back next week for a more meaningful summary!

An array week

Meta Hacker Cup 2025 Round 2 was the first event of the Nov 10 — Nov 16 week (problems, results, top 5 on the left, analysis, my screencast). Once again getting the problems right was more important than solving them fast, but it is still more impressive to do both at the same time. Congratulations to Benq and Um_nik who got quite a margin in penalty time compared to the rest of the full scorers!

In problem D, my solution (like all other solutions) was exponential in k. When I ran it on the validation input, it turned out that one case with k=25 (the maximum) takes about 30 seconds, so I was not sure if 80 such cases would run in time, even with the multithreaded template. But then I realized that the exponential part of the solution depends only on k, so we can precompute it once for all possible values of k, and then solve the 80 testcases in polynomial time. The precomputation only took about 40 seconds for all values of k (since the running time is exponential, k=24 is already much faster than k=25 and so on), and I was able to comfortably submit within the 6 minute window.

What I did not realize is that even if the precomputation took 10 minutes, I would still be able to submit, because one can run the precomputation before downloading the input! And unlike regular contests where the result of the precomputation in such cases must fit into the source limit, here we can just keep it in memory (in case we trust that the program will not crash on the first run) or save it to disk. I never had to do something like this in the Hacker Cup, but will definitely keep this trick in mind!

Codeforces Round 1064 wrapped up the week on Sunday (problems, results, top 5 on the left, analysis). maroonrk was done with 42 minutes to go, but only JDScript0117 was able to join him with 5 problems, and only with 5 minutes remaining in the round. Congratulations to both on solving everything!

In my previous summary, I have mentioned my search for a nice and simple templated treap. I have decided to try building one myself, and you can see the result in action in this submission to problem F2 from Global Round 30 (treap class itself at the top, its usage at the bottom).

The API is modeled on lazysegtree, and it is parametrized with exactly the same types S and F and operations on them, with the same requirements on the composition of operations. A treap contains zero or more blocks, where each block represents an array of values of type S. We support the following operations:

• t.prod(block) -> S: computes op(...(op(op(e(), a), b), ...) if the given block has elements (a, b, ...). Runs in O(1).
• t.apply(f, block): replaces each element x of the given block with f(x). Runs in O(1).
• t.single(s) -> block: creates a new block with a single element with the given value. Runs in O(1).
• t.destroy(block): destroys a block so that its memory can be reused. Runs in O(block_size).
• t.concat(block1, block2) -> block: concatenates two blocks into one. The old blocks are consumed by this operation and are no longer valid after it. Runs in O(log(block_size)).
• t.split_left(block, g) -> (block, block): splits a block into a prefix and a suffix, given a predicate g. The split point is chosen in such a way that both of the following are true: either prefix is empty or g(prod(prefix)) is true; either suffix is empty or g(prod(concat(prefix, first_element(suffix)))) is false. If g is monotonic on prod(prefix), then this will find the point where it changes from true to false. Runs in O(log(block_size)).
• t.interleave_left(block1, block2, g) -> block: interleaves two blocks into one. The predicate g tells, given the products of a prefix of block1 and a prefix of block2, whether the last element of that prefix of block1 should come before the last element of that prefix of block2. Runs in O(smaller_block_size*log^2(block_size)) maybe?

This API tries to unify and generalize the two common cases of splitting by index and splitting by key. Splitting by index can be achieved by adding a 1 as one of the elements of struct S, implementing op as addition for that element, and using a predicate on that sum for splitting. Splitting by key can be achieved by storing the key as one of the elements of struct S, and implementing op(k1, k2)=k2 (this is what the submission linked above does).

I've also tried to make the API harder to misuse by making the block type moveable but non-copyable, so that the compiler helps make sure that we don't use a block after it has been consumed by an operation. This requires some std::move's in user code, but hopefully that is not too big of a burden.

We can also add more operations that can be expressed using the above ones, but allow a dedicated implementation with a better constant factor, such as insert (instead of single+interleave) or a product on a range (instead of two splits, product, then two concats back). However, I wanted to start with a small API to be able to iterate faster.

It is certainly not as powerful as a fully custom treap, but I think it can express most of the operations from BYOT, with the exception of range reverse and segment tree beats. And for me it is much more convenient to think in terms of concatenating and splitting arrays and applying associative operations on them, rather than directly in terms of treap implementation. What do you think, and do you have improvement suggestions?

Thanks for reading, and check back soon for last week's summary!

A treap week

Codeforces Global Round 30 was the main event of last week (problems, results, top 5 on the left, analysis, my screencast). I was doing quite well on the first six problems, but got bogged down with implementing treaps with some additional accounting for problem F2, spending more than an hour on that. Right after the contest ended, I had two thoughts:

1. Wow, the people at the top of the scoreboard are so much better than me at implementation, how did they dig themselves out of this treap mess so fast?
2. I should implement some kind of templated treap and have it available for the next rounds. Currently I do not have a library of my own, and rely on the AtCoder library which has very nice templated segment trees and other algorithms, but not treaps.

Well, it turns out that the first thought was wrong. Out of the top 9 contestants (those that solved 8 problems), exactly the first three did not have treaps or splay trees in their solution for F2, but only segment trees plus standard STL data structures (while the next 6 had treaps or splay trees)! So these results clearly show that thinking some more to simplify the implementation beats just jumping into the first tedious simplementation approach one comes up with :) Well done to Otomachi_Una, Kevin114514 and dXqwq!

The second thought still stands though. However, it is not obvious to me what is the best templated abstraction for a treap. From the 9 contestants mentioned above, it seems that only hos.lyric has a templated splay tree, but even in her case the abstraction seems to leak the implementation details (push/pull), and the function splitAt might have been added specifically for this problem since it is not aligned with the rest of the abstraction, relying on the custom field "size" of the node that no other methods use. Compare this to AtCoder's lazysegtree, which is defined in abstract mathematical terms of applying two operations on ranges of data.

So, does somebody know a templated treap/splay tree abstraction that expresses the operations in abstract mathematical terms, and yet is as fast and powerful as tinkering with treap's implementation details?

In my previous summary, I have mentioned another Codeforces problem: you are given a tree with n<=5000 vertices. Consider the 2ⁿ ways to choose a subset S of its vertices, and for each subset S build a complete graph where S is the vertex set, and every two vertices are connected by an edge with a weight equal to the length of the tree path connecting them. What is the sum of weights of minimum spanning trees of those 2ⁿ graphs?

A natural question to ask is: given a particular pair of vertices a and b, in how many of the 2ⁿ subsets will they be directly connected by an edge of the minimum spanning tree? If we can answer that question, then we can just add up those answers multiplied by the distance between a and b to obtain the answer to the problem.

The first difficulty on that path is that "the minimum spanning tree" is not well defined, there might be multiple spanning trees of the same minimum weight. To deal with that, we can choose a particular minimum spanning tree, say, the one found by the Kruskal's algorithm that processes the edges in the order of weights, breaking ties in the lexicographical order of the edge ends.

In order for an edge between a and b to be chosen by the algorithm, it is necessary and sufficient that there is no path connecting a and b using the previous edges in the aforementioned order, namely using all edges of a smaller weight, and edges of the same weight that come before in the lexicographical order. Let us check how this path might go along the tree. Let us draw the tree in the following manner: the path from a to b is at the top, and a subtree grows from each of its vertices. We need to get from a to b, stopping only in vertices in the chosen subset S, such that each jump satisfies the above criteria.

Suppose there is a vertex c in S, hanging somewhere from the middle of the path, such that d(a,c)<d(a,b) and d(b,c)<d(a,b), then we can just go from a to c to b, so in those cases the edge between a and b will not be chosen. Suppose c hangs from the vertex x on the path (x might not be in S, so we cannot stop there). Then d(a,c)=d(a,x)+d(x,c), d(a,b)=d(a,x)+d(b,x), d(b,c)=d(b,x)+d(x,c), so the above inequalities translate to d(x,c)<d(b,x) and d(x,c)<d(a,x), in other words d(x,c)<min(d(a,x),d(b,x)). So in order for the edge between a and b to be chosen, we must have d(x,c)>=min(d(a,x),d(b,x)) for all c in S.

Now, suppose that inequality is strict: d(x,c)>min(d(a,x),d(b,x)). Then it's not hard to see that instead of going to/from c when passing through x, we can go directly to/from a or b, therefore such vertices are not useful to construct the path we are looking for. So the existence or nonexistence of the path depends only on the vertices c with d(x,c)<=min(d(a,x),d(b,x)). Since we already know that the path will exist when there is c such that d(x,c)<min(d(a,x),d(b,x)), the only interesting remaining case is where there is one or more vertices c such that d(x,c)=min(d(a,x),d(b,x)).

The distances between such vertices can be equal to d(a,b), so this is where the lexicographical ordering of the edges comes into play. It is possible to carefully consider it and solve the problem, but we can also make another small observation instead: vertices c such that d(x,c)=min(d(a,x),d(b,x)) are exactly those vertices that are at the distance of d(a,b)/2 from point z that is the middle of the path between a and b (note that z is either a vertex or a midpoint of an edge)!

This raises a natural question: what if, instead of focusing on the edge between a and b, we focus on all edges of the spanning tree with the given middle point z? If d is the smallest distance between z and a vertex in S, then from the above argument we can see that only edges of length 2d can exist in the spanning tree. If we root the original tree at z, and count the number m of subtrees of the root that contain a vertex at depth d (none of them will have a vertex at depth less than d by the definition of d), then it's not hard to observe that we will have exactly m-1 edges with length 2d and middle point z in the spanning tree. Note that in case z is a midpoint of an edge, then m<=2.

So we just need to count for each subtree how many ways are there to choose S in this subtree such that the smallest depth is d, and then we can combine those values to obtain the answer using the above observation, and then sum up those answers over all choices of z.

It was not strictly necessary to go through the Kruskal's algorithm and the lexicographical order part. Instead, we can immediately start with the "consider all edges of the spanning tree with the given middle point z" argument, and the solution will be short and beautiful. However, I also wanted to demonstrate how one can arrive at this idea analytically.

Thanks for reading, and check back next week!

A QOJ week

Pinely Round 5 started the competitive part of the last week on Thursday (problems, results, top 5 on the left, analysis). This was my first individual appearance in a screenshot on this blog since April 2024, so I think it went pretty well :) I was figuring out the solutions pretty quickly, and did not get stuck in implementation like I often do. However, it was not nearly good enough for the first place, since tourist was both the fastest, and with zero incorrect attempts. Congratulations on the convincing win!

Problem F gave me a nice warm feeling when I figured out the solution, so maybe it will be enjoyable for you as well: you are given a tree with n<=5000 vertices. Consider the 2ⁿ ways to choose a subset S of its vertices, and for each subset S build a complete graph where S is the vertex set, and every two vertices are connected by an edge with a weight equal to the length of the tree path connecting them. What is the sum of weights of minimum spanning trees of those 2ⁿ graphs?

The 4th Universal Cup Stage 4: Chengdu took place on Saturday, as usual (problems, results, top 5 on the left, analysis in Chinese). Team USA1 won the third stage out of four this year, defying the parity rule. The second place went to a team that is not in the season rating, so I assume this was a team that was participating in the original onsite contest that this stage was a mirror of. Congratulations to both teams on solving all problems!

Yandex Cup 2025 Qualification Round  wrapped up the week on Sunday (results, top 5 on the left). A few people were in contention on the easier problems, but starting from problem J ecnerwala was significantly faster than the competition, so it is not a surprise that only he was able to solve everything this time. Well done!

After the 3rd Universal Cup Semifinals, this was the second big contest that required proctoring for those who want to qualify to the onsite round, and it was certainly not the last one to do so.

In my previous summary, I have mentioned an AtCoder problem: you are given a single integer n<=2¹⁰, and you need to produce a sequence p_i of n integers such that 0<=p_i<2³⁰, such that for every value of k between 1 and n there exists a number a such that the longest strictly increasing subsequence of the sequence q_i=p_i&a has length k. Here & denotes bitwise and, in other words we consider a certain subset of bits of p_i, the same subset for all i.

Many, if not most, constructive problems that have a single integer n in the input are solved by figuring out a way to produce solutions for 2n and 2n+1 from a solution for n, and this problem was also one of those. The constraints strongly hinted that we need to learn to double n using at most 3 additional bits.

Suppose we have a sequence p_i that solves the problem for some n. There are actually two ways to easily double the LIS length: we can either add a new bit at the end, replacing each number p_i with two consecutive numbers 2p_i and 2p_i+1, or add a new bit in the beginning, appending a second copy of the sequence sequence p_i to itself, but with all numbers increased by the same value 2^t chosen in such a way that all p_i<2^t. In both cases we set the corresponding bit of a to 1. This way by adding just one more bit we are now able to get all even LIS lengths from 2 to 2n. But what to do about the odd lengths?

Let us use one more bit, and append a number 2^r that is bigger than all existing numbers to the end of the (doubled) sequence. Now if we use the same a as before, the LIS length will still be 2k since the new number becomes 0 if the r-th bit of a is not set. However, if we set the r-th bit of a to 1, then the LIS length will be 2k+1, since the new big number can be appended to any increasing sequence. This means that we now have a sequence of length 2n+1 for which we can get any LIS length between 2 and 2n+1. The only missing length is 1, but that is also easy to achieve: just set a=0.

So we can go from n to 2n+1 using 2 additional bits. What about going from n to 2n? Well, actually we can use the "append a big power of two" trick once again, and go from n to 2n+2 using 3 additional bits. Being able to go from n to 2n+1 and 2n+2 means that we can get any number if we also have solutions for the base cases n=1 and n=2.

As is often the case with AtCoder problems, after seeing the solution one cannot fathom struggling for several hours to come up with it, it looks so straightforward :)

I was discussing an old Open Cup gem with my friends recently, motivated by a lecture on binary search for beginner Swiss high school students. I was almost certain there is no way to upsolve that problem now. However, it turns out that this problem (and probably many other old Open Cup contests?) are now available for upsolving on QOJ.ac, the same website that hosts Universal Cup. Huge thanks to the admins of QOJ for preserving the old contests!

Thanks for reading, and check back next week!

A moonlit week

The Universal Cup Stage 3: Polar was the first event of this week (problems, results, top 5 on the left, still not updated cup standings). In all three stages of this season the first two places went to the same two teams, and in odd-numbered rounds team USA1 comes out on top, if only by less than one wrong submission this time. Congratulations to both season leaders!

AtCoder Grand Contest 074 wrapped up the week just a few hours ago (problems, results, top 5 on the left, analysis, race standings). Just one minute before the end of the round it seemed like Nachia executed a perfect strategy, solving C and B first, then deciding to go for D instead of A since it was clear at that point that A+B+C would not be enough to win the round, and getting D with 15 minutes remaining to go on top with a unique set of problems solved.

However, ksun48 made not one but two submissions on C during the last minute, one of which turned out to be correct. How does one submit, find and fix a bug, and submit again, all within the last minute of the round? Well done, Kevin!

I have spent most of the round on the same problem C. It was clear from the constraints that one should dig in the direction of going from ~n to ~2n using 3 additional bits, and in the end this is exactly how my solution works, but somehow this digging took me more than 2 hours, mostly on paper.

I think it took me so long since I have made a reduction that made the solution more difficult, and did not consider rolling it back (instead, I have persevered and solved the more difficult reduced problem): I was looking for a way to configure the 3 additional bits in such a way that we can go from a LIS of length k for n/2 either to lengths k, 2k and 2k+1 or to lengths k, 2k+1 and 2k+2, depending on the parity of n.

The reason I wanted three options instead of the usual two was that the 2k+x options would not cover small values of LIS, so I thought it would make sense to make sure we also can keep k unchanged; however, on further thought after the round it became clear that the small values not covered are only 1 and possibly 2; and it is always very easy to obtain a LIS of 1 by just making everything equal, and also not hard to obtain a LIS of 2 by making almost everything equal.

Despite a few spoilers above, I hope you can still enjoy solving that problem if you have not already: you are given a single integer n<=2¹⁰, and you need to produce a sequence p_i of n integers such that 0<=p_i<2³⁰, such that for every value of k between 1 and n there exists a number a such that the longest strictly increasing subsequence of the sequence q_i=p_i&a has length k. Here & denotes bitwise and, in other words we consider a certain subset of bits of p_i, the same subset for all i.

In my previous summary, I have mentioned a Hacker Cup problem: you are given a string of 0s and 1s of length <=600000. Two players are playing a game, making moves in turns. On each move of the first player, they erase any prefix of the string that ends with a 0. On each move of the second player, they erase any suffix of the string that starts with a 1. The player who cannot make a move loses. Who will win if both play optimally?

First of all, the first player always takes a 0, and the second player always takes a 1. Naively, one might think that we should just count if there are more 0s or 1s in the string. However, it is very easy to come up with a counter-example: string 110 has more 1s than 0s, but the first player still wins because they can erase it in one go. The 1s in the beginning of the string don't really matter, as long as there is at least one 0.

However, since having more 0s still seems useful for the first player, a somewhat natural idea is to check: what if the first player tries to make a move that maximizes the balance of the remaining string — the difference between the number of 0s and 1s? Here a counterexample is also not that hard: from the string 0100 we can go to two different strings 100 and 0 with the maximum balance of 1, however if we go to 100 then the second player can take the remaining string and win, while if we go to 0, the second player loses.

Guided by this counterexample, what if we always break ties by choosing the shortest possible string with the maximum balance? After spending some time finding yet another counterexample to this approach and failing, I've decided to look for a proof that it works instead.

Suppose we have used that strategy for the first move, and the remaining string has some non-negative balance (it feels intuitive that the balance has to be non-negative for us to win). What happens to the balance after the move of the second player? After some experimentation, we can notice that it always becomes strictly positive. And indeed, it is not hard to prove by contradiction: suppose it is non-positive after the move of the second player. Suppose the string remaining after the move of the first player is s, and the second player has removed then removed the suffix u, and what remained is t, so s=tu. 

The balance of s is non-negative, the balance of t is non-positive, and u starts with a 1. Since the balance of u is the balance of s minus the balance of t, is is also non-negative, so it must have a 0. Consider its first 0, which splits the string u as u=v0w, where v consists only of 1s. But then the first player could have additionally erased the string tv0 in their first move. Since the balance of t is non-positive, and the balance of v0 is non-positive, the balance of tv0 is non-positive, which means that the balance of w is the same or higher than the balance of s=tv0w. But this contradicts the choice of s.

So, after the move of the second player the balance will become strictly positive. But then we can apply the same approach (make the move that maximizes the balance of the remaining string, breaking ties to shorter remaining strings), and the balance of the remaining string will be non-negative (since at least if we take the first 0 it is non-negative, and we maximize it), so we can repeat this until we win.

We can already submit our solution at this point, but formally speaking we also need to prove that if the first player cannot make a move that leaves a string with a non-negative balance, then the second player wins. And indeed, we can apply the same argument as above: if we have left a string with a strictly negative balance, then from the point of view of the second player it has a strictly positive balance, and they can apply exactly the same strategy as above to win.

This solution is longer than the one in the editorial, but it is how I solved the problem during the round, and I hope it shows how to arrive at a solution without having to pull an idea out of thin air, for example an idea to consider balanced parentheses sequences as the editorial does.

Thanks for reading, and check back next week!

A major week

Meta Hacker Cup 2025 Round 1 was the main event of last week (problems, results, top 5 on the left, analysis). As usual in the early Hacker Cup rounds, one has to balance the speed against the amount of effort you spend to test your own solutions before attempting to submit them. There is just one attempt per problem, and the submission result is only revealed after the round ends (a pretty unique setup for today's contests, but one that I think makes the competition more exciting and emphasizes the useful testing skills!), and at the same time you only need to be in top n to advance, your score does not matter for the future rounds. It does matter for the bragging rights though, so well done to Geothermal on being much faster than everybody else!

The Hacker Cup is now the "Major Individual Competition" (according to cphof) that was held the most years among those still happening, this one is the 15th edition! TopCoder Open/Invitational is still in the overall lead with 22 editions, but that number is not going to increase further. Huge thanks to the organizers for putting it together year after year, and I'm looking forward to participating in the next 15, and of course to you bringing back the onsite finals :)

Problem D was quite nice, and you can also solve it as a math problem without any computer help. You are given a string of 0s and 1s (check out the original problem statement for the more colorful story!) of length <=600000. Two players are playing a game, making moves in turns. On each move of the first player, they erase any prefix of the string that ends with a 0. On each move of the second player, they erase any suffix of the string that starts with a 1. The player who cannot make a move loses. Who will win if both play optimally?

Thanks for reading, and check back next week!

A lifting week

The Universal Cup held its Stage 2: Paris during the Oct 6 - Oct 12 week (problems, results, top 5 on the left). This was one of the very rare occassions where the winner seemingly was not a veteran team, but a team THU1 consisting of university students. They were already ahead of the usual suspects on 12 problems by penalty time, and solving the last problem 10 minutes before the end was the icing on the cake. Congratulations!

Codeforces Round 1058 wrapped up the week on Sunday (problems, results, top 5 on the left, analysis, my screencast). As the custom goes these days, I have started well on the easier problems but then got stuck, trying to make progress in either of the three remaining problems, and actually being close to solving D2 at the end, but not quite.

Nobody was able to solve everything this time, but the top 5 shows that many different strategies were competitive. In the end solving the problems fast from left to right was the winning recipe for Benq. Congratulations!

In my previous summary, I have mentioned another Codeforces problem: you are given n<=250000 numbers which are written in sorted order. You need to process q<=250000 queries, each query is a segment [l, r] of the numbers. For each query, you need to find the maximum amount of numbers within the segment [l, r] that can be taken in such a way that for each three taken numbers the difference between the largest and the smallest of them is more than z. The number z is the same for all queries.

The first step is solving the problem for a single [l, r] query. It is not hard to convince oneself (if we want to have a formal proof, we can use the exchange argument) that we can do it greedily: take the first two numbers in the segment a_l and a_l+1, then take the first number at position l+2 or higher that is bigger than a_l+z, then take the first number to the right of that that is bigger than a_l+1+z, and so on.

Now we need to learn to simulate this process fast so that we can process many queries with different values of l within the time limit. The key observation is that the greedy solution can be split into two almost independent chains: the odd-numbered values are a_l, then the first number a_k that is bigger than a_l+z, then the first number that is bigger than a_k+z, and so on; and the even-numbered values are a_l+1, the first number that is bigger that a_l+1+z, and so on. So a solution could count the numbers in those two chains independently and add the results up.

How do we count the numbers in one of those chains, starting with a given position a_l and until we pass a_r? This can be done using a standard algorithm called binary lifting: we can precompute where do we end up after we do 2ⁱ jumps from position l for each l and i. Then to answer an [l, r] query we first try to make 2ⁱ jumps with the highest possible i, if we overshoot a_r then we skip this step otherwise we take it, and then do the 2^i-1 step, and so on. Since the true answer has a binary representation, we will find it in just O(log n) steps per query, and the precomputation takes O(n*log n).

However, this approach is not the full solution since the two chains are only "almost" independent. More specifically, it can happen that the arrive at the same position, and then one of the chains will instead take the next consecutive number as described above.

It turns out that for a given two starting positions l and l+1, we can again use binary lifting to find out when this happens! If two chains are at the same position at a certain moment, they will also be at the same position after any number of additional jumps. It means that we can still use the binary lifting idea of trying a large 2ⁱ jump first for both chains, and if we are in the same position then we roll it back and try 2^i-1, and so on.

Note that it is not necessarily true that the two chains will reach the same number at the same step, though. For example, it might happen that a_l+1>a_l+z, and then the first chain will have a_l+1 at the second position. However, because the jump function is monotonic, the second chain will always be at the same position or to the right of it for the same step, and the first chain will always be at the same position or to the right of it when one step ahead of the second chain. So we just need to check those two possibilities (a collision at the same step, or a collision where the first chain is one step ahead) in the binary lifting condition.

This way we can precompute for all n options for the starting position l, where, and after how many jumps, do the chains starting from a_l and a_l+1 collide. This precomputation takes O(n*log n). Note that after the two chains collide, we now have the collision position k, and the two chains continue from a_k and a_k+1, so we have exactly the same situation as in the beginning.

Now we can consider a new type of jump, from a_l to a_k as described above, and do binary lifting on those big jumps! This time we need to precompute two things for each l and i: where do we end up after 2ⁱ big jumps, and how many small jumps does that entail.

And finally to correctly answer an [l, r] query, we first do the binary lifting steps using big jumps from a_l, and as soon as the next big jump would overshoot a_r, we do the binary lifting steps using small jumps for the remainder.

The solution was ultimately about applying a standard algorithm three times, not about coming up with a novel approach. However, I still find it quite beautiful how the same idea just keeps on giving.

Thanks for reading, and check back for last week's summary!