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):

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

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 I`m correct it is 12.

Wow, that's interesting. So the rules placed here are wrong?

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 ;-)

And I still can't find any difference on the website :-(

This remains the same:

You are right. There are still the old informations... It doesn`t 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...

Anyway thanks. We'll find it out tomorrow.

If you are a contestant then good luck! Else good luck to all your students ;-)

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 ;) )

So, we should make more toures when you should test on traingngs? We will keep this in mind.

12 for a single problem or for all?

You can submit each problem at most 12 times and the best submission counts as final.

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

It seems ok now.

What is the solution to Sailing Race ?

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]) + 1

This 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).

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.

The results of the first day

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...)

It's server's problems, not the Great Firewall of China. Me and my friend had to wait each page for minutes too.

U two are top two in day1.. Admirable!

Is anyone able to access the Day 2 site? I get HTTP Status 404

Nope.

Not only you.

Noone. Does anyone know how to contact admins?

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.

I wrote them before the first contest and still got no answer.

I got in.

The server is up now. All three problems are available here.

UPD: sample.zip for the 'highway' problem is added.How to solve highway?

I mean because of input and output.

people don't have time to answer "Yes". they just "-" the comment. so number of "-" = number of participants already solved the problem)

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

Their provided .cpp for testing has a name "isOnline" while you should use "isOnLine".

Thank you !

I am solving this kind of problem first time and I dont know what's wrong with my program my code look like

server is giving

An Error Occurred: java.lang.NumberFormatException: For input string: “0.000”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).

Does it give you 20/20? Because I got 20/20, dunno what it means. Is it completely correct?

No, maximal score that you can achieve is 80/20. The test&grade system is very strange, slow and buggy.

what does mean

undefined reference to 'GetN()'?Your program cannot find this function. :)

Attention please! Contest was extended for 15 minutes — till 13:15 UTC!My solutions: wagons, highway, network

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!

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).

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/A5aP29fD

Any idea how I can improve it?

My bet is that the excessive use of STL structures might be guilty.

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.

You can use lists instead of vector. See my solution of network for details (lines 32-35, 45, 110-111, 118-120).

You can perfectly store the adjacency list in two arrays.

The results of the 2nd day. I will make the total results when CF ends.

Well, the maximum score for highway is still 80. I'm fully disappointed by organization this year.

А в памятке написано что все задачи по 100 баллов?

Или может они эту задачу специально так и сделали?

The total standings of CEOI 2012 online contest. Everyone with a score of 0 on both days is omitted from the table.

Can you please share a script this page was generated with?

It's not a script. I use Excel. A lot. :D

And organizers have added their total results as well. <ad>But my version is better because it has tied places :)</ad>

Note that the results are preliminary (normalization of all tasks to 100, maybe?).

Onsite Results

Why the best bronze is better then worst silver?

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.

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."

link: http://apps.topcoder.com/forums/?module=Thread&threadID=753938&start=0&mc=3#1569751

This is just... awesome.

Thanks for the info, anyway!