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
n 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
n 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
10, and you need to produce a sequence
pi of
n integers such that 0<=
pi<2
30, 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
qi=
pi&
a has length
k. Here & denotes bitwise and, in other words we consider a certain subset of bits of
pi, 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 pi 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 pi with two consecutive numbers 2pi and 2pi+1, or add a new bit in the beginning, appending a second copy of the sequence sequence pi to itself, but with all numbers increased by the same value 2t chosen in such a way that all pi<2t. 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 2r 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!
