### Zlobober's blog

By Zlobober, 9 years ago, translation,

Tomorrow in Hungary starts CEOI 2012 — Central-European Olympiad in Informatics. It's very interesting contest, problems are quite hard in comparsion to other school olympiads. There will be internet-contest on same problemset: first tour at 9th July, second at 11th July; both tours will start at 08:00 UTC.

Rules — like on old IOI with test groups (group scores only if all tests in that group passed)

Registration closed tomorrow (08 July) at 18:00 UTC!

UPD: (possibly) rules changed this year.

UPD2: you should have recieved e-mail wih password and instructions. Rules indeed were updated.

UPD3: Contest server is veeeery slow so here is the mirror for the tasks (thx to popoffka):

Mirror

UPD4: Here is mirror for second day statements (thx to yeputons):

Mirror

• +42

 » 9 years ago, # |   +11 This year the rules will be different. There will be no groups and the contestants will see the result of theirs submission for every testcase immediately after they submit. There is also a limit on the number of submissions you can make. If Im correct it is 12.
•  » » 9 years ago, # ^ | ← Rev. 2 →   +8 Wow, that's interesting. So the rules placed here are wrong?
•  » » » 9 years ago, # ^ |   +5 The new rules were accepted yesterday on the meeting of team leaders and the rules on the web has been changed — actually only two sentences were changed ;-)
•  » » » » 9 years ago, # ^ | ← Rev. 2 →   0 And I still can't find any difference on the website :-( This remains the same: For each task the test data will be divided into batches, with each batch containing one or more test inputs. A test input is solved correctly if the submitted program produces a correct output file within the enforced limits. For output-only tasks test input is solved correctly if the corresponding output file submitted by the contestant is correct. A batch is solved correctly if each of the inputs it contains is solved correctly. Points are awarded only for correctly solved batches of inputs. 
•  » » » » » 9 years ago, # ^ | ← Rev. 2 →   0 You are right. There are still the old informations... It doesnt seem that they will manage to update the rules on web before the contest :-(It is also possible, that the online contest will run using the old rules...
•  » » » » » » 9 years ago, # ^ | ← Rev. 2 →   +5 Anyway thanks. We'll find it out tomorrow.If you are a contestant then good luck! Else good luck to all your students ;-)
•  » » 9 years ago, # ^ |   0 Really? If it's true, more people will take part in this contest (because people like me are too lazy to test their submitions well ;) )
•  » » » 9 years ago, # ^ | ← Rev. 3 →   +11 So, we should make more toures when you should test on traingngs? We will keep this in mind.
•  » » 9 years ago, # ^ |   0 12 for a single problem or for all?
•  » » » 9 years ago, # ^ | ← Rev. 2 →   +3 You can submit each problem at most 12 times and the best submission counts as final.
 » 9 years ago, # |   0 I am unable to access the contest server. Does anyone else have problems?This is the website url given to me: http://ceoisrv.inf.elte.hu/Day1
•  » » 9 years ago, # ^ |   0 It seems ok now.
•  » » 9 years ago, # ^ |   +2 UPD3: Contest server is veeeery slow so here is the mirror for the tasks (thx to popoffka): mirror
 » 9 years ago, # |   +1 What is the solution to Sailing Race ?
