103503A — Make Sum Great Again
It is always optimal to add the smallest integer which is not already in the array.
The number of operations will never exceed $$$\sqrt{2 \cdot s}$$$.
Based on the first hint, the final array will be equal to $$${v_1,v_1,\ldots, v_n} \cup [1,x]$$$, for some $$$x$$$.
Hint 4: How can we find the value of $$$x$$$ faster than $$$O(\sqrt{s})$$$?
\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)$$$