https://szkopul.edu.pl/problemset/problem/l85hlaT4lDfPzwm3IPUHIMVo/site/?key=statement
I'm getting stuck at this problem. Could you give me a hint ? Thanks.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
05:43:44
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
05:43:44
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 11:51:17 (k2).
Десктопная версия, переключиться на мобильную.
При поддержке
Auto comment: topic has been updated by EternalFire (previous revision, new revision, compare).
Well, I am not able to think of any solution and looks like no one helped you so here is the code by ko_osaga if you didn't come across it yet.
Thank you.
Notice that for any 3 length AP , the first and last term must be of the same parity , hence if we can we can ensure that for every middle element , all elements with odd parity lie on left and all with even parity lie on right , we are done.
so just pick the middle element of 1..n , put all odd terms on left and all even terms on right , and recursively solve them.
But then won't all elements on depth two of the recursion be of the same parity? Can you explain the solution in a with some more details.
Let's look at the bits of each number. In depth K of the recursion we'll look at the Kth least significant bit.
In depth 0 we put all numbers with the first bit 0 at the left part, and the remaining on the right. Any arithmetic progression cannot contain 2 elements from both halves, so we recursively solve for the left part and right part, and now look at the second bit, and so on.
For each layer of recursion we do
time and there are 
layers.
I also thought that looking at second bit, third bit and so on, depending on layer will work, but I don't think it is correct.
It shouldn't work, because we want the equation a0 + 2 * d ≠ a2 to hold, which only forces the 0-th bit to be distinct.
On some layer K, we know that for all elements there, all the bits before the Kth one are equal, which forces the difference of an AP there to have all bits before the Kth be 0, which means all previous bits have no effect on the Kth one so this is exactly a subproblem.
okay , so for simplicity we assume N = 2m - 1 or N = 2m , if not we can always find the smallest such number ≥ N and remove the larger elements before printing.
lets say N = 15 , then middle element = 8 , all elements on left are 7, 9, 5, 11, 3, 13, 1, 15 , the ones on right are 8, 6, 10, 4, 12, 2, 14 its clear that the difference between consecutive elements is 2 so we can instead treat them by reducing to 1..N / 2.
This reduced the problem from 15 to 7 and 8 , 7 can be solved similarly , for 8 , we again pick 5 as middle element , push 1, 3, 5, 7 on left and 2, 4, 6, 8 on right and solve again. [ We basically just need to maintain that after splitting , differences is 2]
actually the 2n - 1 case is useless and we can go straight to the next power of 2 and get the usual ordering we do before FFT.