I did the ABC today: https://atcoder.jp/contests/abc369

The fumbling started on problem A, where I misread the input format and consequently got 2 WA (don't worry why this caused 2 WA and not 1). Then I did a dumb thing and decided to switch between C, Python, and C++ for the next few problems, which obviously resulted in mis-submits...

Somehow managed to get ABCD within 20 minutes even with this nonsense.
But I then hit a wall at E/F.

Ironically G actually seemed solvable. Here's the summarized problem statement:

Given a tree of size N, Alice and Bob play the following game:

Alice picks K vertices on the tree.
Then, Bob constructs a walk that begins and ends at vertex 1, passing through all vertices chosen by Alice.

The "score" is defined as the length of Bob's walk. Alice wants to maximize the score, and Bob wants to minimize it. Determine for every K = 1, 2, ... N the score when both players are playing optimally.

Firstly, we can trivially show that it is always optimal for Alice to pick leaves of the tree.

We can then prove that the solution for K = i+1 (1 < i) must always be the solution for K = i with zero or one leaves added. So, the answers can be constructed iteratively by always picking the leaf which maximally increases the walk length.

Using the DFS traversal order, we can find that each leaf adds the sum of lengths of unused edges above itself to the walk length, scaled by 2.

Programmatically we can simulate this by mantaining such a sum of edges for each leaf. Anytime we choose a leaf, we have to remove all the edges from itself to the root, and update the sum of edges for the other leaves.

Bruteforce for this seems like O(n^3) or something. Can we do better? The costly step here is recomputing sum of lengths for each leaf. If we use some euler tour + range update stuff, each edge removal can be done in O(log n), and because each edge can only be removed once, this amortizes to O(n log n) total. This passes!

Unfortunately, I spent just a little too long debugging and only got AC two minutes after contest end... I also kinda wasted a lot of time midcontest, getting most of these observations around 00:30 - 00:40 but only actually starting implementation at 00:50 or so.

rly gotta not throw next contest fr

tags: programming atcoder contest-logs