SteamTurbine's blog

Codeforces Round #180
By SteamTurbine, 12 years ago, In English

Hi all!

CodeForces 180 will take place at 19/4 17:30 (CEST). I (SteamTurbine), and Ivan Li (AEtheReal) are the authors of the round.

This time you will need to help some polar bears to solve their problems. You know, life in the arctic is hard, they may face difficulties about catching fish, keeping warm etc.

Thanks Gerald for helping us to prepare the round, MikeMirzayanov for the great platform and Delinur for translation.

We hope that the polar bears are not going to eat you. Good Luck.

UPD: Scoring will be dynamic. Problems are sorted by increasing order of difficulty.

Editorial is here(All except Div 1 E) and here(Div 1 E).

Result (div1):

  1. tourist (Solved all!)
  2. wjmsbmr
  3. tckwok0
  4. msg555
  5. Erop

Result (div2):

  1. Parsa.pordel
  2. a88027180
  3. Raoul

Some fun facts:

In 297E - Mystic Carvings (written by AEtheReal), the figure in the problem looks like the facial expression "XD" and "囧", which is done intentionally.

Moreover, three lines can intersect in the following 5 ways:

While discussing the problem, we refer those as "川", "囧", "XD", "卄" and "△". Chinese characters are interesting :)

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

Comments Comments (102)
| Write comment?
»
12 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Good to see new authors here. what is the score distribution? standard maybe?

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

Creative and original)

P.S(1): Blog 17 hours and it is not the main :( (Already on the main! :) )

P.S(2): Sorry for my poor English. :)

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

wish all luck :-)

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

Paint master :)

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

    if the problem contains picture, would it drawn with paint too ?

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

new authors and new heroes.

thank you for the contest and wish everyone lucky.

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

Thanks for the nice bears, I really enjoyed the picture.

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

Very cute polar bears~ :D

Looking Forward to the Round tonight.

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

Рисунок шедевр =)

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

Nice picture!!

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

Thanks for the great contest theme :-) I expect great problems "stories" and statements. Polar Bears , here we come !

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

Just noticed that the polar bears are mirror images of each other!

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

Everybody good luck!=w=

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

The picture is looking good with round because:

1-The picture is of night and the contest is also at night. 2-The bears meet each other and participants will meet the solution easily.

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

    It seems that you have Deep Meaning Search Syndrome.

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

    for some countries the contest in not at night :))

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

It will be good if there will be short statements :)))))

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

Looking forward to meeting a polar bear...

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

As far as I tried, I couldn't find the dynamic scoring rule in the FAQ. Is this the version to be used in this contest? http://codeforces.net/blog/entry/4172

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

Have you noticed the stars between the horns of the Moon? :)

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

Hope Short stories and statement of problems.

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

Thanks to the authors and CF, This is my first round.

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

I love this contest.

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

I admire good art !

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

In problem "C div(2)" what does parity(a) mean???

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

    It is explaied in statement. Read carefully.

    parity(a) = c % 2, c is count of '1' in a

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

