Для того аби перевірити чи можна \(n\) предметів розділити порівну між \(k\) людьми, достатньо перевірити чи \(n\) поділиться націло на \(k\). Оскільки шоколадка має розміри \(n\) та \(m\), то загальна кількість шматочків рівна \(n \cdot m\). Тобто, у цій задачі потрібно перевірити, чи ділиться добуток чисел \(n\) та \(m\) націло на \(k\).
Для кожного робочого місця W спробуємо піти до усіх
можливих кавових автоматів C. Відстань між робочим місцем
на позиції \(i\) та робочим місцем на
позиції \(j\) буде рівна \(|i - j|\) — модулю різниці цих індексів.
Таким чином, ми можемо порахувати мінімальне значення з усіх відстаней
до кавових автоматів.
Складність такого розв’язку \(O(n^2)\), чого цілком достатньо для обмежень задачі.
Можна зробити вказаний в умові процес: допоки всі елементи масиву не рівні нулю, знаходимо найменший ненульовий елемент та віднімаємо його значення від кожного ненульового елемента. Проте такий розв’язок є неефективним, оскільки на кожному кроці процес знаходження найменшого ненульового елемента займає \(O(n)\) часу, а у гіршому випадку таких ітерацій може буде \(O(n)\), що дає загальну складність \(O(n^2)\). І цього недостатньо для повного балу у цій задачі.
Для розв’язання цієї задачі на повний бал необхідно помітити, що
кількість операцій, необхідна для перетворення масиву лише з нулів,
дорівнює кількості унікальних ненульових елементів у масиві. Для
обрахунку кількості унікальних ненульових елементів в масиві можна
використати структуру множина (set). Використовуючи цю
структуру складність розв’язку буде рівна \(O(n log(n))\).
Зрозуміло, що працівники будуть приходити на обід в порядку зростання їх \(t_i\). Будемо підтримувати змінну \(T\) — момент часу, коли місце для обіду стане вільним після останнього працівника, що обідав. Ця змінна нам дозволяє для кожного працівника одразу сказати чи він буде обідати чи просто так простоїть у черзі та й піде далі працювати.
Коли приходить працівник \(i\) на обід то існує 2 сценарії:
\(t_i \ge T\), тобто працівник приступить до обіду, не чекаючи жодного моменту часу. У даній ситуації ми можемо оновити змінну \(T\) значенням \(t_i + s_i\).
\(t_i < T\), тобто працівник змушений певний час почекати, а саме \(T - t_i\). Якщо це більше ніж максимальний час очікування \(i\)-го працівника, то цей працівник не буде обідати. Інакше цей працівник приступить до обіду в момент часу \(T\), а отже оновимо змінну \(T\) значенням \(T + s_i\).
Можна помітити, що якщо певний підмасив \(a_l, a_{l+1}, ..., a_r\) задовольняє умову задачі, тобто має кількість унікальних елементів \(\ge k\), то будь-яке розширення цього підмасиву (вправо чи вліво) також задовольняє цю умову. Тобто для \(l\) ми можемо знайти найменше значення \(r_l\), для якого буде виконуватись, що кількість унікальних елементів на підмасиві від \(l\) до \(r_l\) більша або рівна за \(k\). Зауважте, що для якихось \(l\) може не існувати такого \(r\).
Припустимо, що значення \(r_l\) та \(r_{l + 1}\) існують, то можна довести, що \(r_l \le r_{l + 1}\). Отже, можна використати техніку двох вказівників, щоб розв’язати цю задачу. Ітеруватимемось по \(l\) від \(0\) до \(n - 1\), будемо підтримувати змінну \(r\), таку що підмасив \(a_l, a_{l+1}, ..., a_r\) має хоча б \(k\) унікальних чисел. Відповідно до відповіді потрібно додати \(n - r\).
Щоб підтримувати кількість унікальних елементів, можна використати
структуру map (\(cnt\)),
підтримуючи як ключ власне елемент масиву, а як значення кількість його
входження на підмасиві. Якщо у \(cnt\)
ми будемо зберігати лише елементи, які є на підмасиві, тоді розмір \(cnt\) і буде кількістю унікальних
елементів. Для того аби підтримувати лише елементи на підмасиві треба
видаляти елемент з мапи, якщо кількість його входження в якийсь момент
стала рівна нулю.
Складність розв’язку - \(O(nlog_n)\).
У даній задачі необхідно порахувати кількість рядків, що задовольняють певну умову. У цьому випадку умовою є: “послідовний добуток дорівнює символу \(c\)”.
Використаємо метод динамічного програмування із таким станом динаміки: \[dp[cntA][cntB][cntC][\text{result}]\]
де \(dp[cntA][cntB][cntC][\text{result}]\) — це кількість рядків, що задовольняють таку умову:
у рядку є \(cntA\) символів \('a'\),
\(cntB\) символів \('b'\),
\(cntC\) символів \('c'\),
результат послідовного добутку рівний \(\text{result}\) (\(\text{result} \in \{'a', 'b', 'c'\}\)),
Переходи в задачі
Переходи можна задати з умови задачі: \[\begin{aligned} a \cdot b &= b \cdot a = c, \\ c \cdot a &= a \cdot c = b, \\ c \cdot b &= b \cdot c = a, \\ a \cdot a &= a, \\ b \cdot b &= b, \\ c \cdot c &= c. \end{aligned}\]
Тобто ми знаємо результат набору рядків, і перебравши останній символ, ми можемо визначити, який результат мав мати рядок без останнього символу.
Складність такої динаміки становить \(O(cnt_a \cdot cnt_b \cdot cnt_c)\), що підходить для розв’язання задачі за часом. Проте у пам’яті ми не можемо зберігати стільки станів, адже це призведе до перевищення ліміту.
Зауважимо, що перехід зі стану використовує інформацію лише з попереднього шару: \[dp[сntA][cntB][cntC][\text{result}] \rightarrow \begin{cases} dp[cntA - 1][cntB][cntC][\text{prev}], \\ dp[cntA][cntB - 1][cntC][\text{prev}], \\ dp[cntA][cntB][cntC - 1][\text{prev}]. \end{cases}\]
Використаємо звичний прийом оптимізації пам’яті пошарової динаміки. Можна тримати в пам’яті лише попередній шар (\(dp[cntA - 1]\)) для обчислення теперішнього \(dp[cntA]\). Таким чином, ми оптимізуємо кількість пам’яті до \(O(cnt_b \cdot cnt_c)\).
Розглянемо як ми можемо обмежити максимальну кількість, скільки можна поставити білих шашок. На краях поля не можна ставити шашки, бо їх там неможна буде побити. Також можна помітити, що коли чорна шашка б’є білу то номер рядка та стовпця в яких знаходиться чорна шашка змінюються на 2. Враховуючи це остача номера рядка та номера стовпця по модулю 2 не змінюється. Рядки в яких можуть знаходитись білі шашки мають мати остачу відмінну від остачі номера рядка чорної по модулю 2, аналогічно для стовпців.
Враховуючи усі попередні факти можна показати, що максимум можна поставити \(\lceil \frac{n - 2}{2} \rceil \cdot lceil \frac{m - 2}{2} \rceil\). Це можна робити якщо розставляти шашки в парних рядках та парних стовпцях (якщо пронумерувати рядки і стовпці в 1-індексації) і не знаходяться на краю поля:
І так сталось, що цю кількість справді можна так розставити і потім побити чорною шашкою за один хід.
Розглянемо випадок коли кількість білих шашок в рядку непарна (в рядках де є білі шашки). Будемо бити шашки по рядках: в першому рядку поб’ємо зліва на право, у другому справа на ліво і так далі:
Аналогічно можна бити якщо кількість білих шашок в стовпці непарна, просто симетрично будемо бити шашки по стовпцях.
Для випадку коли кількість білих шашок в рядку і стовпцю парна ми можемо зробити подібно до попереднього випадку. Пропустимо перший стовпець і поб’ємо усі інші стовпці так як раніше по одному рядку (б’ємо шашки справа від червоного стовпця). Після цього поб’ємо перший стовпець знизу догори.