PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Arvind Khandelwal
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh
DIFFICULTY:
1018
PREREQUISITES:
None
PROBLEM:
Given an array A of 2N integers, can it be split into two arrays of length N, each containing distinct elements?
EXPLANATION:
Suppose we split A into B and C, each containing distinct elements.
Consider some element x. x can appear at most once in B and at most once in C.
Of course, this means x can appear at most twice in A.
This applies to any integer, so every x must appear at most twice in A.
It’s not hard to see that this condition is also sufficient, i.e, splitting into B and C is possible if and only if no integer appears 3 or more times in A.
Proof
If something appears 3 or more times, splitting is obviously impossible.
Suppose everything appears \leq 2 times.
For every element that appears twice, put one copy in B and one copy in C.
There are at most N such elements, so B and C both have length \leq N now.
The remaining elements can be distributed in any way to make B and C reach length N, since they will never break distinctness.
Checking this condition is fairly easy, and the constraints even allow for it to be done in \mathcal{O}(N^2):
- Fix an index i \ (1 \leq i \leq 2N)
- Run a loop over A to count the number of times A_i appears in A.
- If this count is \leq 2 for every i, the answer is
Yes
. Otherwise, the answer isNo
.
TIME COMPLEXITY
\mathcal{O}(N) per test case, or even \mathcal{O}(N^2) depending on implementation.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
print('Yes' if max(a.count(x) for x in a) <= 2 else 'No')