kostka's blog

[ACM] Central Europe Regionals 2014
By kostka, 9 years ago, In English

Today has finished the 2014 Central Europe Regional Contests.

Update: the contest is now at Codeforces' gym: 100543. Full ranking is here.

Congratulations to top three:

Rank University Score Time
1 University of Zagreb Stjepan Glavina Ivan ikatanic Katanic Gustav gustav Matula 10 1363 A***CDE**FHIJK**L
2 University of Warsaw Kamil Errichto Dębowski Błażej johnasselta Magnowski Marek mareksom Sommer 8 1067 AC**D*E**F*HIK**
3 University of Wroclaw Bartłomiej bardek Dudek Maciej Solaris Dulęba Mateusz matix2267 Gołębiewski 7 664 A*C*DE*FHIJK***

Additionally, to World Finals were qualified:

Rank University Score Time
7 Jagiellonian University in Krakow Piotr piob Bejda Grzegorz guspiel Guśpiel Michał m.sewcio Seweryn 7 950 A***CDE***F*HIK**
8 Charles University in Prague Filip fhlasek Hlásek Miroslav mirecek3 Olšák Štěpán simsa.st Šimsa 7 998 CDE*****F*HI*K**

The problems were really decent (7/12 was enough to go to Maroko :)). Check them out in gym.

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's worth to add that all three teams from Zagreb finished in top 10. It was really good performance by Croatian teams. Poland haven't won CERC since 2011 :(

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

Congratulations to Zagreb on wiping floor with us.

And to make it clear "7/12 was enough to go to Maroko" -> for some teams it was, but one cannot say that it was sufficient condition :(.

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

Full ranklist: http://cerc.tcs.uj.edu.pl/ranking/ I am quite shocked that Marcin_smu + Swistakk + pompon did not make it.

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

The third member of our team also has a Codeforces account. His handle is mirecek3.

Congratulations to all other finalists!

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

OK guys, so where are finals in 2016 :P?

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

The problems were really decent (7/12 was enough to go to Maroko :)).

If someone want to compare performance with teams from outside CERC — this problemset was also used at MIPT training camp (it is a preparation for NEERC, and most teams there are from NEERC), here are the standings.

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

    Wow, that's really interesting. The problem E seems much harder for NEERC teams than CERC teams. On the other side, you managed with problems K and L much better than our teams ;)

    How did you get the tests so fast? On the CERC website there is a note that "the contest data (problems, tests, and model solutions) will be posted at Sunday, November 23.".

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

      I have no idea about details, i am not one of organizers of that camp and also not a participant (well, i hope for next year:)) , i just decided that this problemset should be from CERC, asked one of participants from that camp — and he confirmed it.

      Maybe this camp is one of the reasons why contest data was not published right after contest, i don't know.

      And when we are talking about performance of teams on different problems — i think that it also depends on some random factors like time of first AC. If your team is not a top-level one — you may focus more on problem which is actually much harder, just because you saw that someone solved it fast... And it increases chances that you will also solve it, so other teams will see even more AC's on it... Snowball effect, you know:)

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

      Problem L was easy, that's why. The organizers said that many top teams should be ashamed of themselves for not solving it. (I did have first blood on it, that's why I can laugh.) Problem K, I found pretty hard.

      So the Russian teams are performing more in line of what I'd expect from top teams after seeing the problemset — but obviously better, considering how many solutions there are on B, G (yes, one!) and J.

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

        Marcin_smu in G got first few tests checking efficiency accepted, but gave only 49998 correct answers out of 50000 testcases in test focusing on correctness. The only thing he lacked was changing set to multiset : /.

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

          Really liked this problem. Unfortunately also didn't get AC during contest due to one stupid bug (see the picture below with difference between WA and AC). Anyway can you share your solution?

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

            Unfortunately I can't share my solution, because I don't have one :pp. Also I don't know how exactly marcin's solution worked, I'm really bad when it comes to strings... So good, that I have Marcin_smu in my team :pp. Ask him.

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

        Could not get the problem L accepted.

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

        Can you please share your approach for problem L? Do share the code along. Thanks.

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

          Don't doublepost...

          Compress the times into 2N (at most).

          Suppose that you know all living aliens in some time interval. Try all times when you could kill the most distant one, which splits the interval into two. With efficient processing of which aliens are alive in these intervals and updating it as you try all those times, you can do a DP with O(N2) states and O(N3) total complexity.

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

            I am sorry for that. I think, I got a feel of your solution, but wont total complexity be 600^3 around!? (That passes?) (You are compressing time intervals, so 2*N distinct times atmost, right?)

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

              And? It's DP, it has a good constant. 6003 isn't so much in this case, and it's worth a try even if you don't think it could pass. If it's too slow, you could try optimizing — but it wasn't necessary in my case.

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

              n ≤ 600 is very standard limit for O(n3) FYI.

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

              Thanks both of you , for your reply! :)

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

    Hah, Russian teams seem to be significantly better than European ones :P. Though only 9 AC to E seem very weird to me. I read it after contest and came up with a solution in 2 minutes or something xd. Congrats on solving B and J so many times (so big amount of lines of code...) and K (not an obvious one). And those statistics confirm my point of view, that L was not that easy.

    Maybe in usual contest we will try to code B and J, but we were literally flooded with unsolved problems, so we didn't think about them even for a while, because ranking told us not to do so. I needed few minutes for them to came up with solutions (after the contest), but I will spend long hours coding them xd.

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

      Can you explain your logic behind E ??

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

        You just need to notice that you lost if there is some small block between two larger blocks (like 4 2 4).

        Our "winning" states will be just two sequences: one increasing and the second one decreasing (for example: 1 2 4 8 | 2). We can keep these sequences (as bitmasks — I used two ints), because we have at most 213 states. We can just simulate everything: with every new block, we iterate over the previous combination and have two options: add it to the left or right.

        The full presentation of solutions is here, there are some nice figures to this problem.

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

      Can you give me a link to editorials published if any?

      → Reply