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!