The European Girls' Olympiad in Informatics 2025 took place from 14th to 19th of July in Bonn, Germany. The results are here. Congratulations to all the contestants and especially the winner Veeon!
The tasks were authored by dozicca, Ivan Gaspardy, MeGustaElArroz23, misteg168, maomao90, pavement, Yoav, penguin133, prvocislo, veluca93.
The problem were prepared by the scientific committee consisting of flute42, jlohse, nigus, simonlindholm, TinyCodeArtist, Xylofo, zehnsechs.
As some of you have noticed, there is an online mirror (day1, day2) with flexible start times going on. It currently runs until Monday, but we will extend it to one week. The problems can also be found on Open Kattis.
The test data is available here. Solutions will be uploaded there after the mirror ends.
See you next year in Italy!
Is day 1 problem D link-cut tree?
Also, any hints for day 2 problem C?
Hi, you can find the official solutions here.
I think I have a slightly simpler solution for Day 1 D than the editorial that only needs std::set and Fenwick tree, but no LCA-like structures.
We start in the same way as the editorial by running Kruskal MST on the full graph. However, instead of constructing a Kruskal tree, we simply do small-to-large merging: when we need to merge two components, we take the smaller of the two and relabel it to the larger of the two.
Now, suppose we merge two components A and B, it means that we have found a new edge of the MST. Which [l, r] queries will this edge contribute to? All of them except the ones where there is a vertex from A and a vertex from B on the segment [l, r].
Now, supposing we draw all points from A and B on the line, we need to find pairs of adjacent points where one is from A and the other is from B. Supposing A was the smaller component, we can find the nearest vertex from B on both sides for each vertex from A (for example by keeping each component in a std::set), and then additionally exclude those cases where there is another vertex from A in between.
This way for each edge of the MST we get a set of non-intersecting (but possibly touching) excluded segments [ci, di], and need to subtract the weight of this edge from all queries that contain at least one of the excluded segments. The total number of excluded segments over all edges is O(nlogn) because of the small-to-large argument.
Now we do a sweep over queries in increasing order of the left boundary l, and maintain a Fenwick tree that for each MST edge stores its cost at the position di of the first excluded segment such that ci>=l. Whenever l passes the left boundary of an excluded segment ci, we need to subtract the edge cost at the position di and add it back at the position d(i+1). And whenever we want to process a query, we simply need to query the Fenwick tree with its right boundary r.
You can solve Day2C in M^5 / W using bitsets
Mirror is over, so jury solutions have been pushed to GitHub. For day 2 problem D I'm quite fond of the cheesy solution I came up with: https://github.com/egoi-org/egoi-2025/blob/main/day2/laserstrike/submissions/accepted/sl_rand.cpp
The decoder here uses a reseedable RNG for normalizing the information it gets into a bitstream that it outputs, and the encoder finds an ordering of the leaves that results in this bitstream being correct by recursive brute force. This encoding process has a success probability of O(1 / N), with the worst case being a line. In that case the encoder has two shots (because there are two leaves) at getting each bit to be guessed right (which is a 50/50), and by induction this gives a success probability of around 4/N. (Intuitively, if we consider the encoder recursion tree, the number of nodes on each level of the tree will be on average the same as on the parent level, and if we see it as a random walk the probability of it never reaching 0 is roughly 1/N, similar to how Dyck paths work.) We can retry with new initial RNG seeds until we get a successful encode and transmit this seed to the decoder. This solution requires O(log N + log #testcases) bits.
We can bring the encoding success probability up to O(1) (getting a K = O(log #testcases) solution) by observing that the worst case (lines) is actually easy to solve by other means, while if we have three or more leaves to choose from in the encoder then the success probability is constant because the number of nodes on each level of the recursion tree increases on average as you go deeper. So we can extend the decoder with a third option: with 45% probability it guesses a bit 0, with 45% it guesses 1, and with 10% it guesses that the tree has been reduced to a line and switches over to that algorithm. The success probability of this is high enough that we can get a 100 point submission with just above 10 resubmits, despite a decent number of lines and almost-lines in the test data.