ARREQU - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: S. Manuj Nanthan
Tester: Harris Leung
Editorialist: Nishank Suresh

DIFFICULTY:

1281

PREREQUISITES:

Observation

PROBLEM:

Chef has an array A of length N. Can it be rearranged such that no two adjacent elements are equal?

EXPLANATION:

Let the maximum frequency of an element in A be M. Then, the answer is “Yes” if and only if M \leq \left\lceil \frac{N}{2}\right\rceil, i.e, 2\cdot M \leq N+1.

Proof
  • First, suppose that some element x appears strictly more than \left\lceil \frac{N}{2}\right\rceil times. Then clearly in any rearrangement, there will be two occurrences of x next to each other.
  • Next, suppose that every element appears \leq \left\lceil \frac{N}{2}\right\rceil times. A valid rearrangement can be constructed recursively as follows:
    • If N = 1 or N = 2, nothing needs to be done - any array is good.
    • Otherwise, let x and y be the two elements with highest frequency in A. Remove one occurrence of x and y from A, and solve it for length N-2 recursively (note that since we are removing the elements with highest frequency, the condition on maximum frequency still holds). Now, append either [x, y] or [y, x] to the solution obtained from N-2: at least one of these will not cause a conflict and we are done.

This gives us a simple solution:

  • Count the frequency of every element of A using some method (map in C++, dict/collections.Counter in python, sorting, etc)
  • The answer is “Yes” if the maximum frequency is \leq \left\lceil \frac{N}{2}\right\rceil and “No” otherwise.
  • To be safe and not have to deal with floating-point issues, check the condition 2\cdot M \leq N+1 instead of computing \left\lceil \frac{N}{2}\right\rceil.

TIME COMPLEXITY

\mathcal{O}(N) or \mathcal{O}(N\log N) per test case, depending on implementation.

CODE:

Editorialist's code (Python) 
import collections
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	freq = collections.Counter(a)
	print('yes' if 2*max(freq.values()) <= n+1 else 'no')