Zlobober's blog

CEOI 2012
By Zlobober, 12 years ago, translation, In English

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

  • Vote: I like it
  • +42
  • Vote: I do not like it

»
12 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.
        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
            ← Rev. 2   Vote: I like it +5 Vote: I do not like it

            Anyway thanks. We'll find it out tomorrow.

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

            → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 3   Vote: I like it +11 Vote: I do not like it

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

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    12 for a single problem or for all?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What is the solution to Sailing Race ?

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      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.

      → Reply
»
12 years ago, # |
  Vote: I like it +28 Vote: I do not like it

The results of the first day

→ Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it +28 Vote: I do not like it

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

UPD: sample.zip for the 'highway' problem is added.

→ Reply
»
12 years ago, # |
  Vote: I like it -29 Vote: I do not like it

How to solve highway?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I mean because of input and output.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

#include <stdlib.h>
#include <iostream>
#include <string>
#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”

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

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

        → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what does mean undefined reference to 'GetN()' ?

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Attention please! Contest was extended for 15 minutes — till 13:15 UTC!

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

My solutions: wagons, highway, network

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You can perfectly store the adjacency list in two arrays.

        → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Onsite Results
Why the best bronze is better then worst silver?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is just... awesome.

      Thanks for the info, anyway!

      → Reply