PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
None
PROBLEM:
Given N, find a set of at most 40 permutations of the integers \{1, 2, \ldots, N\} such that the following condition holds:
- For each triplet (x, y, z) with 1 \leq x, y, z \leq N and x \neq y, x\neq z, y\neq z, there exists a permutation where x appears before y and y appears before z.
EXPLANATION:
The easy version, where we cared about pairs rather than triplets, was solved quite easily.
However, it should quickly become obvious that no such trivial solution exists here: even for N = 3 we’re forced to take all 3! = 6 permutations of [1, 2, 3].
Let’s start with the permutation P = [1, 2, \ldots, N], since we might as well do so.
Now, consider what happens if we reverse both the first and second halves, independently.
That is, we end up with the array \left[\frac{N}{2}, \frac{N}{2} - 1, \ldots, 3, 2, 1, N, N-1, N-2, \ldots, \frac{N}{2}+1\right]
Observe that between this new array and the initial array, we’ve in fact taken care of all triplets (x, y, z) such that x \leq \frac{N}{2} and \frac{N}{2} \lt z.
To see why:
- If y \leq \frac{N}{2}, either the first or the second permutation will contain (x, y) in the first half, depending on whether x\lt y or not.
Then the second half always has z. - Similarly, if \frac{N}{2} \lt y, (y, z) will appear in the second half of either the first or the second permutation depending on whether y\lt z or not, and x is always in the first half.
Of course, many other triplets will be satisfied too - but we focus on only these ones for now.
Observe that the fact that the two halves were [1, 2, \ldots, \frac{N}{2}] and [\frac{N}{2}+1, \ldots, N] didn’t really matter here (not even the fact that they’re halves matters, actually.)
If we partition the set \{1, 2, \ldots, N\} into any two subsets S_1 and S_2, the two permutations S_1S_2 and \text{rev}(S_1)\text{rev}(S_2) together will ensure that every triplet (x, y, z) for which x \in S_1 and z\in S_2 will appear.
(S_1S_2 here refers to the concatenation of S_1 and S_2, and \text{rev}(S_1) to the reverse of S_1.)
We can use at most 40 permutations.
Using the above strategy, each partition requires two permutations - so, if we’re able to find 20 different partition pairs (S_1, S_2), such that for any pair (x, z) with x \neq z there exists some partition where x is in the first set and z is in the second, we’ll be done.
There are probably several ways to achieve this - one of them is to look at binary representations.
If we have two different integers x and z, then surely their binary representations must also differ, i.e. there must exist some bit b that’s set in x but not in z, or vice versa.
We can use this fact to partition the elements.
For each bit b, let X_b denote the set of elements in [1, N] that have bit b set, and Y_b denote the set of bits that have b unset.
Then, the two partitions (X_b, Y_b) and (Y_b, X_b) together take care of all pairs (x, z) that differ at bit b, using four permutations in total (two for each partition, if you recall).
Since N \leq 250 \lt 256 = 2^8, we only need to care about 0 \leq b \leq 7.
Each bit requires 4 permutations, so with 8 bits we’re done in 4\cdot 8 = 32 permutations!
To recap, our construction is as follows:
- Fix a bit b, 0 \leq b \leq 7.
- Let X_b be the list of elements that have b set, and Y_b be the list of elements that have it unset.
- Add the following four permutations to the list:
- X_bY_b
- \text{rev}(X_b)\text{rev}(Y_b)
- Y_bX_b
- \text{rev}(Y_b)\text{rev}(X_b)
TIME COMPLEXITY:
\mathcal{O}(N \log N) per testcase.
CODE:
Editorialist's code (PyPy3)
n = int(input())
ans = []
for b in range(8):
x, y = [], []
for i in range(1, n+1):
if i & 2**b: x.append(i)
else: y.append(i)
ans.append(x + y)
ans.append(y + x)
ans.append(x[::-1] + y[::-1])
ans.append(y[::-1] + x[::-1])
print(32)
for p in ans:
print(*p)