Hello, Codeforces!
Educational Codeforces Round 6 will take place on 21 January 2016 at 18:00 MSK for the first and second divisions. You can read about educational rounds here and here.
<Your Ad Could Be Here>
The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.
If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.
</Your Ad Could Be Here>
Thanks a lot to Aleksa Plavsic allllekssssa who suggested several problems, two of them you will see on the round (the problems D and F). Also thanks to Bayram Berdiyev bayram, Allanur Shiriyev Allanur, Bekmyrat Atayev Bekmyrat.A. They are together suggested five problems, two of them you will see on the round (the problems B and E).
As usual the round was prepared by me, Edvard Davtyan. Thanks a lot to MikeMirzayanov we invented the problems A and C together. Also thanks to Maria Belova Delinur who will check English statements and Aleksa Plavsic allllekssssa who help me with problem testing and have constantly been in touch.
The first problem is pretty simple, so I'm waiting fast accepteds from you. The last problem is pretty difficult, so respect to all particiants who will solve it. I hope you will enjoy the problems!
Good luck and have fun!
UPD 1: I forgot to thank all other users who already sent me the ideas for the problems. I'll try to give that problems to the next rounds.
UPD 2: The main part of the contest is finished. The phase of hacks is started.
UPD 3: The editorial is ready.
UPD 4: The round is over, the results is final.
Thanks Edvard for mentioning my friends and me. I'll really tried to give good and interesting tasks for contest. Possible you will see more our tasks in future rounds, that doesn't depend on me :)
Enjoy in contest, as always I am glad to hear comments and suggestions after round.
Waiting for tourist with AC on last problem in 10 minutes.
I think no man on the world who can solve last task in 10 minutes :P
EDIT: Congratulation to tourist, he is incredible! But I am not counting his solution as regular :P
I can promise that he won't solve the hardest task in 10 minutes on my next round ( normally if he works it :D ).
tourist isn't a man, he's a SuperMan
Good tactic to invite tourist to contest :)
It took only 7 minutes for tourist to solve the last problem(judging by his submissions)
Actually he was able to solve the last one (problem F) in 7 minute .
We don't know it yet. It could be a hackable solution :)
These contests are sucks.
You mean this
I think it is first Turkmen contest.Good luck to everyone!And thanks to contest all problemsetters.
Ahahaha minus yagdyrayypdyrlaraooooow. allllekssssa-nam Turkmen edayipsina.
So, D is solvable by binary search right?
Maybe you can if instead of wasting time in writing comments , you make the changes :)
I am tired. Only the fact that I figured how to solve D kept me going. Now I'm watching youtube :) Commenting takes literally 1-2 minutes.
Am I the only who have passed pretests in B using 7-dimensional array? :D
Unfortunately we gave bad constraints to the problem F. As a result some participants solved the problem in O(n2). In spite of this some participants solved the problem with better complexity. The author solution works in time.
К сожалению в задаче F мы неудачно поставили ограничения и поэтому некоторые участники сдали решение за O(n2). Несмотря на это среди решений есть решения асимптотически более быстрые, но работающие примерно столько же. Авторское решение работает за .
Even author solution runtime does not explain such strange difference between limits on n and m.
Actually the hidden constants for m and n is different.
Sorry, I didn't answer before I had some other obligations.
I am setter of fourth and sixth task. The number of good submissions (till now) is great and I think this round is really good for education..
I only suggested tasks, with official solutions, so I didn't decide about final constrains for numbers and time limits. In my version(when I sent task) constrains were :
n<=10^5 m<=10^4 Ai<=10^12
And my estimation was that 5 seconds enough, but it is changed. Edvard is better programmer with more experience, so I beleive in his decision (and possible it is better to have more correct submissions — 8 good solutions in two hour aren't a lot of).
I hope you enjoyed in tasks and spent 2 great hours. See you on some other round, any suggestion and opinion about tasks will be helpful.
Так вот как её за 7 минут сдавать. Обидно :(
Да мы тоже сильно расстроились. Мы рассмотрели такую возможность, но у меня было другое наивное решение и как раз его я смог завалить такими ограничениями.
Nice contest overall! Russian statements was very clear, except maybe a bit lack of comments on math, like that (+) operation in F is XOR :) I know that, but I also know a lot of people who wouldn't figure out what operation it is. And they can't google for it I guess — hard to write search engine request.
The only flaw I see is difficulty gap between C and DEF. But it is probably very personal thing.
Problem title can help with this
Haha, nice. Well I haven't read problem title until this moment :D
Anyway, I'm kinda used to get such comments in statement, because they are often presented in regular contests (even easily googled ones like what is tree, what is subtree, etc).
I actually get to the clarification writing interface just to be sure, but when I selected problem I had to read the title
Everyone is trying so hard to hack tourist on problem A. well , my friendly advice to those desperate souls: "let it go, my fellow coders. Sad but truth is tourist can solve easy problems too beside hard ones"
I think i could not understand problem C properly. In the test case 5 2 2 3 3 3 will 3-5 be a good segment? if yes, then can a good segment contain more than two pearls of same kind, also two pearls each of two different kind?
Yes, and yes, and yes.
uhh i totally misunderstood the question. Got it accepted easily now. thanks!
Will the editorial be post after the end of hacking phase?
how to solve D?
I used the fact that after 1 change, answer is the minimum of absolute value of
sumA-sumB-2*a[i]+2*b[i]
to use binary search on b[] for closest value to (sumA-sumB-2*a[i])/2. Similarly, for making 2 swaps, you can make to arrays c[] and d[] where c has sum of pairs of elements of a[], and d has sum of pairs of b[]. Then, for each element in c[], binary search in d[]. This step has complexity n^2 log(m^2)
Tried similar thing, looks like tle on test 13: http://codeforces.net/contest/620/submission/15485606
me too, and i don't know why...
I just read editorial. Instead of storing pairs for both arrays in a map, just store for one and directly use the other from the loop. This leads to AC now
Maybe map has huge constants. Why not use a static array of size n^2 ?
http://codeforces.net/blog/Edvard
Hmm, my approach seems correct :)
The second problem is very annoying. Otherwise very good and interesting problemset.
I like how you wrote
Didn't knew we could do that!
Hm, interesting. I've submitted two AC solutions to D. Second one was a bit more optimized. And now first one got hacked. And I got penalty as if I made one WA submission before.
Feels fair, but didn't expected such thing :)
So basically I can submit as many AC as I want, and the first one which won't be hacked will be considered as accepted solution, right? And how about hacked ones? Will I get penalty for every one or how else it works?
In problem E , Why am I getting a RTE on test 51 . I am using Segment Tree on Time Stamps 15485066
Moreover what is the stack limit on Code Forces? Might be recursion is causing stack overflow ..
I got that problem too. You might use 2d arrays for the trees (i guess). Try using 1d arrays. I tried then time limited :D
During the contest i solved B casting every integer in the range [a, b] into a string (using
std::to_string()
) and then iterating the string with a range based for, and I got TLE (code here).Then I removed the
std::string
conversion and did the same thing extracting every digit from the number, using the same complexity [ O(b — a) ], and got AC in 15 ms (code here).Now on my pc the first solution, with the
1 1000000
tc, works in 130ms while the second one takes 40ms (I haven't got any kind of supercomputer or quantum computer and I compile with the same flags of Codeforces (C++11)). Now the question is: does codeforces hatestd::string
? isstd::to_string()
very very slow?I got 3 TLEs for this :(
I wish to say few more things about tasks and whole contest till now.
First I hope you find something interesting in problemset or at least you don't hate tasks :)
This was my help to codeforces, I do this only because of the passion for programming ( and I don't have girlfriend to spend time on it :D ).
I hope to see your problems on the following educational rounds, Edvard is great guy he finished good part of preparation and certainly he would help to new problemsetters. Also I'm always here for any help and question for anything needed.
I liked the contest, F was a though one :)
In problem C:
a submission with
unordered_map
fails with TL: 15496737a submission with
map
gets AC (only one line of code changed!): 15496747a submission with
unordered_map
and custom hash function: AC again! 15497036. Bit slower compared to map, anyway.What exactly is test 42? Looks like someone went through the trouble to generated an extremely bad test case input that causes huge number of collisions in that specific G++ implementation of unordered map. In my opinion, it's a bit against the spirit of the competition ;)
Against the spirit of the competition? Come on, it's just an unrated competition and also it's called an educational round ;) how so?
Hi kfx and sgtlaugh,
Can you please explain how having huge number of collisions give TLE? Shouldn't it give a Wrong Answer instead?
And also can you please explain how would one generate such a test case programmatically.
(My solution also got hacked due to the same reason)
Thanks a lot! :)
Now when the hacking is finished I want to ask something. On the A problem I found a solution with O(n) complexity, e.g. there was iterating from 10^9 to -10^9. I tried to hack it using x1=10^9 and x2=-10^9 and the hacking attempt was unsuccessful. However, on my laptop it run more than 2s and the limit is 0.5s. Is the limit actually higher or am I missing something?
Thanks.
Codeforces servers are very fast. Did you compile with optimization options like -o2 etc.?