One ticket to Div — 2, please.

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

    me too :( , those ratios ( ceil(n/3) and 3/4 ) killed me

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

    Haha, now your rating is exactly 1700 :D

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

    I think it's early :))) you are still in 1 st division :)))))

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

Strange that there is so much submissions on div 2 for Parity Game: the distribution of the number of submissions for Parity Game and Fish Weight are inverted for div 1. A lot of system test fail ?

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

Very interesting problems. I've never tried these 'within x% of an optimal solution' tasks.

Any tips on C and D (Div 1)?

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

    Problem D:

    If k = 1, answer is obvious.

    If k >= 2 answer is always YES. Let's do following.

    If n > m, rotate the field. Now n <= m. Let the horizontal equality/not-equality signs will be row conditions, vertical — column conditions.

    We will use only two colors. We will satisfy all row conditions, and at least half of column conditions.

    Suppose we had satisfied all row conditions, then we know for each row how it looks — there can be two variants of each row (variant with inversed 1 <-> 2). Let's color by rows. If we colored all rows till i-th, let's choose one of two variants of colorint i + 1 such way that we satisfy at least half of column conditions between that two rows (it's always possible).

    So we satisfy >= n * (m — 1) + 0.5 * m * (n — 1) conditions, that's >= 0.75 * total.

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

Very hard problem A. How to prove it? I submitted wrong solution, wrote a stress, realized that solution is wrong and... blocked the problem and get +700 points for the hacks.

If you do emulation for all positions where suffix of the first string is equal to the prefix of the second string, your answer will be wrong on this test:

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

    If current parity is 1, then add 1 at the end of a. Then start to make b just to the right — we always keep number of 1s at max as if we need to remove 1 it can be only if we need to add 1. After all b is built just remove any redundant prefix

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

    From every sting we can get string (cnt + cnt%2) ones. Just erase 0, and erase and add to and 1 if even ones, just add 1, if odd ones. It can be reversed to get any string from bigger number of ones.

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

    Let a be the original string and b — the final string. If parity(a) == 1, let's immediately append '1' to its end. Then let's append symbols of b to the end of a. If you need to append '0', you can just do it. Else, you need to erase symbols from the beginning till the first '1', and then append '1' to the end. So, you can transform a to b iff one_count(a) + parity(a) >= one_count(b).

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

    Although I realized correct solution for A too late (but I hope my solution is correct anyway), the idea is that if you have even number of 1's you can't make any more and if you have odd number of 1's you can add just one. And using this operations you can easily reorder 0's and 1's if there is a solution

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

Thank For Good Questions :) and i enjoyed polar beards :D

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

I've submitted problem B 3567559> at around 30 mins and then 10 mins before the contest ends was going to submit problem C but unfortunately submitted into problem B. Therefore pretest failed on test 1. So I resubmitted the same code of B 3575518adding one extra space in my code just before the contest. Both the submission of B passed pretest. .......:(( :((

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

start system testing pls!

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

Good Luck!

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

I was hacking someone's div2 D in the last 30s, but I accidently and unsuccessfully hacked his/her problem A instead.

I've never read his/her problem A, but I will be happy that the sys test will prove my hacking is right.

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

Does anyone fall to the trap in Div2 E / Div1 C that the original array is a unique array? (I do.)

The problem becomes really difficult when the original array is not a unique array.

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

How to approach div2:E/div1:C ?

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

I really liked this contest, especially those constant-factor approximation problems. It's something one cannot expect in other contests like TopCoder, Google Code Jam, etc.

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

    But today both problem C and problem D was in fact problems with exact solution, there was no need to approximate anything in usual way.

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

What the Contest! Div. 2

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

Thanks for the problems!!!

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

Hi guys, I just need your attention . A man who his name is Rado Asked me to give code of question C and he will give me code of A. He even sent me that code to convince me to sent him C. I didn't do that and I even didn't read that question. I also saw a blog that was about his cheating. they didn't do anything with him, but now plz plz help me to kick this cheaters out of CF. UP1: I send messages to Gerald and Mike but they haven't read it until yet.
UP2: MR.Mirzayanov send this message."Done, thanks." I have to thank him as well.

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

Just have realized what was embarrassing me. The stars on the dark side of the moon on picture

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

    What's with those stars? Do they form some specific shape? I am staring at this picture for like 15 minutes and i still don't see anything interesting :)

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

      I think he means the moon shouldn't allow us to see them.

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

    Nice observation :)

    → Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it 
Those bears were a real pain in the brain....
→ Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Hi, I can't find out why my fishes problem exceeded time limit. http://www.codeforces.com/contest/298/submission/3573315 Can someone with a keen eye spot what's wrong? Thx in advance.

Is there a way to get full test case data?

Confirmed. Same code in C++ worked under 360ms in the worst case. It's not first time when Mono compiler let's me down.

I have used shuffle before sort, as Dalex proposed elsewhere, and it ran under 140ms in C#.

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

    Maybe because Array.sort? See this: http://codeforces.net/blog/entry/4827

    Edit: Oh, I didn't see that it's in C#... Sorry for the mistake :P

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

    It's antiquicksort test. C# has the most stupid implementation of quicksort (pivot = a[(left+right)/2]).

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

    Arrays.Sort uses a quicksort algorithm with a[(l+r) div 2] median. There's an anti-quicksort test at testcase 60.

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

