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.
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Dec/22/2024 22:59:54 (i2).
Desktop version, switch to mobile version.
Supported by
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!