here are some solutions to the problem B of yesterday educational round
approach 1 : find the nearest power of 2
simple implementation : 101610177
using builtin function : 101611194 101612390
using log function : 101611253
approach 2: alternate 1 at even and odd position ( rest elements = a[i]) and compute the sum 2* | a[i] -b[i]| for two different array and print the one with less sum
simple implementation : 101610719
Can you share me the proof of the second approach? Seems kind of counter-intuitive to me.
Let $$$c = [1, a_2, 1, a_4, 1, a_6, ...]$$$ and $$$d = [a_1, 1, a_3, 1, a_5, 1, ...]$$$.
Let $$$S_c = \sum_{i=1}^{n} |c_i - a_i|$$$ and $$$S_d = \sum_{i=1}^{n} |d_i - a_i|$$$.
Note that $$$S_c + S_d = \sum_{i=1}^{n} |a_i - 1| \leq S$$$.
Therefore, $$$min(S_c, S_d) \leq \frac{S}{2}$$$ and thus $$$2 \cdot min(S_c, S_d) \leq S$$$.
Ah thanks, makes sense. Should have realized this sooner.
Another Approach
I thought it'll fail the system testing, but it didn't, so here you go :)