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.
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
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
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?
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]$$$:
- Walk #1. Change $$$(b_0, b_1)$$$ to $$$(b_0, (b_1 + b_0) \bmod 2)$$$.
- Walk #2. Change $$$(b_0, b_1)$$$ to $$$((b_0 + b_1) \bmod 2, b_1)$$$.
- Walk #3. Change $$$(b_0, b_1)$$$ to $$$(b_0, (b_1 + b_0) \bmod 2)$$$.
This idea is related to the fact that we can swap twoint 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:
- Walk #odd: a regular lower-triangular matrix $$$L$$$
- Walk #even: a regular upper-triangular matrix $$$U$$$
Therefore, if we want to get full score $$$(W = 3)$$$, this problem asks to decompose a permutation matrix $$$P$$$ into $$$P = L_1 U L_2$$$ (where $$$L_1, L_2$$$ is a regular lower-triangular matrix, and $$$U$$$ is a regular upper-triangular matrix).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:
- It is a basic knowledge in linear algebra, that multiplication of a regular matrix $$$X$$$ from left can be decomposed into finite number of "elementary row operations" starting from $$$A$$$.
- When $$$X$$$ is a lower-triangular matrix, we can decompose it into finite number of operations of the form "add row $$$j$$$ into values of row $$$i$$$ (where $$$i \lt j$$$)" (Operation Type A).
- Similarly, the multiplication of a lower-triangular matrix from right can be decomposed into finite number of operations of the form "add column $$$j$$$ by values of column $$$i$$$ (where $$$i \gt j$$$)" (Operation Type B).
So if we change $$$P$$$ to an upper-triangular matrix by performing Operation Type A, B (over $$$\mathbb{F}_2$$$) finite number of times in any order as you like, we can directly obtain $$$L_1^{-1}, L_2^{-1}$$$ and the final matrix $$$U$$$, which means that the problem is solved.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:
- Step #1. If $$$P_{1, 1} = 0$$$, there exists other $$$j$$$ that $$$P_{1, j} = 1$$$ (otherwise $$$P$$$ is not regular), so we can add column $$$1$$$ by values of column $$$j$$$.
- Step #2. Then, we can "eliminate" rows with $$$P_{i, 1} = 1 \ (i \geq 2)$$$, by adding column $$$i$$$ by values of column $$$1$$$.
We can then change the second column to $$$(*, 1, 0, \dots, 0)^\top$$$ in the similar way, and then... into the last column. Now we obtained the upper-triangular matrix.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 \lt 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?