gridnevvvit's blog

Codeforces Round #227 (Div. 2)
By gridnevvvit, 11 years ago, translation, In English

Hello!

Soon (on January 30 at 19:30 MSK) you are lucky to participate in Codeforces Round #227 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by me. I want to thank Gerald Agapov (Gerald) for help in preparation of this round, Mary Belova (Delinur) for translation of statements, Michael Mirzayanov (MikeMirzayanov) for marvelous Codeforces and Polygon systems.

The main character of the tasks is the cat George.

UPD1: Scoring will be next: 500, 1000, 1500, 2000, 2500.

UPD2: Contest finished, congratulations to winners!

  1. Sorto
  2. graphis
  3. InternationalGrandmaster
  4. Skedar
  5. mateusz

UPD: Editorial

UPD: Statistics

  • Vote: I like it
  • +101
  • Vote: I do not like it

Comments Comments (76)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it +37 Vote: I do not like it

It is Chinese Spring Festival tomorrow- a very large and important event, so Happy Spring Festival to everybody:) Tonight is called Chu Xi in Chinese, means that wait for the coming new year( in lunar calendar), and I hope this contest will make this night better. Good luck to everybody.

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

    边看春晚边比赛Y(^_^)Y

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

    Which means it will be a challenge because of the firecrackers π_π

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

      orzzzzzzzzzzzz literary giant！！！

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

    Happy Chinese New Year, I have received a big red pocket. :)

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

Sorry, a slip of pen. That is Spring Festival, not Spring Festive.

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

    u don't have to make a new comment for a typo or a grammar mistake. u can click the Edit option on ur old comment and change whatever u want! :)

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

As Chinese people，in this coming New Year's Eve。。。Good luck to everybody

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

    Thank you. I am Vietnamese and I would also like to take this opportunity to wish everyone success for new year.

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

Happy lunar new year!!! I'll see firework at home and practice this round :))

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

Today I wish I go to DIV 1 :)

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

    I see you made it... Congratulations :)

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

      Thank you. Now I wish to stay in Div 1, for that I need to practice more!

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

yeeeeeeeeeeees another <3 gridneeeeeev <3 contest

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

Finally, the main character is a cat! I hope he is fat and orange like Garfield.

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

We hope problems will be normal ;) ...

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

Registered participants are too many for this contest.(about 3500 till now)

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

good luck everyone

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

Guys, Happy Chinese New Year!!!码年快乐哈。。。。。。

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

some bugs with hacks . When i press F5 i can hack guys from another room.

when i try to hack it gives Apache Error

i think it should be unrated if it's not only my error

sometimes when i press @hack@ nothing happens

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

I'm having trouble opening solutions in my room even though I locked both the relevant problems. And sometimes I get redirected to another room (that I'm not in). Has anyone else experienced this?

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

    yes,contest must be unrated!

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

    Thank you for the report. We are investigating the issue. We will do our best to fix it before the next round.

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

    Yes... I faced same problem too... :/

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

    What was "another" room? Was it the 1-st room? Or random? Or not the 1-st but fixed for you?

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

      Room number is shown correct, but users are not. I have seen that room where this user (sayeer_24) was

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

Very glitchy today! "Room" button does not work very well (puts into random room often) and viewing solutions does not always work even after locking problems.

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

I don't want to offend anybody (talking about authors of contests), but this round is really interesting. Thanks a lot, gridnevvvit

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

It's a shame that server problems spoiled an interesting contest. Server was down for much of the contest, room button often redirected into some other room, and hack button rarely worked even if the solutions would finally show up. Very frustrating contest to participate in, but nice problems nonetheless.

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

Round duration increased for 10 minutes. can you announce us before 15 minutes say , before the end of the contest , I've really stop coding at last 2 minutes . Very good contest thanks :)

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

Most fun contest i ever participated on CF. Best regards to everybody who helped in creating this round. I think I got the idea at E (after spending 15 minutes to properly understand the statement) — You use anything you want to create a vector prot[i] which tells you whether or not i is protected then you use divide-et-impera solve(a,b) = get the answer for interval [a,b]. You will need quick queries for sum (0/1 if a number has already been eliminated) and minimum value. All these can be acomplished by a segment tree. Didn't have enough time to implement this though. Is this the right solution? Anyway thanks for the round, Gerald, gridnevvvit, Delinur and of course MikeMirzayanov. Keep up the good work!

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

Is it me or the "room" is buggy today?

On another note: Thanks for the awesome problem set! :)

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

