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

None

PROBLEM:

Define a function f(x, y) as follows:

f(x, y) = \begin{cases} -1, & \text{if } x < y \\ 0, & \text{if } x = y\\ 1, & \text{if } x > y \end{cases}

You’re given an array A containing only integers in [-1, 1].
A can be rearranged however you like.
Then, starting with x = 0, set x \gets f(x, A_i) for each i = 1, 2, \ldots, N in order.

Find all possible final values of x.

EXPLANATION:

To better understand what’s going on, let’s make a table of f(x, y).
It looks like this:

\begin{array}{|c||c|c|c|} \hline f(x,y) & -1 & 0 & 1 \\ \hline\hline -1 & 0 & -1 & -1 \\ \hline 0 & 1 & 0 & -1 \\ \hline 1 & 1 & 1 & 0 \\ \hline \end{array}

where the left column denotes values of x, the top row denotes values of y, and the cell at the intersection of a row and column is the corresponding f(x, y).

From here, note that:

  • f(x, -1) = \min(x+1, 1)
  • f(x, 0) = x
  • f(x, 1) = \max(x-1, -1)

In particular, note that no matter how we arrange elements, zeros in the array won’t affect the value of x at all (because if A_i = 0, we’ll just have f(x, A_i) = x.)
So, we can ignore all zeros in A entirely, and work with only the occurrences of 1 and -1.

Each occurrence of -1 increases the value of x, while each occurrence of 1 decreases its value; though for each change we must ensure that we remain in [-1, 1].

So,

  • To maximize the final value of x, it’s optimal to first place all 1’s and only then place all -1’s; so that we get all possible increments without having to deal with decrements.
  • To minimize the final value of x, the opposite is true: first place all -1’s and then place all 1’s.

That is, the two rearrangements [1, 1, \ldots, 1, -1, -1, \ldots, -1] and [-1, -1, \ldots, -1, 1, 1, \ldots, 1] will give us the maximum and minimum possible final values of x.

Let L denote the minimum computed this way, and R denote the maximum.
There are then two possibilities:

  • First, we might have R-L \le 1, for example L =0 and R = 1 or L = R = -1.
    In this case, there’s nothing between L and R, so clearly L and R are the only possible values we can reach at all.
  • Second, we might have R-L = 2, which happens exactly when L = -1 and R = 1.
    It can be verified that this case can happen if and only if A contains at least two occurrences of both 1 and -1.
    In this case, it’s also possible to make x equal to 0 in the end: for example one construction is to take the array [-1, \ldots, -1, 1, \ldots, 1] and then move a single occurrence of -1 to the end, to obtain [-1, \ldots, -1, 1, \ldots, 1, -1].

So, in every case, the set of reachable values is exactly everything in the range [L, R].
Thus, after computing L and R, simply print everything in the corresponding range.

To implement this without pain, note that L and R are simply the values obtained when running the process on the sorted and reverse-sorted arrays, respectively.

TIME COMPLEXITY:

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

CODE:

Editorialist's code (PyPy3) 
def calc(a):
    x = 0
    for y in a:
        if x < y: x = -1
        elif x > y: x = 1
        else: x = 0
    return x

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    lo, hi = calc(sorted(a)), calc(reversed(sorted(a)))
    print(*range(lo, hi+1))
3 Likes