The Last Remaining Number 2

The answer is $\min(A_1,\ldots,A_N)+N-1$.

Let $m$ be the minimum just before an operation, and let $x$ be the removed value. Every surviving value $y$ falls into one of two cases:

• If $y\le x$, it becomes $y+1\ge m+1$.
• If $y>x$, it is unchanged. Since the values are integers and , we have .

Thus the minimum increases by at least one per operation. There are exactly $N-1$ operations, giving a lower bound of the initial minimum plus $N-1$.

To attain the bound, always remove a current maximum. Every remaining value is at most the removed value, so every one increases by one. A minimum occurrence remains: if removing a maximum also removes a minimum, all current values are equal and another occurrence remains. Consequently, the minimum increases by exactly one per operation and the bound is attained.

For $N=1$, no operation is performed and the same formula applies. The intended solution for the single subtask stores only the minimum while reading the input. Time is $O(N)$ and auxiliary space is $O(1)$.

The naive solution repeatedly finds and removes a maximum and updates every remaining value explicitly. It is correct but takes $O(N^2)$ time and $O(N)$ space, so it times out on maximum-size inputs.

Each integer increases at most $N-1$ times. The answer and all simulation values are at most $10^9+200\,000-1=1\,000\,199\,999$. All arithmetic fits signed 64-bit integers.

Solution written by GPT6