MAXMIN6 - 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:

Simple

PREREQUISITES:

Priority queues or sets

PROBLEM:

You’re given an array A of length N.
You can repeatedly multiply any element of the array by 2.
Find the minimum possible value of \max(A) - \min(A) that can be achieved.

EXPLANATION:

Since we’re aiming to minimize the difference \max(A) - \min(A), and we have only positive integers, which will be multiplied by 2 upon using an operation (and hence increase in value), it’s always optimal to multiply the smallest element by 2 in any given operation.

Any other operation will surely not decrease the value of \max(A) - \min(A), and in fact might even increase it.

Having this observation, we have a relatively straightforward algorithm: repeatedly choose the smallest element of A, multiply it by 2, and then update the answer with the current value of \max(A) - \min(A).

To do this quickly, we need a data structure that allows us to:

  • Find and extract the minimum element
  • Insert a new element into it
  • Find the minimum and maximum elements after insertion

All of these can be done quickly (in \mathcal{O}(\log N)) with the help of a set (std::set or std::multiset in C++, TreeSet in Java - notably hashsets will not work here) or a priority queue.

However, there is one small issue: when do we stop?
The process of multiplying elements by 2 can be done forever since we aren’t really given a limit on the values.

The key observation to be made here is that we never need to allow values to become too large.

Specifically, suppose M is the maximum element of the initial array A, before any multiplications are made.
Suppose we reach a state where every element of A is \gt M.
This would then mean that every element of A has been multiplied by 2 at least once.

But, doing this is never optimal!
This is because, if we reach such a state, then we could just not multiply every element by 2 a single time; and the range of the array will halve, which is clearly better for us.

So, any state where every array element has been modified, can never be optimal.
This means we can break out of the multiplication loop as soon as such a state is reached.

Note that this immediately bounds the number of operations: any positive integer needs to be multiplied by 2 at most \log_2 M times before it exceeds M, so the total number of operations before we break will not exceed N\log M.
Since each operation is performed in \mathcal{O}(\log N), this is fast enough.

TIME COMPLEXITY:

\mathcal{O}(N\log N \log (\max(A))) per testcase.

CODE:

Editorialist's code (PyPy3) 
import heapq
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    mx = lim = max(a)
    ans = max(a) - min(a)
    heapq.heapify(a)
    
    while a[0] <= lim:
        ans = min(ans, mx - a[0])
        mx = max(mx, 2*a[0])
        heapq.heappush(a, 2*a[0])
        heapq.heappop(a)
    print(ans)