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!