NODOUB - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

For an array A, define f(A) as follows:

  • Start with S = H = 0.
  • For each i = 1, 2, 3, \ldots, N in order:
    • If S + A_i \ne 2S, add 1 to H.
    • Then, add A_i to S.
      f(A) is the final value of H.

You’re given an array A, find any rearrangement that maximizes f(A).

EXPLANATION:

We want to maximize f(A), which is equivalent to maximizing the number of times we encounter the situation S + A_i \ne 2S.
Note that this simplifies to just S \ne A_i, that is, we want to maximize the number of times the element we add does not equal the total sum so far.

Observe that one simple situation that ensures that the total sum is not equal to the next element; is simply when the total sum is very large.
In fact, as soon as the total sum exceeds the maximum element of the array, surely every further index will satisfy S \ne A_i; because A_i \ge 1 means the sum only keeps growing.

This naturally leads us to think about making the sum large quickly, which means placing large elements before smaller ones.

So, let’s start by placing the maximum element at the first position of the array.
Let M be this maximum element.
Next, we need to think about the second position.
Note that:

  • If A_2 \ne M, then we have no issues at this index.
    Further, after index 2, our sum is M+A_2 \gt M, so all further indices will automatically be satisfied too, no matter the order of elements.
    This means we’ll end up with f(A) = N, which is clearly optimal.
  • Note that the only time when we cannot enter the above case, is when every element of the array is equal to M.
    In this case, only one rearrangement exists anyway; so just print that rearrangement.
    Note that this arrangement has f(A) = N-1 (unless N = 1, in which case f(A) = N.)

So, quite simply:

  • If all the elements of A are equal, only one arrangement exists. Just print that one.
  • Otherwise, A has at least two distinct elements.
    Let M = \max(A).
    Place M at the first position, any element other than M at the second position, and then arrange the remaining elements however you like.

A simple way to implement this without any casework, is to place the maximum element in the first position, and then all remaining elements in sorted order.

TIME COMPLEXITY:

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

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))

    a.sort()
    ans = [a[-1]] + a[:-1]
    print(*ans)
1 Like