A good easy problem.

I like the $$$O(n \log A)$$$ solution, and I actually almost implemented it (but I used a set instead of maintaining stack maxima). It's fine that solutions with an extra $$$\log$$$ factor passed too.

The first problem that made me think I was missing something obvious, given how quickly many people were solving it. Turned out I failed to recognize Stirling numbers :) The problem is far from obvious anyway, though.

A fun story: my first impression was "I must have solved this problem at AtCoder". I tried searching for it, but only found AGC052 D. Given that the problem is similar (but is asking for "equal LIS" instead of "equal number of records"), and the writer of both problems is antontrygubO_o, I thought "ok, I guess this is the problem I am looking for, it just looks similar, but it's a different problem" and stopped searching. Turns out I should have dug deeper to find AGC028 E.

The second problem that made me think I was missing something obvious. I spent a lot of time thinking about various applications of Minkowski sums, but none of them helped to solve the problem even for $$$k \le 10^3$$$, let alone $$$k \le 10^6$$$. In the last hour, I figured out the reordering trick: we can reorder the stolen items so that the sum on every prefix of length $$$i$$$ is close to $$$w \cdot \frac{i}{k}$$$. It was easy enough from there.

I came up with a slow DP solution pretty early into the contest (before solving my 3rd problem), but only figured out how to reduce its complexity during the last hour. It's fun to have a problem asking for a floating-point answer (which actually allows to speed up the solution too) instead of the exact answer modulo whatever, at least once in a while.

Given the contest situation, I basically discarded this problem, I only came up with a simple $$$O(n^4)$$$ solution. Looks fun to think about, though.