CHFADJSUM - Editorial


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

Author: shanu_singroha
Tester: abhidot
Editorialist: iceknight1093






You’re given an array A. Let Z be the sum of its two largest elements.

FInd out whether there exists a rearrangement of A such that A_i + A_{i+1} \lt Z for each 1 \leq i \lt N.


Let M_1 and M_2 be the two largest elements of A, with M_1 \geq M_2.
It is enough to check whether there exists a rearrangement of A such that no occurrence of M_1 is adjacent to any occurrence of M_2.

There are two possible cases here: M_1 can equal M_2, or they can be different.

  • Suppose M_1 = M_2; let this value be M. We want to check whether A can be rearranged such that no two occurrences of M are adjacent.
    The absolute best we can do is to place instances of M at alternate positions, i.e, position 1, 3, 5, 7, \ldots
    So, the best we can do is \left\lceil \frac{N}{2} \right\rceil positions.
    Hence, if the count of M in A exceeds \left\lceil \frac{N}{2} \right\rceil, the answer is No. Otherwise, the answer is Yes.
  • Suppose M_1 \neq M_2. Then, there is exactly one occurrence of M_1 in A, so we need to check if all the occurrences of M_2 can be placed non-adjacent to it.
    Obviously, if every other element is M_2 (i.e M_2 occurs N-1 times) this is impossible.
    Otherwise, it’s always possible — for example, place all the occurrences of M_2 at positions 1, 2, 3, \ldots and place M_1 at position N.
    So, in this case it’s enough to check whether the count of M_2 equals N-1 or not.


\mathcal{O}(N) per test case.


Editorialist's code (Python)
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    m1, m2 = a[-1], a[-2]
    if m1 == m2:
        print('Yes' if a.count(m1) <= (n+1)//2 else 'No')
        print('Yes' if a.count(m2) <= n-2 else 'No')

hi , what I did was
considering 2 cases →

  1. maximum is repeated - if maximum is repeated-> if maximum is repeated n times
    then we need (n-1) gaps are created and we need to see if we have more than n-1 elements smaller than the maximum element.

2)maximum is not repeated and 2nd maximum is repeated then for n (2nd)maximum value n+1 gaps are created and we have to check if there are atleast n+1 elements other than maximum and 2nd maximum.

my approach couldnt pass 2 test cases can u tell me where am i wrong ( give me an example:))