•  » » 9 years ago, # ^ | ← Rev. 2 →   +4 In the beginning we're using dynamic programming: a[i][j] — what is the maximal amount of stages, if we're beginning in harbor i, and are using the next j harbors after i (j can be negative as well, in which case we're using previous j harbors, but the solution will have the same idea, so I'll speak about next harbors only).a[i][j] = max by k in [i..i+j] (a[k][length of [i+1..k-1]], a[k][length of [k+1..i+j]) + 1This is basically the solution if k = 0, and now we need to deal with the case when k = 1.Then, if we know the first stage S -> T, it will divide everything in 2 pieces (at we will visit both of them). In the one we'll be visiting first, we can go only in one direction, otherwise we won't be able to cross to the other piece. Afterwards we will cross into the second piece, and we can go there as we want.Imagine we fix T and the side which we will visit first (left or right). Because in that piece we can only go in one direction, we get a directed acyclic graph, for which we can compute for every harbor the longest path from T to it. We can do it for O(N^2).Imagine the following O(N^4): we are now fixing not only T, but S and a new path X -> Y as well. The description of a total race is now as follows: S -> T -(in one direction)-> X -> Y -> ... .Now, we know how it is optimal to get from T to X, and we also can calculate for O(1) using previous DP how we need to go from Y.Now, let's shorten it to O(N^3). We won't fix X now. If we know S, T and Y, then we know the first piece, and it is always optimal to choose such a X, so that it is in the first piece, the edge X -> Y exists and the path from T to X is the longest possible. We can notice that in that condition S doesn't figure at all.So, before we fix S, for every harbor Y we calculate b[Y][k] — the maximum path to Y from some harbor X, where X is in interval {T, T+1, ..., k-1, k} and there exists a path X -> Y. b[Y][k] is either b[Y][k-1] or we get a new optimal X = k. Now all three parts of the case k = 1 are O(N^3).
•  » » » 9 years ago, # ^ |   +22 Actually,If we fix T and X,then you can see the closer S to X the better it is,so we just fix T and X and get the optimal S and enumerate Y to solve it..It's also n^3 and easy to write down.
 » 9 years ago, # |   +28
 » 9 years ago, # |   +9 The problems are interesting~but the server condition is too bad T_T...I always need to wait several minutes to fresh the page. T_T...could it be better in day2? (Maybe it's only in China...)
•  » » 9 years ago, # ^ |   +33 It's server's problems, not the Great Firewall of China. Me and my friend had to wait each page for minutes too.
•  » » » 9 years ago, # ^ |   +8 U two are top two in day1.. Admirable!
 » 9 years ago, # |   0 Is anyone able to access the Day 2 site? I get HTTP Status 404
•  » » 9 years ago, # ^ |   +1
•  » » 9 years ago, # ^ |   0 Not only you.
•  » » 9 years ago, # ^ |   0 Noone. Does anyone know how to contact admins?
•  » » » 9 years ago, # ^ |   0 I would suggest mailing to the mail from which the mails are coming: ceoi2012ic@gmail.com . But I doubt that they check it very often. If it's not automated at all.
•  » » » » 9 years ago, # ^ |   +3 I wrote them before the first contest and still got no answer.
•  » » » » » 9 years ago, # ^ |   0 I got in.
 » 9 years ago, # | ← Rev. 4 →   +28 The server is up now. All three problems are available here.UPD: sample.zip for the 'highway' problem is added.
 » 9 years ago, # |   -29 How to solve highway?
•  » » 9 years ago, # ^ |   0 I mean because of input and output.
•  » » » 9 years ago, # ^ |   0 people don't have time to answer "Yes". they just "-" the comment. so number of "-" = number of participants already solved the problem)
 » 9 years ago, # |   0 Can someone explain how to write Highway program? I created main.cpp, included "office.h", wrote my function which calls functions from office library, and uploaded — now I got "Compile time error". What is wrong? If anyone knows, please answer. Thanks in advance
•  » » 9 years ago, # ^ |   +3 Their provided .cpp for testing has a name "isOnline" while you should use "isOnLine".
•  » » » 9 years ago, # ^ |   0 Thank you !
 » 9 years ago, # | ← Rev. 2 →   0 I am solving this kind of problem first time and I dont know what's wrong with my program my code look like #include #include #include #include "office.h" #define MaxN 100001L using namespace std; main() { int n, i, j, k, b1, b2, t = 0, a1, a2; n = GetN(); /* if(isOnLine(i, j, k)) */ Answer(a1, a2, b1, b2); return 0; } } server is giving An Error Occurred: java.lang.NumberFormatException: For input string: “0.000”
