MIRRIM - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

Starting from an initially all-white sequence of boxes, some of them were colored via the following process:

  • Choose two integers X_1 and X_2 with X_1 \lt X_2
  • Repeatedly choose an integer d with 0 \le d \lt X_1, and color boxes X_1-d and X_2+d black.

Given the final set of boxes colored black, decide if they could’ve resulted from this process.

EXPLANATION:

The colored boxes are A_1 \lt A_2\lt\ldots \lt A_N.

Observe that because X_1 \lt X_2, and each time we color a box to the left of X_1 we also color a box to the right of X_2 at the same distance,

  • Coloring box A_1 must have resulted in coloring box A_N.
  • Coloring box A_2 must have resulted in coloring box A_{N-1}.
  • Coloring box A_3 must have resulted in coloring box A_{N-2}.
    \vdots

In general, for each 1 \le i \le \frac{N}{2}, coloring box i is what must have resulted in coloring box N+1-i.

Now, if boxes A_i and A_{N+1-i} were colored together, this means that for the chosen mirror positions (X_1, X_2), there must exist an integer d such that A_i = X_1 - d and A_{N+1-i} = X_2 + d.
In particular, adding up both equations tells us that A_i + A_{N+1-i} = X_1 + X_2.

Note that we just took an arbitrary i to come to this conclusion - which means that this must hold for every index i with 1 \le i \le \frac{N}{2}.

So, the value of X_1 + X_2 is in fact fixed, and must equal the sum of any opposite pair of elements.
In particular, this means that every opposite pair of elements must have the same sum, i.e. we need the condition

A_1 + A_N = A_2 + A_{N-1} = A_3 + A_{N-2} = \ldots = A_{\frac N 2} + A_{\frac N 2+1}

where M = \frac{N}{2}.

If this condition doesn’t hold, the answer is immediately No.

If the condition does hold, the answer is always Yes: indeed, you can always pick X_1 = A_{\frac N 2} and X_2 = A_{\frac N 2 + 1}, and see that the mirroring works out.

Since the input is given already sorted, it takes \mathcal{O}(N) time to check this condition.

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()))
    ans = 'Yes'
    for i in range(n):
        if a[i] + a[n-1-i] != a[0] + a[n-1]:
            ans = 'No'
    print(ans)