The European Girls' Olympiad in Informatics 2024 took place from 21st to 27th of July in Veldhoven, the Netherlands. The results can be found here. Huge congratulations prvocislo for winning the contest for the second year in a row and all other contestants who did incredibly well.
The tasks were authored by jasmin_studer, zoooma13, Sorting, bestial-42-centroids, nigus and Massimo Cairo.
The problem were prepared by the scientific committee consisting of nigus, simonlindholm, Xylofo, zehnsechs, SlavicG, flute42 and JanKuipers.
We also thank our testers: Petr, carolinux, Ante0417, mango_lassi, ainta, jasmin_studer and waynetuinfor.
An online mirror is available with flexible start time on Kattis running until July 29. The problems can also be found individually on Kattis (/Open Kattis) or on the EGOI24 website.
Test data and jury solutions are available at https://github.com/zehnsechs/egoi-2024-testdata.
You are welcome to discuss the problems in the comments!
orz
Cant wait to see all trans teams if they are allowed.
they would obliterate the competition
simps are mad at us :(
they hate the fact that men are better women than women
based.
prvocislo orz
prvocislo ORZ
prvocislo orz
berr orz
berr orz
berr orz
berr orz
berr ORZ
berr orz
berr orz
berr orz
berr orz
berr orz
berr orz
berr orz
berr orz
berr orz
berr orz
berr orz
berr orz
berr orz
berr ORZ
berr orz
berr orz
no
berr orz
no
Weobe orz :D
Weobe orz
Weobe orz
Weobe orz
Weobe orz
Weobe orz
Weobe orz
Veeon orz
Veeon, sysia orz
stanirina ORZ!
simona1230 orz
rahidilbayramli orz
how does one submit without joining the mirror?
It's possible on Open Kattis: https://open.kattis.com/problem-sources/European%20Girls%27%20Olympiad%20in%20Informatics%202024
I didn't know it's possible to add gifs to blog posts but this one is awesome!
AtinaRu kicika orz
CS50programmer rahidilbayramli orz
orz
clarinha ORZ top 4 with 4 attemps left
wow thats insanely cracked! good luck in her future attempts, it'll be cool to see the improvement!
Maybe top 4 -> top 3 -> top 2 -> top 1 -> top 0
fr lol goated
Congrats to the winners!
Which country is hosting the next EGOI?
Isn't this usually announced in the closing ceremony?
No one? Please!!
prvocislo orz
berr orz :D
What's the solution to "Where is Waldo?" from the practice session (and where to submit)?
EDIT: found it, https://github.com/Kodsport/swedish-olympiad-2022/blob/main/lager/whereswaldo/submissions/accepted/sl_pq2.cpp
Any plans to release the test datas?
Test data can be found at https://github.com/zehnsechs/egoi-2024-testdata. Jury solutions will be uploaded there after the mirror contest ends.
Is there any explanation as to why the 100-pt solution to lightbulbs has any sort of worst-case guarantee, given that it is randomized?
We don't have a proof for it, but we do have some hand-wavy intuition about why the uniformly random case should be the worst, and the solution we have uses at most ~65 queries on that so we figured there was a large enough margin. We do have a deterministic O(n / log n) solution as well but its constant is much too bad; it seems unclear whether 85 queries is doable deterministically.
What's the intuition?
Can you please summarize the randomization solution for us? Since it doesn't have an editorial.
Good job by the organizers, the problems were great! I encourage everyone try d1D and d2D (and full score d2C if you have a free week, lol)
Here is my solution to Day 1 Problem 4 "Garden Decoration". If you are going to participate in Online Mirror, don't see (I am writing now because the blog says we can discuss problems here):
First, we consider how to do it in case of $$$N = 2, A = [1, 0]$$$:
int a, b;
bya ^= b; b ^= a; a ^= b
.How the state $$$(b_0, b_1)$$$ changes in the solution of Idea #1 can be expressed as matrix over $$$\mathbb{F}_2$$$ (from the left; Walk 1, 2, 3):
which means that the final state will be
and this is why we can successfully "swap" $$$(b_0, b_1)$$$ into $$$(b_1, b_0)$$$.
Generalizing this, for each walk, we can multiply:
We consider $$$P = L_1 U L_2$$$ in the form of $$$L_1^{-1} P L_2^{-1} = U$$$. Here, since the inverse of a regular lower-triangular matrix is also a regular lower-triangular matrix, we can take any such matrices for $$$L_1^{-1}, L_2^{-1}$$$.
Let's review some linear algebra knowledges here:
Now the problem became simple: how to change $$$P$$$ into an upper-triangular matrix.
The first step is to change the first column into $$$(1, 0, \dots, 0)^\top$$$. We can do in the following way:
In conclusion, we can obtain $$$L_1^{-1}, L_2^{-1}, U$$$ in $$$O(N^3)$$$ time and we can calculate matrix inverse in $$$O(N^3)$$$ time, so we solved the problem in $$$O(N^3)$$$ time!
OIers, now it's time to learn linear algebra!
Anyway, if it is an intended solution, I will be really surprised.
I would be surprised too if this intended but there is a $$$O(n)$$$ solution by pure construction, one of our IOI team members found it during virtual. It's pretty nice imo.
we want to permute a sequence $$$a_1,a_2,...,a_n$$$ into $$$a_{p_1},a_{p_2},...,a_{p_n}$$$ via some xor operations. If we work backwards what should our sequence look like after the second round, call the sequence after the second round $$$b$$$.
$$$b_i$$$ should be the the xor of some subset of $$${a_{p_1},a_{p_2},...,a_{p_{i-1}}}$$$ together with $$$a_{p_i}$$$ for all $$$i$$$. — (1)
Now let's assume we have an algorithm that can produce such a sequence after round two for any permutation of any length $$$n$$$.
If $$$p_n = n$$$ we ignore $$$n$$$ and only solve for the first $$$n-1$$$ elements. Otherwise, in the first round we make $$$a_n = a_n \oplus a_{p_n}$$$ then we swap $$$p_j$$$ and $$$p_n$$$ such that $$$p_j = n$$$. And recursively solve for $$$p'_1,p'_2,...p'_{n-1}$$$ where $$$p'$$$ is the permutation of length $$$n-1$$$ after the swap.
The idea is since we are solving recursively, after the second round we can make $$$b_i$$$ = xor of some subset of $$$a_{p'_1},a_{p'_2},...,a_{p'_{i-1}}$$$ together with $$$a_{p'_i}$$$ for $$$i < n$$$. Now we add the operation $$$b_j = b_j \oplus b_n$$$ somewhere in the second round and we are done because the $$$a_{p_n}$$$ term in $$$b_j$$$ has been replaced with $$$a_{p_j}$$$ and $$$p'_i = p_i$$$ for the rest so (1) is fulfilled
Credits to isaachew
Congratulations berr! You deserved it well :D
Is it possible to give virtual after July 29th on any of the platforms?
Does anyone know which country is hosting EGOI 2025?
We knew the dates & host by this time last year.