A week with Ethan

TopCoder SRM 741 was the first event of the Oct 28 - Nov 4 week (problems, results, top 5 on the left, analysis). xudyh and tourist came to this event having the same number of points in the TCO19 qualification race (link, click on "Stage 1"), and this was the last round of the first stage so one of them would become the first TCO19 finalist. tourist had much better tie-breaker before this round, and has made it a habit to be in top 10, so the qualification boiled down to: if xudyh can win, he would qualify, otherwise it would most likely be tourist. xudyh came quite close, but was stopped by the great performance of fjzzq2002. Congratulations to xudyh on the great performance, to fjzzq2002 on the win and to tourist on making it to the TCO19 finals so early!

Facebook Hacker Cup 2018 onsite final round took place on Saturday (problems, results, top 5 on the left, analysis). There was quite tense competition until the very end, but ultimately Mikhail's (LHiC) speed could not be matched. Congratulations on the huge victory!

I've spent a huge chunk of the contest thinking that I almost have a solution to the problem "City Lights" (as in, "now it should finally start working in a few minutes after I handle this surely last corner case"), however it stayed as "almost" until the end of the contest. Here's what the problem was about: there are w<=80 windows and s<=50 stars, both cells on a grid which represents a skyline. One must draw several buildings, each represented by a rectangle on the grid with line y=0 as the bottom side. Several buildings may intersect. Each window must be inside at least one building, and each star must not be inside any building. We need to find the minimum number of buildings required to satisfy those constraints. Such a problem would be too easy, so there's an extra twist: suppose we remove a random subset of windows (each window is removed independently with probability 0.5), what is the expected value of the minimum number of buildings required to cover all remaining windows without covering the stars?

Codeforces ran another onsite contest on Sunday, the Lyft Level 5 Challenge Final Round (problems, results, top 5 on the left, parallel round results, analysis). tourist was unstoppable this time, solving all problems and doing it 20 minutes faster than scott_wu, the only other onsite contestant to solve everything. Congratulations to both!

Problem B in this round was a very nice interactive problem: you are given a tree with nodes numbered from 1 to n (n<=1000) and a subset of nodes in it which forms a connected subtree, given as a list of numbers of the nodes. There's also a second, hidden numbering of all nodes with distinct numbers from 1 to n, and a second subset of nodes which also forms a connected subtree, which is given to you as a list of hidden numbers of its nodes. However, you don't know how the hidden numbers of the nodes correspond to the visible ones. You can ask an oracle questions of two types:

• What is the hidden number of the node with [visible] number x?
• What is the visible number of the node with hidden number y?

Your goal is to find any vertex that belongs to both given subsets, or report that there isn't any. You can ask at most 5 questions.

Thanks for reading, and check back for more!