The European Girls' Olympiad in Informatics 2023 took place from 15th to 21st of July in Lund, Sweden. The results can be found here: https://egoi23.se/scoreboard/. Huge congratulations prvocislo for winning the contest and all other contestants who did incredibly well.

The tasks where authored by snowysecret, Pajaraja, MladenP, bestial-42-centroids, nigus, 4fecta and dj3500.

The problem where prepared by the scientific committee consisting of Cupcakess, nigus, simonlindholm, Xylofo, zehnsechs, deadkey and dj3500.

We also thank our testers: Petr, Eliden, Cauchico, Gullesnuffs and VladGavrila.

An online mirror is available with flexible start time on Kattis running until July 24.

The problems can also be found individually on Open Kattis or on the EGOI23 website. You are welcome to discuss the problems in the comments!

The difficulty ranges between Div2 C and Div1 F, and we are very happy about the quality of the problems.

We are looking forward to seeing you at EGOI 2024 in Eindhoven, the Netherlands.

The finals of Swedish Coding Cup took place recently. Results. Congrats to dukati8 for winning!

The problems are also available on Open Kattis; I think they are kinda nice. (Bonus problem: solve E in O(N + M) time with two monsters.)

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.

I wrote an article/blog about how to do fast modular multiplication:

https://simonlindholm.github.io/files/bincoef.pdf

tl;dr:

• avoid latency-bound loops
• dynamic modulus is slow, constant modulus is fast
• if you perform many multiplications with the same dynamic modulus, you can do what the compiler does and use Barrett reduction (involves some precomputation)
• it is actually possible to beat the compiler if you accept a result in [0, 2*MOD):

uint64_t reduce(uint64_t a) {
  return a - (uint64_t)((__uint128_t(-1ULL / MOD) * a) >> 64) * MOD;
}

Same goes for addition and subtraction: if you can live with a result in [0, 2*MOD), just do a + b or a - b + MOD and skip the range correction that brings the result into [0, MOD). Delay modular reductions far as possible, ideally combining them with multiplications. While being mindful of overflows, of course.

• on 32-bit, use Montgomery multiplication instead, to avoid __uint128_t
• if really desperate, combine Montgomery multiplication with SIMD; this runs 3x faster than Barrett reduction when AVX2 is available
• for larger numbers (e.g. multiplication of 64-bit numbers), use floating-point based methods

Hot on the heels of Finland's contest, the Swedish olympiad finals also took place this weekend, and for those who want to try out the problems, we have put up a site where you can participate during any 5 hour period during this week: https://pofinal19-open.kattis.com/.

If you don't have 5 hours to spare you can also look at the problems directly at https://pofinal19.kattis.com/. The last problem is IMO quite neat.

We just made KTH's ICPC team reference document open source. It contains a few nice things that I haven't seen elsewhere:

• Ergonomic API's for SCC, biconnected components, 2-SAT, angle sweepings, and monotone function partitioning.
• I don't recall seeing tridiagonal linear equation solving or tree compression in other TRD's, but they have definitely turned out useful from time to time.
• A large section on constant factor optimization, with notes about how to best do loop unrolling, bump allocation, SIMD. It also notes the existence of "#pragma GCC optimize ("Ofast")", which makes GCC auto-vectorize and unroll code to win a nice constant factor in code with tight loops.
• Fancy-looking 3-column layout!

For people with archaeological interest, we also have our old TRD available, with version control history going back to 2002. (Did you know that in 2003, the ICPC did not have a page limit for TRDs? KTH's was 129 pages pages long, and included four different bigint implementations. At one point it even contained a re-implementation of the STL, since that wasn't necessarily available on all platforms.)