NEWOP - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

You’re given an array A.
In one move, you can choose an index i and replace A_i with A_i + 2A_{i+1}, and delete A_{i+1}.
Find the minimum and maximum possible values of the last remaining element.

EXPLANATION

Observe that each time an element is merged to its left, its value will double.
This applies across multiple merges: for example if we have [x, y, z], then:

  • Merging y and z into y+2z doubles the value of z.
  • After that, merging (y+2z) into x gives the value x + 2y + 4z, so the coefficients of both y and z have doubled.

Also,

  • Every element except A_1 must be merged to its left at least once, for us to end up with a single element in the end.
  • The element A_i can be merged to its left at most i-1 times before it ends up being part of the leftmost element (and thus cannot participate in any more leftward merges).

So, because all array elements are positive,

  • The minimum final value is obtained by ensuring that each element doubles as little as possible.
    • This means the best we can do is
      A_1 + 2\cdot (A_2 + A_3 + \ldots + A_N)
    • It’s easy to see that this value is achievable by performing operations left to right, i.e. with indices i = 1, 2, \ldots, N-1 in order, so that each element merges to its left exactly once.
  • The minimum final value is obtained by ensuring that each element doubles as much as possible.
    • Since element A_i can merge left at most i-1 times, this means the best we can do is
      A_1 + 2^1\cdot A_2 + 2^2\cdot A_3 + 2^3\cdot A_4 + \ldots + 2^{N-1} \cdot A_N
    • It’s easy to see that this value is also achievable by performing merges in order from right to left, i.e. with indices N-1, \ldots, 2, 1 in order.

So, the minimum final value is

A_1 + 2\cdot (A_2 + A_3 + \ldots + A_N)

and the maximum is

A_1 + 2^1\cdot A_2 + 2^2\cdot A_3 + 2^3\cdot A_4 + \ldots + 2^{N-1} \cdot A_N = \sum_{i=1}^N 2^{i-1}\cdot A_i

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    mn, mx = a[0], a[0]
    pw = 2
    for i in range(1, n):
        mn += 2*a[i]
        mx += pw*a[i]
        pw *= 2
    print(mn, mx)