Масив і ще кілька масивів#222

Масив і ще кілька масивів (Розбір)

Оскільки всього елементів рівно , вони мають бути попарно різними й лежати в , то після зсувів вони утворюють перестановку чисел від до . Зокрема, значення обов'язково має бути покрите.

Це і є ключ до розв'язку. Зсув зберігає порядок усередині масиву, тому якщо масив покриває значення , то це може бути лише його найменший елемент — усі інші перейдуть у більші числа. Отже, для цього масиву зсув визначено однозначно:

d_i = 1 - \min(a_i).

Далі міркування повторюється: після того як частина масивів розставлена, найменше ще не покрите значення знову має покриватися мінімумом одного з масивів, що залишилися, і це знову задає його зсув однозначно.

Отже, увесь вибір зводиться до порядку, у якому масиви «займають» найменші вільні значення. Оскільки k \le 5, таких порядків щонайбільше 5! = 120 — їх можна просто перебрати пошуком у глибину.

Для кожного часткового порядку перевіряємо два обмеження:

  • після зсуву всі елементи масиву лежать у ;

  • вони не перетинаються з уже зайнятими значеннями.

Множину зайнятих значень зручно тримати як бітову маску довжини (bitset у C++). Тоді перевірка перетину — це одне побітове І, а додавання масиву — одне АБО; кожна операція коштує . Зсунуту маску масиву теж отримуємо зсувом бітсета.

Загальна складність — приблизно \mathcal{O}(k! \cdot k \cdot n / 64), що при n \le 10^4 і k \le 5 працює миттєво.

Якщо жоден порядок не спрацював, відповіді не існує — виводимо No. Інакше — Yes і знайдені зсуви; зверніть увагу, що вони можуть бути від'ємними.