Update the ratings so I can see myself everytime farther from division 1.

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

Is there a way to find the full case when the window shows "..." at the end? I failed case 49 of problem C div2.

http://www.codeforces.com/contest/298/submission/3573436

And while I already know the more elegant solution of using a simple formula, I'd like to know what went wrong.

Thanks,

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

    I think we can't view the full test case. At least for now. :)

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

      I was afraid that was the case. I guess I'll have to try to find such a case myself.

      Thanks

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

    Try this:

    1

    01

    your program should output YES but i think it doesn't :)

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

Off topic: I'm experiencing a weird bug in google-chrome on 64 bit linux. On the right side I have a ruler with 2 arrows(one up and down) but when I press the up arrow it acts just like the down arrow. Anybody else experiencing this?

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

    I still don't know how those new comments arrow work, but I think they do act differently. Go to another topic, for example: http://codeforces.net/blog/entry/7361

    Here they seemed to me, as you say, to do the same. There I can see the (actually "a", can't tell for sure how it works) difference.

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

    I get the same behavior (chrome on ubuntu 12.04). However, it says "New comments" when you point your mouse at it, so probably that thing is supposed to scroll to the top/bottow of new comments at the current page.

    And if you're in the middle of the page, it will scroll you down, as all new comments are in the bottom.

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

Hey, can someone help me discover why my B (Div. 1) failed because of TLE. I have a regular solution — sort and use "two pointers" method. It usually works in under 100 ms, but takes over a second on test 33 (most likely infinite loop). So I probably have some bug in my code, but I cannot discover it.

Code: http://pastebin.com/ArKkCQe9

Thank you!

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

    I'm not sure about this, but if bi >= 0 and ai == -1, you might get stuck in your first if-else-if case.

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

      Oh, damn it! Added ai>= 0 && bi >= 0 to that clause and it passed. Thanks!

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

the contest for div1 depended on time too much(my mean is more for persons that accepted A and B)for example there were somebody that accepted A and B and with succesfull hack and their rank became so good while there were somebody else that accepted A and B with better time and spent the remainder of their time to the other questions and at last their score became less than the persons that got succesfull hack.and so it might be so diference between two persons that almost have the same skill(specially for persons that accepted A and B).so it will be better that the contest donot depend of time so much(of course it is my idea and my mean was for many contests not only your contest and also my words was a offer) at last thanks for the contest and sorry for my poor english .

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

    Agreed. The main reason is I underestimated the difficulty of problem C. I will try to do better next time :)

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

      thank you and thanks for your contests.also I really enjoyed of problem C. :D

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

      For me, it was more like not reading the words "unique" and "distinct"; I got the solution's sketch after noting that. A lesson to read the problem statement more carefully next time.

      It might also be useful to emphasize the word "distinct"?

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

I have some apokalyptically weird problem with my solution of D (Div. 2). I kept getting WA 1 sending the solution last minutes. It 3574362 says the code gives NO for the first pretest, but on my computer this exact code does give YES. I can't get it. Does anyone else have this problem?

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

I hope the editorial of this contest has no "coming soon..." phrase

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

Am I the only one who thinks why the moon in that picture is YELLOW?

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

Sorry if I missed this but will there be an editorial/when

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

Rating?

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

And tourist wins again, If anyone has the formula to be at least 10% like him please send it to me, I really need it not to quit programming right now...

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

Though I am an "antifan" of those kinds of constructive problems, I have to admit that solutions of C and D are so beautiful :)

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

Thank you for the contest! I liked the problems, they are more natural (as in "not too artificial") than a typical Codeforces problem.

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

Author master of greedy :)

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

first time to do cf，I felt very nice ，thank the aurthor.Orz tourist.:)

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

f**k zoe ~

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

The polar bears are very cute, and the problems are very interesting..

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

Surprised to see Chinese character^_^

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

Screencast

→ Reply