Пробудіть мене#12315

Пробудіть мене (Розбір)

Автор проблеми:	Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редаговано:	Хасан Салех (MathModel)

Рішення

Нехай $p$ буде перестановкою з ${1, 2, \dots, n}$ \{1,2,\dots,n\}. Умова

\forall i \in [1, n - k + 1] (j = 0 \sum k - 1 p_{i + j}) mod 2 = 1

\forall i\in[1,n-k+1]\quad \Big(\sum_{j=0}^{k-1} p_{i+j}\Big)\bmod 2 = 1

залежить лише від парності елементів, оскільки парні числа вносять $0$ за модулем $2$ , а непарні числа вносять $1$ .

Визначимо бінарний масив $s$ довжини $n$ :

s_{i} = p_{i} mod 2 \in {0, 1} .

s_i = p_i \bmod 2 \in \{0,1\}.

Тоді умова стає:

\forall i \in [1, n - k + 1] j = 0 \sum k - 1 s_{i + j} \equiv 1 (mod 2) .

\forall i\in[1,n-k+1]\quad \sum_{j=0}^{k-1} s_{i+j} \equiv 1 \pmod 2.

Отже, кожне вікно довжини $k$ масиву $s$ має непарну кількість одиниць.

Ключова властивість: періодичність

Нехай

S_{i} = j = 0 \sum k - 1 s_{i + j} (mod 2) .

S_i=\sum_{j=0}^{k-1}s_{i+j}\pmod 2.

Нам потрібно, щоб $S_{i} = 1$ S_i=1 для всіх допустимих $i$ . Порівняємо сусідні вікна:

S_{i + 1} \equiv S_{i} - s_{i} + s_{i + k} (mod 2) .

S_{i+1} \equiv S_i - s_i + s_{i+k}\pmod 2.

Оскільки $S_{i} = S_{i + 1} = 1$ S_i=S_{i+1}=1, ми отримуємо

- s_{i} + s_{i + k} \equiv 0 (mod 2) \Rightarrow s_{i + k} = s_{i} .

-s_i+s_{i+k}\equiv 0 \pmod 2 \;\Rightarrow\; s_{i+k}=s_i.

Отже, $s$ є $k$ -періодичним. Таким чином, $s$ повністю визначається шаблоном $b$ довжини $k$ :

b_{0}, b_{1}, \dots, b_{k - 1}, s_{i} = b_{(i - 1) mod k} .

b_0,b_1,\dots,b_{k-1},\quad s_i=b_{(i-1)\bmod k}.

Нехай $t = \sum_{j = 0}^{k - 1} b_{j}$ t=\sum_{j=0}^{k-1} b_j буде кількістю одиниць в одному періоді. Сума будь-якого вікна довжини $k$ дорівнює точно $t$ , тому умова виконується, якщо:

t непарне .

Відповідність кількості непарних

У перестановці кількість непарних значень фіксована:

O = # {1 \leq x \leq n : x непарне} = ⌈ \frac{n}{2} ⌉ = \frac{n + 1}{2} .

O=\#\{1\le x\le n: x \text{ непарне}\}=\Big\lceil\frac{n}{2}\Big\rceil=\frac{n+1}{2}.

Отже, ми повинні скласти $s$ з точно $O$ одиниць.

Запишемо $n = q k + r$ n=qk+r з $0 \leq r < k$ 0\le r<k. $k$ -періодичний рядок містить:

$q \cdot t$ q\cdot t одиниць з $q$ повних періодів,
плюс $x$ одиниць з перших $r$ позицій шаблону, де $x = \sum_{j = 0}^{r - 1} b_{j}$ x=\sum_{j=0}^{r-1} b_j.

Отже, нам потрібно:

q \cdot t + x = O .

q\cdot t + x = O.

Знаючи $t$ , ми маємо $x = O - q \cdot t$ x=O-q\cdot t. Тепер нам потрібно лише перевірити, чи може шаблон з точно $t$ одиницями мати точно $x$ одиниць у своїх перших $r$ позиціях.

Доступний діапазон для $x$

Ми вибираємо $t$ одиниць серед $k$ позицій; перші $r$ позицій є префіксом.

Максимум одиниць у префіксі: $min (r, t)$ \min(r,t).
Мінімум одиниць у префіксі: якщо ми розмістимо якомога більше одиниць поза префіксом (є $k - r$ k-r позицій), то принаймні $t - (k - r)$ t-(k-r) одиниць повинні бути всередині, тому:
$max (0, t - (k - r)) .$
\max(0,\,t-(k-r)).

Отже, для даного непарного $t$ можливість:

max (0, t - (k - r)) \leq x \leq min (r, t) .

\max(0,\,t-(k-r)) \le x \le \min(r,t).

Ми пробуємо непарні $t \in {1, 3, 5, \dots, k}$ t\in\{1,3,5,\dots,k\} і беремо перше можливе. Якщо нічого не підходить, відповідь $- 1$ .

Складання шаблону $b$

Після вибору $(t, x)$ :

Розмістіть $x$ одиниць у префіксних позиціях $0, 1, \dots, x - 1$ 0,1,\dots,x-1 (щоб префікс мав точно $x$ одиниць).
Залишилися $t - x$ t-x одиниць повинні бути розміщені поза префіксом (індекси $r, \dots, k - 1$ r,\dots,k-1), щоб зберегти кількість одиниць у префіксі незмінною.

Складання перестановки

Підготуйте два списки:

всі непарні числа в порядку зростання,
всі парні числа в порядку зростання.

Для позиції $i = 0.. n - 1$ i=0..n-1:

якщо $b [i mod k] = 1$ b[i\bmod k]=1, розмістіть наступне непарне,
інакше розмістіть наступне парне.

Це створює перестановку (кожне число використано один раз), і за конструкцією парність шаблону є $k$ -періодичною з непарною сумою періоду, тому сума кожного вікна довжини $k$ є непарною.

Складність

Для кожного тесту ми пробуємо максимум $k$ значень $t$ з кроком $2$ , тобто $O (k)$ , і будуємо перестановку за $O (n)$ . Зважаючи на $\sum n \leq 1 0^{6}$ \sum n\le 10^6, загальний час є лінійним.

Референсний код (Python)

for _ in range(int(input())):
    n,k=map(int,input().split())
    O=(n+1)//2
    q,r=divmod(n,k)

    t=x=-1
    for T in range(1,k+1,2):
        X=O-q*T
        if X<0: continue
        if max(0,T-(k-r))<=X<=min(r,T):
            t,x=T,X
            break
    if t<0:
        print(-1)
        continue

    b=[0]*k
    for i in range(x): b[i]=1
    y=t-x
    for i in range(r,k):
        if y==0: break
        b[i]=1; y-=1

    odds=list(range(1,n+1,2))
    evens=list(range(2,n+1,2))
    oi=ei=0
    ans=[]
    for i in range(n):
        if b[i%k]:
            ans.append(odds[oi]); oi+=1
        else:
            ans.append(evens[ei]); ei+=1
    print(*ans)

Python