The first ever European Girls Olympiad In Informatics (EGOI) is now over. You can view the scoreboard of the official contest on the EGOI 2021 webpage. Congratulations to the medalists, and in particular to Alisa Gladchenko AliceG and Ekaterina Shilyaeva AlFlen for the top scores!
We are also organising a virtual contest with the problems from the olympiad. The two contest days will be on codeforces. There is a 28-hour period during which you can take the 5-hour contest. The first contest will open in a few hours and last until midnight on Saturday, and the second will last from the start of Sunday to early Monday morning. All times are UTC+2!
Day 1: Friday 18.6. 20:00 — Saturday 19.6. 23:59 (EGOI 2021 Day 1)
Day 2: Sunday 20.6. 00:00 — Monday 21.6. 04:00 (EGOI 2021 Day 2)
Feel free to discuss the tasks here after the virtual contest frame ends.
A big shout out to the organisers and volunteers.
EDIT: Congratulations to ko_osaga for being the only one to fully solve Lanterns, and to Radewoosh for fully solving Double Move. I am sorry for messing up the settings of the virtual contest (which made it display only the first 5 hours for day 1, and no results at all for day 2). Unfortunately I do not know how to fix that :(
1
ig its to popularise CP among girls . Because , let's be honest, most of the participents in the IOI is male. Its based on the same concept of EGMO. You can read more about it here
I know most of the participants are male because they qualified in the national round . if,there are less female participant,thats not mean we have to create a gender based competition rather we should encourage them to participate and we should organize more camps. i will be not so surprised if I hear they launching another competition like ICPC for females....XD There will be no female gold medalist in IMO,IOI,ICPC because they will be preparing for gold in gender based ones rather than IOI,IMO..... We will never find great mathmaticians like Maryam Mirzakhani in IMO, because of THIS shits like EGMO,EGOI, EGOICPC
Women only competitions encourages them to participate in open division and there are camps that prepare national teams. And what's the difference between preparing for EGOI and IOI?
There is a huge difference between IMO and EGMO problems difficulty and preparation. I am sure that they will repeat this process in EGOI too.
Example : A participant in our country got silver medel in EGMO last year, but she didn't get chance in IMO team,last year. She placed 11th in IMO camp.She is not preparing for participating math olympiad in this year, because she is quite happy with EGMO medal achievement. I think the gender gap is increasing rather than decreasing by this gender based competitions
That's might be a problem. But I believe if a person happy with the EGMO silver medal the absence of EGMO won't make them an IMO medalist.
This year's EGOI problem set has interesting and challenging problems and they are good preparation for IOI.
I don't understand your logic very well. There are also other smaller/easier contests before IOI, such as BOI and CEOI. Is it also bad that those contests are organized, because someone may be happy after winning a medal in them?
We should organize more contest as much as possible both easy and hard ones. But I think Mind sports and olympiads shouldn't be gender based .
if you see the statistics of the IMO after the 1st EGMO held in 2012, sadly,the number of medalist among girl decreased. Samething happening with mind sports like Chess tournament for a long time.
I really appreciate the hard work of problemsetters in EGOI.
And lastly thanks for the CP handbook ,It helps me a lot in my CP journey. I am using 2nd handle in sake of my CONTRIBUTION
It is a good point that the number of female participants in IMO doesn't look good after almost ten years of EGMO. But do we know that it has decreased because of EGMO? Another possibility is that it would be even smaller without EGMO and there is some other reason why it has decreased.
'This year's EGOI problem set has interesting and challenging problems and they are good preparation for IOI.' Seriously?
Yes, I think even very high rated contestants should find some of the problems interesting :)
I have no objection to any contest, regardless how arbitrary the participant constraints are. And contest creators should be able to leverage participant restrictions to their liking — whether that means EBOI or EGOI, etc. Besides, I think one more contest is always better — especially given how rare they are (around 2 times a week). Olympiads are even rarer.
And you can apply the same argument to other contests, like pllk mentioned — if EGOI is invalid because it is easier than IOI, then perhaps BOI and CEOI should be done away with. And maybe even by that logic, Codeforces shouldn't exist because it is not representative of IOI.
There's nothing wrong with an easier olympiad with arbitrary participant constraints.
I'm doing the EGOI gym contest, and it seems like all the answers have been in queue for upwards of 30 minutes — CF or local issue?
lol, I was under an impression that EGOI meant the Egyptian Olympiad of Informatics.
So the virtual contest has just finished. Does anyone have an idea for the last 40 points of Lanterns? I used DP to get 60 points: For each starting lantern redo the whole DP. Let DP[A][B] = minimum amount you need to pay to finish your mountain walk, currently having lanterns which cover the range [A,B]. For the transitions you just try all lanterns that are reachable, increase the range, and overlap with your current range (You don't ever have to pick a lantern which doesn't overlap with your current range, because you can always pick it up later). This program is n times an $$$O(n^2*k)$$$ DP, which makes it $$$O(n^3 \cdot k)$$$, but apparently this was fast enough for 60 points. To optimize my solution, I didn't erase the whole DP table for every starting lantern, but kept track if a state in the table was the same range on the mountain, and if so, reuse this DP state, if not, solve this DP state again. This got me to testcase 68, which gave TLE.
Did you do 2nd one by DP ?
No, I did it greedily. For each friend from left to right, when we visit the rightmost of a pair, we just "move" the pair together in $$$distance-removed(p_1,p_2)$$$ steps and then delete them both. To calculate removed(l,r) (the amount of friends removed from l to r) fast we can use a binary indexed tree.
Great! Is it possible for you to share your code?
Here you go: https://ideone.com/K0MOwM
Thank you very much!!
I don't actually know the solution, but the editorial can be found here if you want.
Btw, I asked and the editorial solution for the last subtask is incomplete; it currently is wrong because it doesn't prevent the next lantern from being disjoint from your current lantern range. To deal with this, you have to keep track, for each segment tree, of which values are usable. Since you process a/b_i's in sorted order, you can just have a pointer keep track of the left/rightmost valid next dp transition (in terms of lantern range), and invalidate values as they slide out of the current lantern range.
Idk about the editorial solution, but my solution is pretty short and only uses priority queues.
Link
Note — it's not actually correct in the sense that it never outputs any number greater than or equal to $$$10^9+7$$$, but it passes the test data. :P
Hope you all enjoyed (not) solving this task!
The virtual contest "window" for the first day actually is not over yet, it "finishes" at 23:59 today (Saturday 6.19.2021) so it still lasts > 15 hours.
It turns out though that you cannot actually have a virtual contest last a specific time window on codeforces (at least we couldn't make that work). So instead, at 23:59 today, I'll go manually grab the current standings. After day 2's window ends, I'll do the same for that contest, and post combined virtual contest results somewhere here.
As for Lanterns, I have a solution different from the Editorial (The Editorial is based on majk's solution). I can share it here once the "window" for day 1 actually ends :)
In "Twin Cookies" instead of producing two subsets of the same sum, you can produce 5000 subsets of different sums, and ask for all of them in the last order.
Cool solution! We also figured out this, but only during the first contest day. I also believe Petr found a similar solution at around the same time.
This can even be implemented to run in $$$\mathcal{O}(n \log n)$$$, where the only $$$\mathcal{O}(n \log n)$$$ part is writing the output. I believe you need 14 queries for $$$n = 5000$$$.
I wonder if there is a even better solution, which uses more than one query that depends on your previous queries.
I don't know how to utilize more such queries, but I have found a better solution that needs only 10 queries (9 fixed and one dependent).
The idea is to generate a fixed set S with at least 5000 different differences between pairs of its subsets. I tried just to take 9 random numbers up to 10^6 and it worked (we need at least 9, since for k-set we can get at most (3^k-1)/2 differences).
The i-th query (for i <= 9) generates S_i+eps by asking numbers S_i * 10^5 + j (for 0 <= j < N). For the 10-th query we just ask for N differences, and return these two subsets of S that generate obtained difference (of course adding the difference to the cheaper subset).
My observation for that problem was basically "anything random works". I just made ceil(log2(N)) random disjoint queries, found a bunch of (arbitrary) subset sums and asked a final query to pick one of them.
It nicely shows what I don't like about too many constructive interactive problems: either anything works like here so the interactive part is just implementation, or you need some super specific idea, there's almost no middle ground. Here, it seems at first glance like a really interesting problem where you could have multiple options due to randomness but need to be a bit clever, but turns out you don't need to be clever, just to avoid straight out bugs or non-randomness.
By the beard of Zeus! I had a good time, thanks for the contest.
For C, I just output the first 101 * n random numbers and assumed I’d be able to find a solution where one of the sets has size 1. I was not expecting to get full credit for this — does someone have a proof or intuition why this works?
Edit: I read over your size of set=1, I don't know a proof for that.
I did kind of the same, and there's a proof for my solution. Say we take all subsets of the numbers you got, and we find set A and B with the same sum. Now these sets could be overlapping, but we could remove the overlap, as this would subtract the same amount of both. So now we want to find two subsets that have equal sum. There are 2^101 subsets, but the sum of elements in a subsets can only be up to 101*101*n. By the pigeonhole principle there must be two subsets with the same sum. Also you can choose to purchase less than 101 cookies (you only need 30 or so), to make finding of the subsets easier. I found the subsets with DP.
Oh my, after reading your proof I realized that I'd misunderstood the problem to require that each cookie should be given to exactly one of the twins. Even with this harder constraint my kind-of-similar solution where I only ever query the first 101*N numbers (difference: I allow terminating early before all 101 queries are used) worked...
It doesn't work, the interactor can always return a number that ends with ...01 (i.e. one that is $$$\equiv 1 \pmod{100}$$$). Then the last two digits of the sum of a subset are always the size of this subset (except subsets of size $$$100$$$ that give you 00). Note that we don't care about subsets of size $$$0$$$ or $$$101$$$, so we have $$$100$$$ possible subset sizes ($$$1 - 100)$$$ that each give us a different pair of last digits. In particular, if we have two subsets with the same sum, these subsets need to have the same size. Hence, if one set has size $$$1$$$, the other one also needs to have size $$$1$$$, which is impossible.
As a side note, if you print random numbers the probability that the interactor can always return a number $$$\equiv 1 \pmod{100}$$$ is around $$$(1 - (99 / 100)^n)^{101}$$$. For $$$n = 200$$$, this is $$$\approx 5 \cdot 10^{-7}$$$, so you're probably fine, but for $$$n = 1000$$$, this is $$$\approx 0.99565$$$, so you will very likely fail.
Well, I passed, so good to know I'm a lucky man! How does the scientific committee write interactors for problems like this? The space of cheese solutions like mine seems vast.
One thing I noticed about this contest is that it is really quite easy to artificially gain some brownie partial points with a solution that shouldn't really pass with better test cases. In particular, for Day 1 problem 2 and day 2 Problem 1, I fakesolved to get pretty decent partial credit on both of them (although I eventually got full marks with a complete solution).
I'm not sure if this is the organizers intention, though. And I guess making stronger preliminary tests may cause some logistical issues (and perhaps the point is to learn how to cheese)? Idk. Either way, I thought the problems were really cool (at least, the ones I could comprehend). In particular, it was nice to see a segment tree problem I could do :)).
What is the eligibility of the contest? I saw some countries outside Europe sent their team.
For this year, there wasn't much of a difference, except that countries outside Europe cannot vote on anything but the problems.
From next year on, contestants outside of Europe won't count for medal cutoffs.
I hope everyone enjoyed the problems (especially my problem, Luna :) )! It was nice to see so many solves both onsite and in the mirror.