CNDY - Editorial

editorial
,
1

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 is No.

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')
2

There’s a problem in a testcase… where the array elements are 1 and 1 …
according to me distinct means different, but when you will slpit the array the element will be same in both splitted array and the output should come NO, but the output is YES…
Can you elaborate, Sir?

3

You want to split the array into two arrays such that each of them, individually, contains distinct elements.

So splitting [1, 1] into [1] and [1] is completely valid, since neither of the two arrays has repeating elements within itself.

The first sample case in the statement also clarifies this: you can note that there’s a 4 in both arrays there.