COOLSUB - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: AkIII and Newtech66
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You’re given an array A.
A subsequence of this array is called cool if the average of every non-empty subsequence of the subsequence appears in the complement of the subsequence.

Find any cool subsequence of the given array.

EXPLANATION:

The condition of all subsequence averages being present in the complement subsequence is quite a strong one.

Suppose we fix the subsequence of elements S = \{x_1, x_2, \ldots, x_k\}, with its complement being A\setminus S = \{y_1, y_2, \ldots, y_{N-k}\}.
Then, certainly each of \{x_1\}, \{x_2\}, \ldots, \{x_k\} are themselves subsequences of S, so their averages must be present in A\setminus S.
The average of a single element is that element itself; so this condition just means that each x_i must be present as a y_j as well.

In particular, this means that each x_i occurs more than once in A; and our chosen subsequence can only contain elements that appear more than once.

So, if every element of A appears exactly once (i.e. A contains N distinct elements), it’s impossible for a cool subsequence to exist, and the answer is -1.

On the other hand, if some element x does appear multiple times, note that we can just take the single element \{x\} which will be a cool subsequence - the only average is x itself which is present in the complement since we know another occurrence of x is present.

So, the final solution is quite simple:

  • If all the elements of A are distinct, no solution exists.
  • Otherwise, print any 1-element subsequence \{x\} where x is an element that appears multiple times.

There are several ways to find an element that appears multiple times: for instance, you can sort A and look at adjacent elements, or use a set to store elements that have already appeared.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    s = set()
    done = False
    for x in a:
        if x not in s: s.add(x)
        else:
            print(1)
            print(x)
            done = True
            break
    if not done: print(-1)
2

Sorry if I am misinterpreting the question
Consider areay A=[1,2,3]. The subsequence [1,3] has its average in the complement and there is no repetition, but it is still valid right?

3

u have to take all non empty sub sequences of [1,3] so not only [1,3] but [1] and [3] also should be present in the compliment which isnt

1 Like