2156E

Here’s a link to the problem.

Hint

The first thing to notice is that only our first few turns should matter, since the best pairs will either be locked or deleted very early on.

Solution

Now, consider the subproblem where Alex moves first. Let’s say he locks index $i$. Then, no matter how Hao moves, it’s clear that Alex can always achieve a beauty at least equal to the second-highest beauty of any pair containing $i$, which we will denote as $b_i$. Therefore, our final answer must be at least $\max b_i$, since we can choose $i$ freely.

Moreover, if Hao plays optimally, we can never achieve beauty greater than $\max b_i$. This is because every time we lock an index $i$, Hao can simply delete the index $j$ that maximizes the beauty of the pair $(i,j)$.

Therefore, we just need to compute the minimum of $\max b_i$ over all possible choices for Hao’s first deletion. The implementation of this is quite clean and is left as an exercise to the reader. Here’s mine in case you get stuck.