A double Moscow week

The first week of April was of course focused on ICPC 2019 World Finals (problems, results, top 12 on the left, official broadcast, our stream, analysis). It feels strange to write a short summary given the amount of coverage available for the contest, but I'll do it anyway :) Warsaw took a huge early lead, but almost stopped after two hours, spending eternity on the technically tricky problem C and still not solving it. The three pre-tournament favorites Moscow, MIT and Tokyo overtook them, but only Moscow could solve all 10 solvable problems. Congratulations to the winners and to all medalists!

Problem K was the most exciting for me, even though I didn't actually solve it myself. It went like this: you are given a street with n<=500 traffic lights on it arranged from left to right. The i-th traffic light stays red for r_i seconds, then green for g_i seconds, then repeats this cycle infinitely. The cycles for all traffic lights start at the same time 0, r_i and g_i are integers, and r_i+g_i does not exceed 100. Suppose you approach this street from the left at a random moment in time, and drive until you encounter a red light for the first time, or until you pass the entire street. What is the probability that you see red for the first time on 1st, 2nd, ..., n-th traffic light?

Codeforces Global Round 2 took place on Saturday, when most of the teams were already back home or on the way there (problems, results, top 5 on the left, analysis). ICPC gold medalist ecnerwala got enough points for the first place in less than an hour, even though our entire streaming team was trying to catch him as you can see :) Well done!

Problem G in this round was very nice. You have n game units, each capable of causing 1 unit of damage per second. You need to merge them into m bigger game units, and if a_i units were merged into the i-th bigger unit, it will cause a_i units of damage per second. The m bigger units will then attack an enemy army also consisting of m units, with the j-th enemy unit having b_j hit points. The attack will happen second-by-second, and in each second each of your big units attacks one enemy unit. It is allowed for multiple units to attack one enemy unit in one second. What is the fastest way to decrease the hit points of all enemy units to zero or negative? You can choose the way you merge the n units into m big units, but you can do it only once, before all attacks.

Thanks for reading, and check back for more!