Echoing Permutation#13045

Echoing Permutation (Editorial)

Solution

Let

m = n + 1.

m=n+1.

Define

P_{i} = p_{1} p_{2} \dots p_{i} (mod m),

P_i=p_1p_2\dots p_i \pmod m,

and let

P_{0} = 1.

P_0=1.

At position $i$ , we need to choose an unused value $p_{i}$ p_i such that

P_{i - 1} p_{i} \equiv b_{i} (mod m) .

P_{i-1}p_i\equiv b_i \pmod m.

Let

g = g cd (P_{i - 1}, m) .

g=\gcd(P_{i-1},m).

The congruence

P_{i - 1} x \equiv b_{i} (mod m)

P_{i-1}x\equiv b_i \pmod m

has a solution if and only if

g ∣ b_{i} .

g\mid b_i.

If this condition does not hold, there is no valid permutation.

Otherwise, define

M = \frac{m}{g} .

M=\frac{m}{g}.

After dividing the congruence by $g$ , we get

\frac{P _{i - 1}}{g} p_{i} \equiv \frac{b _{i}}{g} (mod M) .

\frac{P_{i-1}}{g}p_i \equiv \frac{b_i}{g} \pmod M.

Also,

g cd (\frac{P _{i - 1}}{g}, M) = 1.

\gcd\left(\frac{P_{i-1}}{g},M\right)=1.

Therefore, $\frac{P _{i - 1}}{g}$ \frac{P_{i-1}}{g} has a multiplicative inverse modulo $M$ .

Hence, $p_{i}$ p_i must satisfy exactly one residue condition

p_{i} \equiv r (mod M),

p_i\equiv r\pmod M,

where

r = \frac{b _{i}}{g} (\frac{P _{i - 1}}{g})^{- 1} (mod M) .

r= \frac{b_i}{g} \left(\frac{P_{i-1}}{g}\right)^{-1} \pmod M.

Thus, at every step we only need to find an unused number from one residue class modulo $M$ .

Why any representative works

Suppose

x \equiv y (mod M) .

x\equiv y\pmod M.

Since

P_{i - 1} = g q

P_{i-1}=gq

and

m = g M,

m=gM,

we have

P_{i - 1} x - P_{i - 1} y = g q (x - y) .

P_{i-1}x-P_{i-1}y = gq(x-y).

Because $M ∣ x - y$ M\mid x-y, it follows that

m ∣ P_{i - 1} x - P_{i - 1} y .

m\mid P_{i-1}x-P_{i-1}y.

Therefore,

P_{i - 1} x \equiv P_{i - 1} y (mod m) .

P_{i-1}x\equiv P_{i-1}y\pmod m.

So every number from the required residue class produces exactly the same next prefix product.

Now define

g_{i} = g cd (P_{i}, m)

g_i=\gcd(P_i,m)

and

M_{i} = \frac{m}{g _{i}} .

M_i=\frac{m}{g_i}.

Since

P_{i} = P_{i - 1} p_{i} (mod m),

P_i=P_{i-1}p_i\pmod m,

we have

g_{i - 1} ∣ g_{i} .

g_{i-1}\mid g_i.

Therefore,

M_{i} ∣ M_{i - 1} .

M_i\mid M_{i-1}.

Thus, every future modulus divides the current modulus.

So if two values are equal modulo the current $M$ , they also remain equal modulo every future modulus.

Therefore, all unused representatives of the current residue class are completely equivalent, and we may choose any of them.

Maintaining unused values

Every possible value of $M$ is a divisor of $m$ .

For every divisor $M$ , group the numbers $1, 2, \dots, n$ 1,2,\dots,n by their residue modulo $M$ .

For every residue class, keep a pointer to the first candidate that has not yet been checked.

When a residue class is requested, move its pointer while the current value has already been used.

If there is no unused value left in this class, then no valid continuation exists.

Otherwise, choose this value as $p_{i}$ p_i and mark it as used.

Finally, update

P_{i} = P_{i - 1} p_{i} (mod m) .

P_i=P_{i-1}p_i\pmod m.

Correctness

At every step, the condition on $p_{i}$ p_i is equivalent to belonging to exactly one residue class modulo $M$ .

Every value from this class produces exactly the required next prefix product.

Since all future moduli divide the current modulus, all representatives of this residue class remain equivalent for all future positions.

Therefore, choosing any unused representative is always safe.

If no unused representative exists, then no unused value can satisfy the current congruence.

Hence, the algorithm constructs a valid permutation exactly when one exists.

Complexity

Let $τ (m)$ be the number of divisors of $m$ .

For every divisor, every value may be processed only a constant number of times.

Therefore, the total complexity is

O (n τ (m))

O(n\tau(m))

time and

O (n τ (m))

O(n\tau(m))

memory.

m = n + 1.

P_{i} = p_{1} p_{2} \dots p_{i} (mod m),

P_{0} = 1.

p_{i}

P_{i - 1} p_{i} \equiv b_{i} (mod m) .

g = g cd (P_{i - 1}, m) .

P_{i - 1} x \equiv b_{i} (mod m)

g ∣ b_{i} .

M = \frac{m}{g} .

\frac{P _{i - 1}}{g} p_{i} \equiv \frac{b _{i}}{g} (mod M) .

g cd (\frac{P _{i - 1}}{g}, M) = 1.

\frac{P _{i - 1}}{g}

p_{i}

p_{i} \equiv r (mod M),

r = \frac{b _{i}}{g} (\frac{P _{i - 1}}{g})^{- 1} (mod M) .

x \equiv y (mod M) .

P_{i - 1} = g q

m = g M,

P_{i - 1} x - P_{i - 1} y = g q (x - y) .

M ∣ x - y

m ∣ P_{i - 1} x - P_{i - 1} y .

P_{i - 1} x \equiv P_{i - 1} y (mod m) .

g_{i} = g cd (P_{i}, m)

M_{i} = \frac{m}{g _{i}} .

P_{i} = P_{i - 1} p_{i} (mod m),

g_{i - 1} ∣ g_{i} .

M_{i} ∣ M_{i - 1} .

1, 2, \dots, n

p_{i}

P_{i} = P_{i - 1} p_{i} (mod m) .

p_{i}

O (n τ (m))

O (n τ (m))