PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: shanu_singroha
Tester: abhidot
Editorialist: iceknight1093
DIFFICULTY:
1604
PREREQUISITES:
None
PROBLEM:
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.
EXPLANATION:
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 isNo. Otherwise, the answer isYes. - 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.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
a.sort()
m1, m2 = a[-1], a[-2]
if m1 == m2:
print('Yes' if a.count(m1) <= (n+1)//2 else 'No')
else:
print('Yes' if a.count(m2) <= n-2 else 'No')