•  » » 9 years ago, # ^ | ← Rev. 2 →   0 Try to define a1, a2, b1 and b2, just to be sure, maybe? 0 isn't a valid argument for that funcion. Like 1, 2, 3 and 4. That's my best guess — I haven't experienced those errors. My last submission on this task was done some time ago though — at 12:10:46 (Hungarian time — 02:10:46 after contest has started).
•  » » » 9 years ago, # ^ |   0 Does it give you 20/20? Because I got 20/20, dunno what it means. Is it completely correct?
•  » » » » 9 years ago, # ^ |   +1 No, maximal score that you can achieve is 80/20. The test&grade system is very strange, slow and buggy.
 » 9 years ago, # |   0 what does mean undefined reference to 'GetN()' ?
•  » » 9 years ago, # ^ |   +3 Your program cannot find this function. :)
 » 9 years ago, # | ← Rev. 2 →   +5 Attention please! Contest was extended for 15 minutes — till 13:15 UTC!
 » 9 years ago, # | ← Rev. 2 →   +4 My solutions: wagons, highway, network
•  » » 9 years ago, # ^ |   0 I terribly sorry, but can you also upload your solutions from Day1. Thanks in advance :) And, as I understood from the Russian version of the thread, congratulations for your top scores in both days, a really amazing achievement!
•  » » » 9 years ago, # ^ | ← Rev. 2 →   0 Thank you.My solutions for the first day: jobs, race (it works about 6sec on my computer), circuit (it doesn't work well, I got AC by merging it with the naive solution).
 » 9 years ago, # |   0 It seems that the time limit for networks is a bit tight. I wrote an O(V+E) solution but I got TLE for the last testcase =(My solution is in the link below: http://pastebin.com/A5aP29fDAny idea how I can improve it?
•  » » 9 years ago, # ^ |   0 My bet is that the excessive use of STL structures might be guilty.
•  » » » 9 years ago, # ^ |   0 In that case, then it means that the time limit really is tight =(How do you reduce the number of STL structures? For example, I believe I need to use adjacency list to represent the graph, so I believe I will need a vector for that.
•  » » » » 9 years ago, # ^ |   +5 You can use lists instead of vector. See my solution of network for details (lines 32-35, 45, 110-111, 118-120).
•  » » » » 9 years ago, # ^ |   0 You can perfectly store the adjacency list in two arrays.
 » 9 years ago, # |   0 The results of the 2nd day. I will make the total results when CF ends.
•  » » 9 years ago, # ^ |   0 Well, the maximum score for highway is still 80. I'm fully disappointed by organization this year.
•  » » 9 years ago, # ^ |   0 А в памятке написано что все задачи по 100 баллов?Или может они эту задачу специально так и сделали?
 » 9 years ago, # |   +8 The total standings of CEOI 2012 online contest. Everyone with a score of 0 on both days is omitted from the table.
•  » » 9 years ago, # ^ |   0 Can you please share a script this page was generated with?
•  » » » 9 years ago, # ^ |   0 It's not a script. I use Excel. A lot. :D
•  » » 9 years ago, # ^ | ← Rev. 4 →   0 And organizers have added their total results as well. But my version is better because it has tied places :)Note that the results are preliminary (normalization of all tasks to 100, maybe?).
 » 9 years ago, # |   +16 Onsite ResultsWhy the best bronze is better then worst silver?
•  » » 9 years ago, # ^ |   0 Also, for the onsite the maximum seems to be 600 (at least 595). And I would like to know the task order used in that table.On the other note, judging by onsite results, this CEOI can be counted as relatively easy compared to the earlier ones.
•  » » 9 years ago, # ^ |   0 This is what I found on topcoder forum:"Yes, they are final. During the second day of the contest there were serious problems with problem Highway: problems with library — it was impossible to compile it; until the last hour of the competition the grader told most people had only 60 points even if their solutions were correct and maybe more problems i don't know about.This issue was a reason to change the classical distribution of medals. It worked as follows: Each contestant recieved a medal for the first day only (according to classical rules) and for the total score (in the same way) and finally he was assigned better of these two medals. This is also the reason why a person with less total score can have better medal."
•  » » » 9 years ago, # ^ |   0 This is just... awesome.Thanks for the info, anyway!