### Endagorion's blog

By Endagorion, 7 years ago, translation, ,

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!

•
• +321
•

 » 7 years ago, # | ← Rev. 3 →   -37 Thank you Endagorion~
 » 7 years ago, # |   -55 Wish you best of luck! ;)
 » 7 years ago, # |   +35 Thank you Endagorion, nice problem set! Especially loved the Flatland Fencing (problem D in Div1).
 » 7 years ago, # |   +17 I must say, C of Div.1 is very very unusual for me > <
•  » » 7 years ago, # ^ |   -13 Anyone could explain the hash-based solution to problem C? It seems to be very intersting.
 » 7 years ago, # |   0 When will the system test start?
•  » » 7 years ago, # ^ |   +14 After div2 testing finished I think. Today div2 got test first :)
 » 7 years ago, # |   +6 OK, still far from being red. Nice problem set, anyway I hoped I could do it better.
 » 7 years ago, # | ← Rev. 5 →   +72 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 1226917UPD2: during the contest it seemed very suspicious to me that he resubmitted using pascal, since the first submission was written in C++
•  » » 7 years ago, # ^ |   0 Yes, I remember him from one another round, where the code looked similar to some other account. There must be something going on.
•  » » » 7 years ago, # ^ |   +1 I'm very sorry that it happens. But as you see , I use language pascal. Maybe he (dnc1994) copied my code.
•  » » » » 7 years ago, # ^ |   -17 U r dead Mr. SAW.
•  » » » » » 7 years ago, # ^ |   -13 ? what's your meaning?
•  » » » » 7 years ago, # ^ |   +15 It is almost obvious that you are innocent here.
 » 7 years ago, # |   0 -7500 in Div 2 ?
 » 7 years ago, # |   0 When will my rating be update?
•  » » 7 years ago, # ^ |   +8 Let Div 1 system test be over first.Then ratings are updated
 » 7 years ago, # |   -15 Chapeau :)
 » 7 years ago, # |   0 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.:)
•  » » 7 years ago, # ^ | ← Rev. 2 →   +3 You can try to factor numbers in O(logN) time.
•  » » » 7 years ago, # ^ |   +3 Faster and easier is through eratosthenes sieve.
 » 7 years ago, # |   0 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
•  » » 7 years ago, # ^ |   0 oh nvm, my bad. got it now. sorry.
 » 7 years ago, # |   +16 The solution of problem c in div1 is using "hash" ? It's so unusal... And "map" will get TLE?
•  » » 7 years ago, # ^ |   -21 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.).
 » 7 years ago, # | ← Rev. 3 →   -34 I think there must be many participants ignored the vital constraint in problem A: Also, each pair has different letters and each letter occurs in no more than one forbidden pair. It is guaranteed that each letter is included in no more than one pair. I think writer should make it bold. It's codeforces, not readforces...
•  » » 7 years ago, # ^ |   0 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?
•  » » » 7 years ago, # ^ |   +3 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 %)
•  » » » » 7 years ago, # ^ |   +3 What kind so DP did you use?
•  » » » » » 7 years ago, # ^ |   +5 D(i,j) — minimum deleted characters for prefix of length i, and last undelete character is equal j.
 » 7 years ago, # | ← Rev. 2 →   -11 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 ?
 » 7 years ago, # |   +14 This contest is my favorites... Every problem are clearly presented... Thank you very much Endagorion
 » 7 years ago, # |   0 I think all problems is nice.Thank you Endagorion!Finally,pray for myself not to make mistakes.
 » 7 years ago, # |   +10 Is there any way to solve div1-C without hashing?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +15 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.
•  » » » 7 years ago, # ^ |   +8 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.. :(
•  » » 7 years ago, # ^ |   +26 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.
•  » » » 7 years ago, # ^ |   0 You ideas are good one~ Thank you very much!
•  » » » 7 years ago, # ^ |   -10 Is it really necessary to sort if you are using trie?
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 7 years ago, # ^ |   0 I have a problem. how about memery limit? For each vertices on trie,have 10^6 chilid!!
•  » » » » » » 7 years ago, # ^ |   +5 use hash-table:)You can see my implementations 1235766 (2970 ms) and 1235773 (1910 ms).
 » 7 years ago, # |   0 Are the editorials coming before the next round??
•  » » 7 years ago, # ^ |   0 It's finally done. Sorry for the delay.
•  » » » 7 years ago, # ^ |   0 is there English verson?
•  » » » » 7 years ago, # ^ |   +3
 » 7 years ago, # |   0 How to get the complete input data used by the system test?