First of all, I want to congratulate everyone who won medals. Special congratulations to everyone who won gold medals. And special special congratulations to Egor.Lifar who won eJOI 2018 by solving all 3 problems on Day 2.
I myself won a silver medal and I would like to write about some things I did wrong at the contest.
Focusing too much on a single problem
Most of the time at Codeforces Rounds it is perfectly fine to concentrate on one problem because all the other problems you haven't solved yet. On an olympiad, you never quite know which problem is easy and which is hard. At this eJOI, the problems on both days were sorted by expected difficulty, but at least I wasn't notified it was going to be in that order.
Thinking you cannot solve a problem
Entering the contest hall on Day 2, I thought the problems would be harder than Day 1 and I didn't expect to solve any problem. So I didn't even try to solve the whole problem A on Day 2, and I was pretty satisfied when I got 75. Seeing the results, it turned out yes the problems was harder, but not unsolvable.
Finding the balance between the hardness of a subtask and the number of points it gets.
Day 2 included an output only problem. The number of points you will get on an output only problem is usually hard to predict. I thought that it was more useful to work on my output only solution than to try to code some more subtasks on Cycle sort which I already had in mind. I decided to work on my output only solution which turned out to be a mistake. I got only 4 or 5 points more than I already had. Half an hour before the end of the contest I started coding those subtasks on the last problem but there wasn't enough time left.
I would like to make it clear this is only my second Olympiad in informatics and these are only some of my thoughts. If you have any piece of advice or thoughts, they are more than welcome.
Is that you, matthew99?
His blog post was the inspiration for this one xD
You forgot to talk about yourself in the third person and in a tense which assumes nothing actually happened (e.g "He would get 75 points and be satisfied with it, only to soon find out after the contest ends that the problem was, indeed, harder but not unsolvable).
What I have learned from this olympiad and the ones that I participated before
Never just wait till the olympiad finishes just because there are 10-15 minute left and you can't do anything at that time. At day 1 in the last 15 minutes I dropped from the 3-rd place to 5-th and in that 15 minutes I was doing completely nothing, I was just waiting till the contest finishes. But I now know that every minute is very important and you can always think about another subtask or just test your wrong code if you have one.
Never try to find the mistake in your code if you can't find it in 30-40 minutes, if you reached that limit, just stop and think about another problem, then when you get some points return to your unfixed code.
If there is an output-only problem like the one that was in olympiad try many ways to solve it, mostly the ways that are easy to code.
Don't think that you are doing bad or the problems are hard and you can't solve them, just concentrate on the problems (I know it is difficult sometimes, but I think it is always possible)
Don't try to solve problems fully, first try to think about subtasks that are easy to you and easy to code
I hope my advices will help someone in the future contests
P.S. Sorry if I made some mistakes in English.
I don't think that your decision to work on the output-only problem was a mistake — perhaps the mistake was in the way you used the time you spent on it. I don't know how you approached the problem, but if you have solved some marathon problems before there is a pretty easy method (it's called hill-climbing) to get 20-40 more points. If you just swap some node numbers on random and then look if there is an improvement, and only if there is, keep the swap, your score will be only increasing. For small tests this works pretty well because the possible states are small. This can be further optimized if you first run a greedy algorithm, so your initial state is already quite good. Of course, if you just run your solution for longer you can't expect much of a score increase. I am curious to see how you solved the problem and how you used the time to optimize your solution.
I see that you scored 82 on that problem. Did you use hill-climbing for that?
I tried many things but the best solution was
and then I was just writing all elements of the ans in output. I tried to optimise it a lot but it didn't work. I always got 49 points.
Could you share the statement of that output only problem?
You have a tree with N nodes and you have to label all the nodes with numbers from 1 to N so all the labels are distinct and you get as many edges that have the gcd of their ends equal to 1.
You may have more trees inside a file, you'll have to find a labeling for all the trees.
Grading system: Let R be the ratio of the number of bad edges and the total number of edges. if R > 0.4 you get 0 points on the test if 0.33 < R <= 0.4 you get 1 points if 0.26 < R <= 0.33 you get 2 points if 0.19 < R <= 0.26 you get 3 points if 0.12 < R <= 0.19 you get 4 points if 0.05 < R <= 0.12 you get 5 points if 0.01 < R <= 0.05 you get 6 points if 0.005 < R <= 0.01 you get 7 points if 0.001 < R <= 0.005 you get 8 points if 0 < R <= 0.001 you get 9 points if R == 0 you get 10 points per test
The test structure: Input file 1 -> 3 trees with 7 nodes each and you know how the trees look like (they are drawn on the statement) Input files 2 and 3 -> 100 random trees of 10 and 30 vertices respectively Input files 4 to 8 -> randomly generated trees with special structures (binary trees, trees with many leaves etc.) Input files 9 and 10 -> randomly generated trees with 50.000 and 100.000 vertices respectively
If someone could post a download link for the actual tests, that would be nice.