103503A — Make Sum Great Again

\item Solution: \end{itemize} \textbf{Lemma:} The number of operations will never exceed $$$\sqrt{2 \cdot s}$$$.

Since we need to maximize the final length of the array, it is always optimal to add the smallest integer which is not already present in $$$a$$$.

The naive implementation of this idea has a runtime complexity of $$$O(n \cdot \sqrt s)$$$, although this can be easily optimized to $$$O((n+ \sqrt s)log(n))$$$, if binary search is used to check whether the new elements are already present in $$$a$$$.

The optimal solution has a runtime complexity of $$$O(N log S)$$$. Based on hints $$$3$$$ and $$$4$$$, we can find the value of $$$x$$$ with binary search. For some $$$x$$$, the sum of the elements in $$$a$$$ will be equal to $$$sum(x)=\frac{x\cdot(x+1)}{2}+\sum_1 v_i$$$, where $$$\sum_1 v_i$$$ is the sum of the elements greater than $$$x$$$.

Since the sum of elements $$$sum(x)$$$ is a monotonous function, we can use binary search on the interval $$$[1,\sqrt{2 \cdot s}]$$$ to find the exact value of $$$x$$$.

Final time complexity: $$$O(N log S)$$$