Hello everyone. I'm Mikhail Tikhomirov and I'm the author of today round. I want to say big thanks to Gerald Agapov (Gerald) and Artem Rakhov (RAD) for great help in preparing this contest, and also Maria Belova for translating the statements into English (Delinur).
Today round is for contestants from both divisions. Each division has five problems, which intersect, as always. Score distributions are also standard (500-1000-1500-2000-2500). In short, it's a usual round. Or not?.. =)
Hope that problems will be interesting, tests will be secure, server will be fast, solutions — (mostly) correct, and the round will be rated. =) Wish you best of luck!
Round finished, thank you all for participating!
Results:
div1:
div2:
Editorial is finally up!
Thank you Endagorion~
Wish you best of luck! ;)
Thank you Endagorion, nice problem set! Especially loved the Flatland Fencing (problem D in Div1).
I must say, C of Div.1 is very very unusual for me > <
Anyone could explain the hash-based solution to problem C? It seems to be very intersting.
When will the system test start?
After div2 testing finished I think. Today div2 got test first :)
OK, still far from being red. Nice problem set, anyway I hoped I could do it better.
I just opened solution of zzy_troy for 155D - Colliders. And his solution happened to be the same as resubmited solution of dnc1994 after I challenged him.
Check it out: 1225624 1228387.
I think "someone" has multiple accounts.
UPD: also check out the hacked solution of dnc1994 1226917
UPD2: during the contest it seemed very suspicious to me that he resubmitted using pascal, since the first submission was written in C++
Yes, I remember him from one another round, where the code looked similar to some other account. There must be something going on.
I'm very sorry that it happens. But as you see , I use language pascal. Maybe he (dnc1994) copied my code.
U r dead Mr. SAW.
? what's your meaning?
It is almost obvious that you are innocent here.
-7500 in Div 2 ?
When will my rating be update?
Let Div 1 system test be over first.Then ratings are updated
Chapeau :)
I am getting TLE in Test Case 30 for the problem Colliders.Can someone tell me where to optimize it.Here's the code ->Link .I cant get it.Thanks in advance.:)
You can try to factor numbers in O(logN) time.
Faster and easier is through eratosthenes sieve.
Hey i'm curious as to how solutions to C handle cases like aaaabbbbaaabbba I tried a few correct solutions out but they give TLE or 0 as the answer o.O
oh nvm, my bad. got it now. sorry.
The solution of problem c in div1 is using "hash" ? It's so unusal... And "map" will get TLE?
What exactly do you mean by "map" and how do you know that map is too slow only by a constant factor? At least I could imagine that in some cases map compares people with many friends too often. (As an extreme example: Let's not use a map but sort the people (I guess this doesn't make a huge difference). The runtime depends on the internals of the sorting algerithm: The sorting algorithm might be "stupid" and first compare the two persons with the most friends with each other n times and then do quicksort. This sorting algorithm works in O(n log(n)) if comparison could be done in O(1) but it can take O(nm) when persons have to be compared lexicographically.).
I think there must be many participants ignored the vital constraint in problem A:
I think writer should make it bold. It's codeforces, not readforces...
That happened to me. But he did write it twice....
If you take out that restriction and allow letters to be in more than one pair, can it be solved with DP?
Most of the solutions that I read during the round ignored that restriction and used DP (so does mine). I was surprised when I tried to challenge solution that used the restriction and my test turned out to be incorrect %)
What kind so DP did you use?
D(i,j) — minimum deleted characters for prefix of length i, and last undelete character is equal j.
Interestring, my rating on the contest just went up, now I am 10th DIV2, I was 11th when contest ended. Also, may I know how soon will editorials be posted ?
This contest is my favorites... Every problem are clearly presented... Thank you very much Endagorion
I think all problems is nice.Thank you Endagorion!Finally,pray for myself not to make mistakes.
Is there any way to solve div1-C without hashing?
I think I found an O((n+m)log(n)) solution without hashing. Unfortunately it seems to be too slow by a constant factor. It works as follows:
(1) Let v(i) be the list of friends of i.
(2) Sort v(i). Create the list 1..n. Sort it by length(v(i)).
Then sort each chunk of this list with constant length(v(i)) by v(i) (lexicographically). , so this step takes at most time O((n+m)log(n)).
Afterwards you can easily divide this list into chunks with equal v(i) in time O(n+m).
This gives the number of doubles (i,j) which are not friends.
(3) Add i to v(i) and repeat step 2. This time you get the number of doubles (i,j) which are friends.
Lost of hashing cost about 1s, and time limited is 3s. Many solution in div1 got TLE, because of the big constant factor.I hacked by someone's big test , and got TLE too.. :(
It can be solved using trie that should implemented using hash-table (it is not hashing:) ).
You can find list of friends for every vertex. Now you should sort all of them and insert into trie. In some vertices of the trie you can count a number of lists that end in such vertex.
So, we have exact solution in O(MlogM) time with small constant.
You ideas are good one~ Thank you very much!
Is it really necessary to sort if you are using trie?
You should sort all numbers inside every list (because lists like {2,3,1} and {1,3,2} should be equal) and use a trie instead of sorting all of lists.
I have a problem. how about memery limit? For each vertices on trie,have 10^6 chilid!!
use hash-table:)
You can see my implementations 1235766 (2970 ms) and 1235773 (1910 ms).
Are the editorials coming before the next round??
It's finally done. Sorry for the delay.
is there English verson?
Here..