Last weekend the finals of Swedish Coding Cup took place. Results. Congrats to _h_ for winning!
The problems are available on Open Kattis; I think they are quite nice.
Last weekend the finals of Swedish Coding Cup took place. Results. Congrats to _h_ for winning!
The problems are available on Open Kattis; I think they are quite nice.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 163 |
| 4 | TheScrasse | 159 |
| 5 | nor | 157 |
| 6 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 146 |
| 8 | orz | 146 |
| 10 | BledDest | 145 |
It looks like the reference solution to Ligatures uses SIMD. If possible, how would one solve it without SIMD?
I'm embarrassed to admit that the intended solution is the quadratic time bitset one, and I don't know of any subquadratic one. It should be possible to do it with regular 64-bit numbers at most 4x slower than the 0,37 s AVX2-based one on the Kattis leaderboard, which should pass, though you might have to do a fair bit of constant factor optimization.
(I think it's an interesting exercise though precisely how to apply bitsets here, IMO it's far from obvious.)
How to see reference solution ?