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.
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
37:28:11
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
37:28:11
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 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 | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 04:06:49 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
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 ?
quite late, but it's here: https://github.com/Kodsport/swedish-coding-cup-finals-2021/blob/main/ligatures/submissions/accepted/sl_simd.cpp
Also, linking some resources Simon mentioned when I asked him about SIMD, in case they're helpful:
Happy to answer that question! :)
[https://stackoverflow.com/tags/sse/info] is a good overview. It links to e.g.:
[https://ppc.cs.aalto.fi/ch2/] is nice for explaining how to think about high perf.
[https://github.com/simonlindholm/simd-book/blob/master/book.tex] is the outline of a book I was planning at some point, with some links to problems I've applied SIMD on in fun ways (solutions in the same repo) and a write-up of fast simd modmul.
I will say that a majority of the time cheesing problems with SIMD takes more time than solving the problem for real; the main exception is when #pragma GCC optimize ("Ofast") + #pragma GCC target ("avx2") auto-vectorization happens to work out, which problem authors are pretty good about catching these days... But it's fun when you manage to come up with some over-complicated quadratic SIMD solution that does pass!