lydrainbowcat's blog

Codeforces Round #185
By lydrainbowcat, 12 years ago, In English

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://mirror.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://mirror.codeforces.com/blog/entry/7785

Contest is over. Congratulations to the winners.

Div.1

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

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

Div.2

  1. ymxlkAc
  2. sasha.sochka
  3. bohuss
  • Vote: I like it
  • +53
  • Vote: I do not like it

Comments Comments (127)
| Write comment?
»
12 years ago, # |
  Vote: I like it +60 Vote: I do not like it

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!

→ Reply
»
12 years ago, # |
  Vote: I like it +14 Vote: I do not like it

It seems Chinese authors always posts announcements early.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hope to have a great round

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I hope that this round will be easier! Thank you!

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the real name of Riatre is hidden?

→ Reply
»
12 years ago, # |
  Vote: I like it -18 Vote: I do not like it

it seems to be a great contest because there are many people that direct the contest.

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it -14 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I think this is helpful

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In www.jutge.org you can find several collections, and an special one for dynamic programming.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    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.

    → Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it -39 Vote: I do not like it

rp+=your vote; wish all of you can get a good result :)

→ Reply
»
12 years ago, # |
← Rev. 5   Vote: I like it +80 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Comma separated contest IDs in a link ?? :O Really nice idea :)

→ Reply
»
12 years ago, # |
  Vote: I like it -6 Vote: I do not like it

I thought I had registered for the contest, but apparently I hadn't...

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

Is anybody but me see six problems for Div2?

→ Reply
»
12 years ago, # |
  Vote: I like it +106 Vote: I do not like it

Thanks for this EASY contest!!

→ Reply
»
12 years ago, # |
  Vote: I like it +107 Vote: I do not like it

It seems that the problems are really very easy.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Yeah, so forking easy, I've managed to solve all 5 problems just pressing this button.

    → Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

In the div2 contest, I can see 6 problems. But I can't see the Problem F. Is it a platform bug?

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any change about the problem:"Cats Transport"?

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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 ?.

→ Reply
»
12 years ago, # |
  Vote: I like it +33 Vote: I do not like it

easier than the past several rounds prepared by Chinese :) :| easier ?

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it -15 Vote: I do not like it

1) Сходил пи-пи в начале контеста — слился в див 2
2) Задержал дыхание при написании А — стал красным.
Вот такой вот контест :)

→ Reply
»
12 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Contest by Contest, Chinese writers are making it hard for me to believe their claims. :P

→ Reply
»
12 years ago, # |
  Vote: I like it +137 Vote: I do not like it

Contest is made in China.

→ Reply
»
12 years ago, # |
  Vote: I like it +62 Vote: I do not like it

so pity to see the unrated round. :(

hope that the next china round will be well-prepared.

→ Reply
»
12 years ago, # |
  Vote: I like it +18 Vote: I do not like it

CodeforcesReputation--; :|

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Code forces will stay my favorite website forever

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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!

      → Reply
»
12 years ago, # |
  Vote: I like it +33 Vote: I do not like it

When everyone has worked hard in solving problems for nearly 2 hours , they say that contest will be unrated !! :(

→ Reply
»
12 years ago, # |
  Vote: I like it -9 Vote: I do not like it

contest unrated

this is very bad and intolerable

only that question should be out of rating

the desicion is condemned

→ Reply
»
12 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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!

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    same here !!

    → Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

2 unsuccessful contests within 4 successive rounds, from 182 to 185......This is very very bad..

→ Reply
»
12 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Problem D is very similar to problem E from NEERC Northern Subregional 2009

→ Reply
»
12 years ago, # |
  Vote: I like it +30 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Good luck) Thanks for the tasks

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    Now why unrated contest? The hacks just can be retested..... 2 hours and a hard contest and now unrated....

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

    everybody makes mistakes, next time you'll do better :)

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +15 Vote: I do not like it

    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)

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -74 Vote: I do not like 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! :)

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    =w=...liouzhou is so cool!.and we will support U as always

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, It is a good idea...Someone make successful hacking attempts or have accepted their codes, this problem does not affect them!

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    As rating is a relative scoring, partially-rated contest is not fair.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      There is no absolute fair thing in the world.

      → Reply
»
12 years ago, # |
  Vote: I like it -8 Vote: I do not like it

str[4294967293] didn't get a runtime error :(

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Because according to the C++ standard it's an Undefined Behaviour

    → Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
  Vote: I like it +95 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

Ah ok, got it, it's a Chinese to English translation. LOL

→ Reply
»
12 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    You can improve it with this: http://wcipeg.com/wiki/Convex_hull_trick

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    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://mirror.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://mirror.codeforces.com/contest/311/submission/3776732.

    → Reply
»
12 years ago, # |
  Vote: I like it +45 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Is this good that first rank contestant nickname similar to testers nick name?

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

can someone explain me this test case?

it says 10 lines but I see only 6

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Full input is not provided.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is there any way to get the full input in this case?

      → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it -6 Vote: I do not like it

    UPD. sorry, my mistake

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    There are blank lines in that test. In my opinion, this was stupid.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -12 Vote: I do not like it

      stupid !! in real life you code should solve the problem regardless of the cases .

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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! :)

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sentences containing spaces are fine. I'm talking about sentences which consist of a single newline character.

        → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

With 110 minutes' hard working and I saw it's unrated.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
12 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Run an output of the programm on the code, given in statement. Where can be a mistake in checker?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Probably run 2000*2000/2 iterations for checker is not so fast — so they probably have optimized it somehow.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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).

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just mistype in distance function as I know.

    → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -7 Vote: I do not like it

-Вопрос решен.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    В псевдокоде, условие на больше или равно. Т.е. нужно строго меньше, а в Вашем варианте — выпадает равенство, так как разница всегда n + 10

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I see great and friendly community here. Best of luck for all

      → Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

And how about ymxlkAc? It's not usual to see such "new user" in a normal(not Div.2 only) round.

→ Reply
»
12 years ago, # |
  Vote: I like it +111 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 ???

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Because according to the C++ standard it's UB (Undefined Behaviour).

    → Reply
»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

can't unrated contests be added to the contests list of a contestant? thanks

→ Reply
»
12 years ago, # |
← Rev. 3   Vote: I like it +40 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
  Vote: I like it +27 Vote: I do not like it

On codeforces contest will be held only Sundays? I saw last contests and Early in week was many contests. what happen now?

→ Reply
»
12 years ago, # |
  Vote: I like it -9 Vote: I do not like it 
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.
→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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?

→ Reply