### lydrainbowcat's blog

By lydrainbowcat, 6 years ago, ,

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), xiaodao(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.com/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.com/blog/entry/7785

Contest is over. Congratulations to the winners.

Div.1

1. roosaphu (I promise it's someone who pretends to be roosephu, and I've known who he is.)
2. cp12321
4. ACMonster
5. kAc

And ryz , cgy4ever, who passed problem E in the contest.

Div.2

•
• +53
•

 » 6 years ago, # |   +60 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!
•  » » 6 years ago, # ^ |   +34 Are FredaShi and lydrainbowcat a pair of lovers? :D
•  » » » 6 years ago, # ^ |   +37 Of course!:D
•  » » » 6 years ago, # ^ |   -31 Of course not!
 » 6 years ago, # |   +14 It seems Chinese authors always posts announcements early.
 » 6 years ago, # |   0 hope to have a great round
 » 6 years ago, # |   +5 I hope that this round will be easier! Thank you!
 » 6 years ago, # |   0 Why the real name of Riatre is hidden?
•  » » 6 years ago, # ^ |   +28 He told me that he didn't want to show his real name.
 » 6 years ago, # |   -18 it seems to be a great contest because there are many people that direct the contest.
 » 6 years ago, # | ← Rev. 3 →   -14 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.
•  » » 6 years ago, # ^ |   +9 I think this is helpful
•  » » 6 years ago, # ^ |   0 In www.jutge.org you can find several collections, and an special one for dynamic programming.
•  » » 6 years ago, # ^ |   -6 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.
 » 6 years ago, # |   -58 Hello everyone,I thank Zanoes, liouzhou_101, lydrainbowcat, roosephu, FredaShi, sjynoi, sevenkplus, xiaodao, Riatre, Gerald & MikeMirzayanov for organizing this contest.At this time, 8 hrs is left to the contest.I hope that this round will be easier & to have a great contest
 » 6 years ago, # | ← Rev. 4 →   -39 rp+=your vote; wish all of you can get a good result :)
•  » » 6 years ago, # ^ |   0 What did it mean?
•  » » » 6 years ago, # ^ |   -11 If you have a high 'rp', you will be very lucky.
 » 6 years ago, # | ← Rev. 5 →   +80 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.
•  » » 6 years ago, # ^ |   +3 Right!And enjoy yourself><
•  » » 6 years ago, # ^ |   +1 I think the problems in this round are not too hard. One of the testers solved all the five problems of Div.1 successfully.
•  » » » 6 years ago, # ^ |   +31 In 2 hours?
•  » » » 6 years ago, # ^ |   +55 so if this is easy how would the hard one be?
•  » » 6 years ago, # ^ |   -10 +1
 » 6 years ago, # |   +41 Comma separated contest IDs in a link ?? :O Really nice idea :)
 » 6 years ago, # |   -6 I thought I had registered for the contest, but apparently I hadn't...
 » 6 years ago, # | ← Rev. 2 →   +4 Is anybody but me see six problems for Div2?
•  » » 6 years ago, # ^ |   +4 Me too
•  » » 6 years ago, # ^ |   +1 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 :)
 » 6 years ago, # |   +106 Thanks for this EASY contest!!
 » 6 years ago, # |   +107 It seems that the problems are really very easy.
•  » » 6 years ago, # ^ |   +23 Yeah, so forking easy, I've managed to solve all 5 problems just pressing this button.
 » 6 years ago, # |   +9 In the div2 contest, I can see 6 problems. But I can't see the Problem F. Is it a platform bug?
•  » » 6 years ago, # ^ |   0 Yes
 » 6 years ago, # |   0 Is there any change about the problem:"Cats Transport"?
 » 6 years ago, # | ← Rev. 2 →   0 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 ?.
 » 6 years ago, # |   +33 easier than the past several rounds prepared by Chinese :) :| easier ?
 » 6 years ago, # | ← Rev. 3 →   -15 1) Сходил пи-пи в начале контеста — слился в див 22) Задержал дыхание при написании А — стал красным.Вот такой вот контест :)
 » 6 years ago, # |   +29 Contest by Contest, Chinese writers are making it hard for me to believe their claims. :P
 » 6 years ago, # |   +137 Contest is made in China.
 » 6 years ago, # |   +62 so pity to see the unrated round. :(hope that the next china round will be well-prepared.
 » 6 years ago, # |   +18 CodeforcesReputation--; :|
•  » » 6 years ago, # ^ |   0 Code forces will stay my favorite website forever
•  » » » 6 years ago, # ^ |   +2 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!
 » 6 years ago, # |   +33 When everyone has worked hard in solving problems for nearly 2 hours , they say that contest will be unrated !! :(
•  » » 6 years ago, # ^ | ← Rev. 2 →   +58
 » 6 years ago, # |   -9 contest unrated this is very bad and intolerable only that question should be out of rating the desicion is condemned
 » 6 years ago, # |   +12 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.
•  » » 6 years ago, # ^ |   +9 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!
•  » » 6 years ago, # ^ |   -6 same here !!
 » 6 years ago, # |   +4 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.
•  » » 6 years ago, # ^ |   0 Good idea!
 » 6 years ago, # | ← Rev. 3 →   +10 2 unsuccessful contests within 4 successive rounds, from 182 to 185......This is very very bad..
 » 6 years ago, # |   +13 Problem D is very similar to problem E from NEERC Northern Subregional 2009
•  » » 6 years ago, # ^ |   -13 That's a coincidence. I haven't seen it before.
•  » » » 6 years ago, # ^ |   +5 the problem has been discussed in winter-camp 2010 (by zej).
•  » » 6 years ago, # ^ |   +5 Hmmm, Gerald should be familiar with this problem, it's well known in Russia...P.S. Nice solution :)
•  » » » 6 years ago, # ^ |   +20 Hm, it's strange, but I didn't remember that problem. =(
•  » » » » 6 years ago, # ^ |   0 It is in latest 25 blogs now :)http://codeforces.ru/blog/entry/4863
 » 6 years ago, # |   +30 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.
•  » » 6 years ago, # ^ |   +10 Good luck) Thanks for the tasks
•  » » 6 years ago, # ^ |   -18 Now why unrated contest? The hacks just can be retested..... 2 hours and a hard contest and now unrated....
•  » » 6 years ago, # ^ |   +41 everybody makes mistakes, next time you'll do better :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   +15 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)
•  » » 6 years ago, # ^ |   +14 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.
•  » » » 6 years ago, # ^ |   0 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
•  » » 6 years ago, # ^ |   -74 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! :)
•  » » » 6 years ago, # ^ |   +1 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.
•  » » » 6 years ago, # ^ |   +3 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.
•  » » 6 years ago, # ^ |   +3 =w=...liouzhou is so cool!.and we will support U as always
 » 6 years ago, # |   0 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
•  » » 6 years ago, # ^ |   0 Yes, It is a good idea...Someone make successful hacking attempts or have accepted their codes, this problem does not affect them!
•  » » 6 years ago, # ^ |   +23 As rating is a relative scoring, partially-rated contest is not fair.
•  » » » 6 years ago, # ^ |   +11 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 contestantsI don't remember exactly what was the contest
•  » » » 6 years ago, # ^ |   +25 There is no absolute fair thing in the world.
 » 6 years ago, # |   -8 str[4294967293] didn't get a runtime error :(
•  » » 6 years ago, # ^ |   +3 Because according to the C++ standard it's an Undefined Behaviour
 » 6 years ago, # |   +4 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.
 » 6 years ago, # |   +95 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.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 3 easy + 2 superb hard .. huh? ... in div2
 » 6 years ago, # | ← Rev. 2 →   -18 Ah ok, got it, it's a Chinese to English translation. LOL
 » 6 years ago, # |   +16 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.
•  » » 6 years ago, # ^ |   +7 You can improve it with this: http://wcipeg.com/wiki/Convex_hull_trick
•  » » 6 years ago, # ^ | ← Rev. 3 →   +8 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.com/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.com/contest/311/submission/3776732.
 » 6 years ago, # |   +45 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.
•  » » 6 years ago, # ^ |   0 MarioYC Could you tell me please which is the problem in the 2012 latin american regional similar to Div1-B?
•  » » » 6 years ago, # ^ |   0
•  » » » » 6 years ago, # ^ |   0 Thanks
 » 6 years ago, # |   +26 Is this good that first rank contestant nickname similar to testers nick name?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 He even has same name and avatar!
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +3 I think there's a same story like with these two guys: WJMZBMR and wjmsbmr. Can someone explain this joke with the same nicknames and another's avatars?
•  » » » » 6 years ago, # ^ |   +7 They are tow guys I promised. It's chinese style and just for fun. :)
 » 6 years ago, # |   +1 can someone explain me this test case?it says 10 lines but I see only 6
•  » » 6 years ago, # ^ |   +1 Full input is not provided.
•  » » » 6 years ago, # ^ |   0 Is there any way to get the full input in this case?
•  » » 6 years ago, # ^ | ← Rev. 2 →   -6 UPD. sorry, my mistake
•  » » 6 years ago, # ^ |   +6 There are blank lines in that test. In my opinion, this was stupid.
•  » » » 6 years ago, # ^ |   -12 stupid !! in real life you code should solve the problem regardless of the cases .
•  » » » 6 years ago, # ^ |   0 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! :)
•  » » » » 6 years ago, # ^ |   0 Sentences containing spaces are fine. I'm talking about sentences which consist of a single newline character.
•  » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   +1 With 110 minutes' hard working and I saw it's unrated.
 » 6 years ago, # |   0 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?
•  » » 6 years ago, # ^ |   0 Naive
 » 6 years ago, # |   +16 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.
 » 6 years ago, # |   +15 Run an output of the programm on the code, given in statement. Where can be a mistake in checker?
•  » » 6 years ago, # ^ |   +2 Probably run 2000*2000/2 iterations for checker is not so fast — so they probably have optimized it somehow.
•  » » » 6 years ago, # ^ |   +6 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).
•  » » 6 years ago, # ^ |   0 Just mistype in distance function as I know.
 » 6 years ago, # |   +1 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.
•  » » 6 years ago, # ^ |   0 This issue has been discussed a lot of timesit's impossible
 » 6 years ago, # | ← Rev. 2 →   +6 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
•  » » 6 years ago, # ^ |   0 That's life
•  » » 6 years ago, # ^ |   +22 I just thought you are Rank 1 in Div.2. Seems like ymxlkAc is someone who tried to make a "super new user" like roosaphu: there are users named xlk and kAc in Codeforces.
•  » » » 6 years ago, # ^ |   0 I didn't noticed that there are users named xlk and kAc in Codeforces. I'm new here. Also, I'm sad about the unrated round.
 » 6 years ago, # |   -10 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.
 » 6 years ago, # | ← Rev. 2 →   -7 -Вопрос решен.
•  » » 6 years ago, # ^ |   -6 В псевдокоде, условие на больше или равно. Т.е. нужно строго меньше, а в Вашем варианте — выпадает равенство, так как разница всегда n + 10
•  » » » 6 years ago, # ^ |   0 I see great and friendly community here. Best of luck for all
 » 6 years ago, # |   +9 And how about ymxlkAc? It's not usual to see such "new user" in a normal(not Div.2 only) round.
 » 6 years ago, # |   +111 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.
 » 6 years ago, # |   +1 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 ???
•  » » 6 years ago, # ^ |   +1 Because according to the C++ standard it's UB (Undefined Behaviour).
 » 6 years ago, # |   +7 can't unrated contests be added to the contests list of a contestant? thanks
 » 6 years ago, # | ← Rev. 3 →   +40 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.
 » 6 years ago, # |   +27 On codeforces contest will be held only Sundays? I saw last contests and Early in week was many contests. what happen now?
•  » » 6 years ago, # ^ |   +7 Everything is OK :)
 » 6 years ago, # |   -9 I do not have time to participate in a number of competitions, this one I think I can get a better grade, yes I do , with good grade. But no rating changed. I may not to blame the one who hold the round, but I do not want this happen again.
 » 6 years ago, # |   +8 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?