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.

# | User | Rating |
---|---|---|

1 | tourist | 3751 |

2 | Benq | 3727 |

3 | cnnfls_csy | 3691 |

4 | Radewoosh | 3651 |

5 | jiangly | 3632 |

6 | orzdevinwang | 3559 |

7 | -0.5 | 3545 |

8 | inaFSTream | 3478 |

9 | fantasy | 3468 |

10 | Rebelz | 3415 |

# | User | Contrib. |
---|---|---|

1 | adamant | 178 |

2 | awoo | 167 |

3 | BledDest | 165 |

4 | Um_nik | 164 |

5 | maroonrk | 163 |

6 | SecondThread | 160 |

7 | nor | 157 |

8 | -is-this-fft- | 154 |

9 | kostka | 146 |

10 | Geothermal | 144 |

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.

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/27/2023 07:23:10 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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 ?