A digging week

Codeforces Global Round 31 last Friday wrapped up the 2025 Global Round series (problems, results, top 5 on the left, analysis, serie standings that use the "sum all 3" instead of the actual "sum 2 best out of 3" scoring system). I spent way too much time on implementation and debugging once again, solved A-F1 and then decided not to go for even more standard-ish implementation in F2 and instead tried to get H1 in the end, but could not actually solve it. ecnerwala had roughly the same amount of time as myself for H1 after solving A-G (even the strong version of G), and he did solve H1 as well to claim a clear first place. Well done!

Meta Hacker Cup 2025 held its final, this time online, on Saturday (problems, results, top 5 on the left). Gennady has won his 6th Hacker Cup, and it was not easy: he scored 44 out of his 71 points in the last hour, and Yui could still have snatched the first place were her last-second submission in C1 correct. Congratulations to both! Looking at the scoreboard of this contest, it feels sad that all other contests have abandoned the system test concept and no longer reward writing good code and testing it before submission as much.

AtCoder is wrapping up the year with two last chances to qualify for AWTF 2026, the first of which was Grand Contest 075 (problems, results, top 5 on the left, analysis, serie standings). In problem A, I was looking for an algorithmic solution, trying hard to find some sort of knapsack subproblem with slowly increasing weights that can be solved by greedy or backtracking. However, it seems that this was a dead end, and one had to pull the main idea out of thin air, or to print the answers for small n and generalize.

I've then tried to solve problems B and C, but there I actually had an opposite issue: I was digging in the right direction (maintaining a piecewise-constant rolling window of size y in B, going in increasing order of b_i and checking how much we can deviate from the sorted order of a_i in C), but at some point I stopped digging, with the justification that in an AGC problem I should look for a beautiful alternative approach instead, which I could not find. After reading the editorial it turned out that the missing piece was more digging :)

Luckily, in problem D the required digging was not very deep, and I managed to get a non-zero score with a whopping 2 minutes remaining in the round. This did not get me any tour points, but I guess there is still an imaginary chance to qualify if I win the upcoming AGC 076. That is not going to happen, of course :)

tourist did his share of digging faster than others, but as his AWTF qualification was set in stone anyway, these results might be celebrated more by Kevin090228 who has likely guaranteed his AWTF qualification with this second place, and f3e6g4 who has jumped into the magical top 12 for now. Congratulations to all three!

Let me highlight problem C from this round, at a risk of not being able to fully describe a solution next week: you are given two sequences of integers a_i and b_i of the same length n up to 2*10⁵, 1<=a_i<=10⁹, 0<=b_i<=30. We will permute the sequence a_i arbitrarily, and then compute sum(a_i>>b_i), where >> denotes the bitwise shift right. How many of the n! permutations yield the smallest possible value of that sum? You need to print the answer modulo 998244353. 

Thanks for reading, and check back next week.