Hello,everyone!
Codeforces Round #185 will take place on Sunday, May 26th at 19:30MSK (23:30CST).
This round is initiated by zanoes, and here are the problem setters:
- Div.1E & Div.2B —— zanoes (**Zhang Gaoxiang**)
- Div.1D & Div.1A —— liouzhou_101 (**Wang Qisheng**)
- Div.1C & Div.1B & Div.2A —— lydrainbowcat (**Li Yudong**)
Testers are roosephu(Luo Yuping), FredaShi(Shi Haoyue), sjynoi(Sun Jiayu), sevenkplus(Gu Yuzhou), MinakoKojima(Tang Feihu) and Riatre.
Especially thanks Gerald for helping us to prepare the round, MikeMirzayanov for the great platform and Delinur for translation.
Score will be standard, 500-1000-1500-2000-2500 in both divisions. In our opinion, problems are easier than the past several rounds prepared by Chinese)
This is our first Codeforces round, I hope you can enjoy it. Wish you high rating and good luck!
UPD: We feel really sorry about the mistake we made. The following words were written by Div.1A (Div.2C)setter, liouzhou_101. http://codeforces.net/blog/entry/7773#comment-134702 .
Meanwhile, It's also zanoes's and my fault that we didn't check his checker carefully, even brought troubles to Codeforces flat. I beg your forgive for liouzhou_101, for he also tried to prepare the round well these days.
UPD2: The round will be unrated.
Editorials will come out soon. Now you can find some of the editorials here: http://codeforces.net/blog/entry/7785
Contest is over. Congratulations to the winners.
Div.1
- zfmdhy786 (I promise it's someone who pretends to be roosephu, and I've known who he is.)
- cp12321
- RAD
- ACMonster
- kAc
And ryz , cgy4ever, who passed problem E in the contest.
Div.2
This is my first time to be a tester :). lydrainbowcat considered me as a good tester XD I'm sure all of the competitors will enjoy the problems! GL & HF!
Are FredaShi and lydrainbowcat a pair of lovers? :D
Of course!:D
Of course not!
It seems Chinese authors always posts announcements early.
hope to have a great round
I hope that this round will be easier! Thank you!
Why the real name of Riatre is hidden?
He told me that he didn't want to show his real name.
it seems to be a great contest because there are many people that direct the contest.
Guys, If anyone of you know some good source to learn and practice all types of dynamic programming problems, it would be really helpful for me..!! and yup, I am not sure if this is not the right place to ask such questions or there is some separate forum.
I think this is helpful
In www.jutge.org you can find several collections, and an special one for dynamic programming.
unfortunately, when you enter in www.jutge.org appears a message asking for accept a certificate. But it is not dangerous, you can accept, register, and use the judge without any problem.
rp+=your vote; wish all of you can get a good result :)
What did it mean?
If you have a high 'rp', you will be very lucky.
A lot of maths is observed in the every past Chinese contest. And every time when they said contest is gonna be easy, it was tougher than usual.
Right!And enjoy yourself><
I think the problems in this round are not too hard. One of the testers solved all the five problems of Div.1 successfully.
In 2 hours?
so if this is easy how would the hard one be?
+1
Comma separated contest IDs in a link ?? :O Really nice idea :)
I thought I had registered for the contest, but apparently I hadn't...
Is anybody but me see six problems for Div2?
Me too
It's just a bonus for those who solve Div2 E. Submit Div2 E's solution for Div2 F and you get more points than 2500 max. (Just joking :)
Thanks for this EASY contest!!
It seems that the problems are really very easy.
Yeah, so forking easy, I've managed to solve all 5 problems just pressing this button.
In the div2 contest, I can see 6 problems. But I can't see the Problem F. Is it a platform bug?
Yes
Is there any change about the problem:"Cats Transport"?
Believe me, I was pulling my hairs when I was reading problems D and E, The lines does not make sense to me despite of how many times I read those again. It is not so good to introduce too much mathematics in problem statements. The language seemed like some kind of cryptic language. I was very much frustrated while reading it. I can't imagine what would be the situation of person who is not so good in English.
Moreover there was no correlation of lines in the paragraph with each other. I am so frustrated with these problems. This is not at all a good translation work. Btw I am thinking that do the authors even try to read the problem to make sure that it is understandable in some definite amount of time ?.
easier than the past several rounds prepared by Chinese :) :| easier ?
1) Сходил пи-пи в начале контеста — слился в див 2
2) Задержал дыхание при написании А — стал красным.
Вот такой вот контест :)
Contest by Contest, Chinese writers are making it hard for me to believe their claims. :P
Contest is made in China.
so pity to see the unrated round. :(
hope that the next china round will be well-prepared.
CodeforcesReputation--; :|
Code forces will stay my favorite website forever
Codeforces is great and this has raised our expectation!
But this doesn't mean that this mistakes are not important.
We expect codeforces to be the best, not just good!
When everyone has worked hard in solving problems for nearly 2 hours , they say that contest will be unrated !! :(
contest unrated
this is very bad and intolerable
only that question should be out of rating
the desicion is condemned
Coincidence? The last two contests that I participated in became unrated (182, 185) :( Couldn't participate in the others as they were held at a different time slot.
Same here! It's been over a month since I've been able to participate in a rated Codeforces round. In the meantime, I've participated in 6 TopCoder contests!
same here !!
I have hacked a lot of solutions in Div1A (Div2C) and I didn't have any problems with that. I suppose not a lot of people are affected. It would be a wonderful idea to unrate this round only for affected people.
Good idea!
2 unsuccessful contests within 4 successive rounds, from 182 to 185......This is very very bad..
Problem D is very similar to problem E from NEERC Northern Subregional 2009
That's a coincidence. I haven't seen it before.
the problem has been discussed in winter-camp 2010 (by zej).
Hmmm, Gerald should be familiar with this problem, it's well known in Russia...
P.S. Nice solution :)
Hm, it's strange, but I didn't remember that problem. =(
It is in latest 25 blogs now :)
http://codeforces.net/blog/entry/4863
It's my fault that I've made an awful mistake on the checker of div1A&&div2C. Sorry to every participant and I feel most guilty. If I have a chance to prepare a round once more, I promise that I won't make such a mistake next time and we will make a successful round.
Good luck) Thanks for the tasks
Now why unrated contest? The hacks just can be retested..... 2 hours and a hard contest and now unrated....
everybody makes mistakes, next time you'll do better :)
As one of the authors could you tell please how many people were affected? Are there no chances to make this round rated?
UPD: and don't get upset)
Would you mind sharing old version of the checker? It will be interesting to "hack" checker and it can help future authors avoid making similar mistake.
i think it's good enough if some problem setter check each other task, after all problem setters usually is consisted of some high rate people, right ?
if there is still error, then, can't help it
It seems, that it was impossible to make a bug in such a simple checker, but it was done.. If I were an admin, I would decrease your rating by 1000, because you should practice in DIV2A/DIV2B problems solving. P.S. Thanks for interesting problems! :)
Your words are naive and irresponsible. You have no rights to blame others' faults in this weird way unless you have tried making checkers or something else before.
Thank you for your feedback. It's necessary that my rating should be decreased by 1000 or more. To tell you the truth, my rating have been decreased by nearly 300 these days and now for every problem I always get AC after some WAs. So now you may be aware of my awful and sad situation then.
=w=...liouzhou is so cool!.and we will support U as always
Why not to make contest unrated for only those got pretest passed and they should get Wrong Answer?
and for those got unsuccessful hacking ,simply give them their points
Yes, It is a good idea...Someone make successful hacking attempts or have accepted their codes, this problem does not affect them!
As rating is a relative scoring, partially-rated contest is not fair.
I remember a past contest in code forces happened the same problem , the checker has bug. the contest was partially-rated for only not affected contestants
I don't remember exactly what was the contest
There is no absolute fair thing in the world.
str[4294967293] didn't get a runtime error :(
Because according to the C++ standard it's an Undefined Behaviour
It seems to be the second or third consecutive Chinese round that is unrated >"<. It's really a pity that these rounds become unrated in the end, since as far as I can remember, there are enjoyable great problems in these rounds. Some of the participants are frustrated for yet another unrated contest after 2 hours of hard work, but I believe the problem-setters are even more regretful. I wish all the best that the next round you hold will be successful and flawless.
Do you think it's a funny joke to say "In our opinion, problems are easier than the past several rounds prepared by Chinese :)" if problems are very hard in fact? I think many people are very frustrated because of unbalanced problemset, not because of mistake in checker.
3 easy + 2 superb hard .. huh? ... in div2
Ah ok, got it, it's a Chinese to English translation. LOL
So, div1 B reduces to the following:
Having n descending sorted numbers a[i], find p (<= 100) numbers i[0] = 0 <= i[1] <= .. <= i[p] s.t. the following is maximized:
sum_{j = 1:p-1} a[i[j]] * (i[j] — i[j-1])
How to do this ? A dp solution in n^2*p works, but we need smthg better.
You can improve it with this: http://wcipeg.com/wiki/Convex_hull_trick
You can note that the recurrence takes the form, dp[p][m] = min_{m' < m} (m — m') * a[m] — (psum_a[m] — psum_a[m']) + dp[p — 1][m'] = m * a[m] — psum_a[m] — m' * a[m] + psum_a[m'] + dp[p — 1][m'].
The -m' * a[m] + psum_a[m'] + dp[p — 1][m'] part takes the form of a line with slope -m' and y intercept psum_a[m'] + dp[p — 1][m'], so you can optimize this with convex hull trick. Since x coordinates in the queries and slopes in the added lines are monotonic we don't need the full convex hull trick, leading to a short O(m p) solution.
My solution (http://codeforces.net/contest/311/submission/3778498) is O(m p) but failed because it uses integer division, which leads to a high constant factor, T_T. There is a nice solution by RAD at http://codeforces.net/contest/311/submission/3776732.
I'm curious about what chinese coders consider easy, a problem very similar to B was the hardest one in the latinoamerican regional last year.
MarioYC Could you tell me please which is the problem in the 2012 latin american regional similar to Div1-B?
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=572&page=show_problem&problem=4142
Thanks
Is this good that first rank contestant nickname similar to testers nick name?
He even has same name and avatar!
I think there's a same story like with these two guys: YuukaKazami and wjmsbmr. Can someone explain this joke with the same nicknames and another's avatars?
They are tow guys I promised. It's chinese style and just for fun. :)
can someone explain me this test case?
it says 10 lines but I see only 6
Full input is not provided.
Is there any way to get the full input in this case?
UPD. sorry, my mistake
There are blank lines in that test. In my opinion, this was stupid.
stupid !! in real life you code should solve the problem regardless of the cases .
well the problem clearly states that a sentence can have spaces so your solution should solve the case of having one space as a sentence. Mine unfortunately didn't because I wasn't paying enough attention when reading the problem! Better luck next time! :)
Sentences containing spaces are fine. I'm talking about sentences which consist of a single newline character.
Yes, full input not provided. So u might be getting WA on this TC, because u haven’t used cin.ignore() after inputting the integer "number of lines". Another way could be taking input of each line character by character, avoids this problem.
With 110 minutes' hard working and I saw it's unrated.
just don't accept the hack of codes which doesn't pass pretest and then rejudge the whole contest!!! it's not hard, is it?
Naive
The fact that in all tests except first for div1B M is greater than 100 is very nice. Please, do that in every your problem, providing any info is unnecessary.
Run an output of the programm on the code, given in statement. Where can be a mistake in checker?
Probably run 2000*2000/2 iterations for checker is not so fast — so they probably have optimized it somehow.
You are strongly mistaken, 2*10^6 iterations will be executed very fast in the modern computers. Now there is year 2013, not 1980 :) Anyway checker has enough big TL (about 10 seconds).
Just mistype in distance function as I know.
Some test cases are long and incomplete when showing on screen. Is there a way to allow for downloading of the complete test cases after the contest is over?
Thanks.
This issue has been discussed a lot of times
it's impossible
I have second absolute place in Div 2 first time in my life and round is unrated.
I'm the happiest man in the world :D
That's life
I just thought you are Rank 1 in Div.2. Seems like ymxlkAc is someone who tried to make a "super new user" like zfmdhy786: there are users named xlk and kAc in Codeforces.
Is there any reason for the trend toward extremely high constraints recently (eg, Div1-B today with M*P <= 10,000,000)? It's quite annoying to see an idiomatic solution fail simply because it wasn't 'optimised' enough.
In the case of B, it seems very difficult to use things like std::deque to keep track of the convex hull without timing out; to succeed I had to hand-code a replacement, ie. 3778121 → 3780175.
-Вопрос решен.
В псевдокоде, условие на больше или равно. Т.е. нужно строго меньше, а в Вашем варианте — выпадает равенство, так как разница всегда n + 10
I see great and friendly community here. Best of luck for all
And how about ymxlkAc? It's not usual to see such "new user" in a normal(not Div.2 only) round.
Well, now I can see that rounds wrote by Chinese people are unusual. There are many writers, so the problems turns out to be new and interesting, that's a nice thing. :)
Problem A is something new, but I think it looks like a riddle instead of a algorithm contest problem. It contains lots of details and looks very artificial. The core is this line: "if (p[j].x-p[i].x>=d) then break", I first misunderstand it into "dist(p[j], p[i]) >= d" and it becomes very hard to solve.
Problem B is too hard in my opinion. And I don't know if some of the writer/tester has read this problem: http://poj.openjudge.cn/campus2013/A/. It was a problem used in this month, nearly the same with this problem but with lower constraints. I know the key of this problem is DP optimizing, but it's not so good to use it if you know that problem was used in PKU's contest. And the DP optimizing part looks too hard for a 1000p, it required some detailed calculation.
And as for problem D, I find this sentence: "He tells you that because the answer may be too huge, you should only output it modulo 95542721.", it is somewhat misleading, "the answer may be too huge". is not the only reason we have to "modulo 95542721", one another reason is: (3**48)%(95542721-1)=1. Anyway it's an interesting idea to do some hack in the module number.
I haven't read problem C. And for problem E, it's good, but I think the statement can be better: "He will think SmallR succeeds if and only if on some day", it looks like we can satisfy this folk and then do some operation and satisfy another. Yes, then you know why it says "a kind of medicine which can be valid for only one day.", am I taking an English reading exam?
Overall, I would say it's an interesting contest, but it could be better (and rated) if they were well tested.
I saw a code(Your text to link here...) to make negative indexing ....
But this negative indexing didn't cause Runtime Error not even in my compiler ...
I wonder why ???
Because according to the C++ standard it's UB (Undefined Behaviour).
can't unrated contests be added to the contests list of a contestant? thanks
I think we cannot complain them too much,after all this is their first CF round.The reason you all angry maybe is that you binding them together with last several Chinese rounds.But It is unfair to them.
On codeforces contest will be held only Sundays? I saw last contests and Early in week was many contests. what happen now?
Everything is OK :)
Why my problem A is skipped??? After the contest, I submit again and it Accept! So why my solve in problem A is skipped? someone can help me?