what a fun bug!! :D

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

    So the winner is vas.and.tor, who made 2 hacks:D

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

      Even I had the same problem. But still managed to hack 1. :D And I had vas.and.tor in my 'buggy' room. But the users he hacked were not shown in that room. What a bug. And regarding ' extended duration' I did not get any notice until after the contest. :( I closed the browser 10 seconds before the end of the competition.

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

one more great contest, with interesting problems and bugs :)

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

I managed to make CF show me a standings page full of -1 and -2 where everybody failed all his submissions (even the top 10). A refresh fixed this.

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

    same here in Friends standings

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

    This was happening throughout entire systests. It was a pleasant surprise to see myself in 20th position, but it was quickly revealed to be only a dream :(

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

As Chinese people，Good luck to everybody。

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

This was a nice round. I especially enjoyed solving E. Keep up the good work !

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

Can someone please explain the main idea behind problem D? Thank you! I tried to fix my center, delete it from the graph and then see what the solution is (this is the problematic part — I was thinking about maxflow, but n is too large).

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

    The same problem. I think we have to check all vertexes as center and choose the best. But how delete arcs in optimal way?

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

    You should use biparate matching on the graph, where left side is outdegree of vertex, right side is indegree of vertex.

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

    No, n is not too large at all.

    Maxflow algorithm's (good implemented for biparate matching) complexity is O(FLOW * (N + E)) , E is number of edges here. FLOW's limit is N so overall complexity O(N * E).

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

How to solve E?

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

    First, a slow (but useful) solution:

    In one step, we can remove the minimum of an interval. That means the smallest number (overall) will be removed whenever it's inside the interval picked. If it's supposed to stay, it's clear that we can't ever include it in our interval, and we can just consider our algorithm running on the parts of the original array to the left and right of it.

    Otherwise, we have to pick it eventually. If we pick it in the k-th operation, we can get a larger answer just by picking swapping the k-th and k - 1-st operation (think why it works), which means we should pick it in the first operation. And why not with as large w as possible — picking the whole array. Further in the algorithm, we just operate on the same subarray without the deleted element, without doing any splitting (like above).

    The slow (O(N2)) solution would now be simulating this algorithm. We can do better, though: we can see that it's all right to remove numbers in increasing order (the order among 2 distinct parts of the array doesn't matter), and we know how much the optimal solution will cost: the number of elements in the subarray on which we're running the algorithm, which haven't been deleted yet.

    Splitting subarrays into even smaller parts and checking which one the current element belongs to can be implemented with map<>, counting deleted elements with a Fenwick tree. The implementation is just straightforward now. Complexity: .

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

Failed submission:5850238 Time: 2000 ms (MS C++)
Accepted submission:5850920 Time : 872 ms ( GNU C++ )
It shows that ios::sync_with_stdio(false) in GNU C++ does a Miracle!!!!

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

    Yes. Input is very large to read input with cin

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

    Having it in your template is a good idea...

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

rating change reverted after some time... anyone else experiencing it ?

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

    Looks like I'm still blue even though I'm over 1700.

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

      I'm also still green although I'm over 1500. I imagine this is just a small lag between rating change and color change and should be resolved soon though.

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

        The problem is that I oscilate between the 2 colors.

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

Finally reached blue ^_^ !!

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

Better than nothing: http://translate.google.com/translate?hl=ro&sl=ru&tl=en&u=http%3A%2F%2Fcodeforces.com%2Fblog%2Fentry%2F10583

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

Violet "Candidate Master" and blue "amirMD" (1741) ! :D

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

Sorto supposedly solved C in 3 minutes, has different code templates in his solutions and even different tab settings. And yet he is allowed to take first place.

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

    Also after solving D, submited E in 2 minutes which has just a bug : 5843619.

    He have to explain this situation i think...

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

Can't find what's wrong, with this code: 5847679.Can someone help me?

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


And other stuff

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

For the problem B:

10010111

Can somebody tell me how to merge 100,10,1,1,1 into 10010111 ?

I try but fail.

So I think this data's answer is 4 ..

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

    Sorry, problem C..

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

      I have tested some Accepted code,all their answers are 5.

      I got confused now.

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

        After test data '111',I believe the system test data is not strong enough.

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

    You can do it with this operations (I hope my notation is clear):

    100 + 10 -> 10010, 1, 1, 1

    10010 + 1 -> 100101, 1, 1

    100101 + 1 -> 1001011, 1

    1001011 + 1 -> 10010111

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

      Sorry,I misunderstand the Description。。 thanks ：）

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

    {100, 10, 1, 1, 1} → {1, 1, 1, 10010} → {1, 1, 100101} → {1, 1001011} → {10010111}

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

      Oh.sorry,I mistake 'i!=j' to 'i<j',thanks ^-^

      → Reply