1335E2 - Three Blocks Palindrome (hard version)
In this problem, the solution outlined by the editorial is $$$O(n*200*200)$$$, here $$$N$$$ <= $$$200000$$$.
How is the solution able to pass with that time complexity on a constraint like this?
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 163 |
| 2 | adamant | 149 |
| 3 | Um_nik | 145 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 135 |
| 7 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 132 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 15.05.2026 23:36:20 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
You pick a number (for first and third block) and iterate on its positions. Irregardless of the 'number' of numbers, there are only N positions in total to pick, thus the complexity is
O(N * 200). Of course you have to implement it in an appropriate way. Similar to how, when you DFS/BFS, you iterate on the children of a node, and you do it for every node! It seemsO(N^2)but there are only N distinct nodes to visit in total.