avi_9314's blog

B — Find The Array
By avi_9314, history, 4 years ago, In English

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

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you share me the proof of the second approach? Seems kind of counter-intuitive to me.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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$$$.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ah thanks, makes sense. Should have realized this sooner.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Another Approach

I thought it'll fail the system testing, but it didn't, so here you go :)

→ Reply