simonlindholm's blog

Swedish Coding Cup finals
By simonlindholm, history, 3 years ago, In English

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.

  • Vote: I like it
  • +75
  • Vote: I do not like it

»
17 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It looks like the reference solution to Ligatures uses SIMD. If possible, how would one solve it without SIMD?

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.)

    → Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to see reference solution ?

    → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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:

      From Simon:
      → Reply