Editorial for Yet Another Contest 8 P2 - No More Modern Art

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Josh

Subtask 1

It suffices to simulate all N! possible sequences of operations.

Time complexity: \mathcal{O}(N \times N!)

Subtask 2

Suppose a bucket with colour P is selected for the first operation, and a bucket with initial colour Q is selected for the second operation. For all other buckets, a bucket starting with colour A would end up having colour A \oplus P \oplus (P \oplus Q) = A \oplus Q. It is clear that the actual value of P does not affect the answer. In general, all buckets other than the last two remaining buckets before the final operation do not matter; the final colour is simply the XOR of the last two remaining buckets.

Thus, it suffices to loop through all pairs of elements, and check if the XOR of any of them is equal to X.

Time complexity: \mathcal{O}(N ^ 2)

Subtask 3

We can speed up subtask 2. Loop through the array and maintain a set of already seen values. When processing value a_i, we should check if a_i \oplus X is in the set, since a_i \oplus (a_i \oplus X) = X. If not, we should add a_i to the set and continue.

It's also possible to just create a set for the entire array at once, and do the above check for each element. However, be careful of the special case where X = 0; here, a_i = a_i \oplus X, so we need to check that there is an element occurring more than once.

Time complexity: \mathcal{O}(N) or \mathcal{O}(N \log N)


There are no comments at the moment.