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.
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 :(
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 :(.
Full ranklist: http://cerc.tcs.uj.edu.pl/ranking/ I am quite shocked that Marcin_smu + Swistakk + pompon did not make it.
They were too.
We were too.
The third member of our team also has a Codeforces account. His handle is mirecek3.
Congratulations to all other finalists!
added :)
OK guys, so where are finals in 2016 :P?
At Kochi (Kerala) I believe Amrita School of Engineering , Amritapuri is hosting the WF 2016
I think India
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.
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.".
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:)
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.
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 : /.
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?
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.
Could not get the problem L accepted.
Can you please share your approach for problem L? Do share the code along. Thanks.
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.
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?)
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.
n ≤ 600 is very standard limit for O(n3) FYI.
Thanks both of you , for your reply! :)
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.
Can you explain your logic behind E ??
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.
Can you give me a link to editorials published if any?
Editorial
Thanks!