### SteamTurbine's blog

By SteamTurbine, 8 years ago,

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

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

• +321

 » 8 years ago, # |   -6 Good to see new authors here. what is the score distribution? standard maybe?
 » 8 years ago, # | ← Rev. 2 →   +4 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. :)
 » 8 years ago, # |   -8 wish all luck :-)
 » 8 years ago, # |   +16 Paint master :)
•  » » 8 years ago, # ^ |   -15 if the problem contains picture, would it drawn with paint too ?
 » 8 years ago, # | ← Rev. 3 →   +10 new authors and new heroes.thank you for the contest and wish everyone lucky.
 » 8 years ago, # |   +5 Thanks for the nice bears, I really enjoyed the picture.
 » 8 years ago, # |   +4 Very cute polar bears~ :DLooking Forward to the Round tonight.
 » 8 years ago, # | ← Rev. 2 →   0 Рисунок шедевр =)
 » 8 years ago, # |   +10 Nice picture!!
 » 8 years ago, # |   -8 Good luck and high ratings for everyone!!!
 » 8 years ago, # |   -10 Thanks for the great contest theme :-) I expect great problems "stories" and statements. Polar Bears , here we come !
 » 8 years ago, # |   +5 Just noticed that the polar bears are mirror images of each other!
•  » » 8 years ago, # ^ |   +10 they are twins, I suppose :p
 » 8 years ago, # |   +13 Everybody good luck!=w=
 » 8 years ago, # | ← Rev. 2 →   -33 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.
•  » » 8 years ago, # ^ |   +45 It seems that you have Deep Meaning Search Syndrome.
•  » » 8 years ago, # ^ |   +2 for some countries the contest in not at night :))
 » 8 years ago, # |   0 But, according to codeforces time, it is at night.
 » 8 years ago, # |   +2 It will be good if there will be short statements :)))))
 » 8 years ago, # |   -6 Looking forward to meeting a polar bear...
•  » » 8 years ago, # ^ |   +17
 » 8 years ago, # |   +9 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.com/blog/entry/4172
•  » » 8 years ago, # ^ |   +28 Yes.
 » 8 years ago, # |   +23 Have you noticed the stars between the horns of the Moon? :)
 » 8 years ago, # |   -12 Hope Short stories and statement of problems.
 » 8 years ago, # |   +2 Thanks to the authors and CF, This is my first round.
 » 8 years ago, # | ← Rev. 2 →   +2 I love this contest.
 » 8 years ago, # |   +8 I admire good art !
 » 8 years ago, # |   -16 In problem "C div(2)" what does parity(a) mean???
•  » » 8 years ago, # ^ | ← Rev. 3 →   +3 It is explaied in statement. Read carefully.parity(a) = c % 2, c is count of '1' in a
•  » » » 8 years ago, # ^ |   -19 Thanks and sorry my mistake!!
 » 8 years ago, # |   +74 One ticket to Div — 2, please.
•  » » 8 years ago, # ^ |   +21 me too :( , those ratios ( ceil(n/3) and 3/4 ) killed me
•  » » 8 years ago, # ^ |   +11 Haha, now your rating is exactly 1700 :D
•  » » 8 years ago, # ^ |   +6 I think it's early :))) you are still in 1 st division :)))))
 » 8 years ago, # | ← Rev. 2 →   0 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 ?
 » 8 years ago, # |   +13 Very interesting problems. I've never tried these 'within x% of an optimal solution' tasks.Any tips on C and D (Div 1)?
•  » » 8 years ago, # ^ |   +40 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.
•  » » » 8 years ago, # ^ |   0 when K>2 ?
•  » » » » 8 years ago, # ^ |   +5 We use only two colors, even if K > 2. There is no need to use all colors.
 » 8 years ago, # | ← Rev. 2 →   0 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 
•  » » 8 years ago, # ^ |   +7 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
•  » » 8 years ago, # ^ |   +7 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.
•  » » 8 years ago, # ^ |   +21 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).
•  » » » 8 years ago, # ^ |   +10 Thanks!
•  » » 8 years ago, # ^ |   +8 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
 » 8 years ago, # |   -16 Thank For Good Questions :) and i enjoyed polar beards :D
 » 8 years ago, # | ← Rev. 2 →   0 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. .......:(( :((
•  » » 8 years ago, # ^ |   +3 Your links will lead us to Our submissions, not yours. So the links should be :35675593575518
 » 8 years ago, # |   -29 start system testing pls!
 » 8 years ago, # |   -19 Good Luck!
 » 8 years ago, # |   +10 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.
•  » » 8 years ago, # ^ |   0 indeed, he/she failed div2 D :)
 » 8 years ago, # |   +3 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.
 » 8 years ago, # |   0 How to approach div2:E/div1:C ?
 » 8 years ago, # |   +9 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.
•  » » 8 years ago, # ^ |   +20 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.
 » 8 years ago, # |   +7 What the Contest! Div. 2
 » 8 years ago, # |   +5 Thanks for the problems!!!
 » 8 years ago, # | ← Rev. 9 →   +45 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.
 » 8 years ago, # |   +35 Just have realized what was embarrassing me. The stars on the dark side of the moon on picture
•  » » 8 years ago, # ^ |   0 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 :)
•  » » » 8 years ago, # ^ |   +8 I think he means the moon shouldn't allow us to see them.
•  » » 8 years ago, # ^ |   +5 Nice observation :)
 » 8 years ago, # |   +9 Those bears were a real pain in the brain....
•  » » 8 years ago, # ^ |   -30 not in the brain but in the ass! XD
 » 8 years ago, # | ← Rev. 4 →   0 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#.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +1 Maybe because Array.sort? See this: http://codeforces.com/blog/entry/4827Edit: Oh, I didn't see that it's in C#... Sorry for the mistake :P
•  » » 8 years ago, # ^ |   +18 It's antiquicksort test. C# has the most stupid implementation of quicksort (pivot = a[(left+right)/2]).
•  » » 8 years ago, # ^ |   +9 Arrays.Sort uses a quicksort algorithm with a[(l+r) div 2] median. There's an anti-quicksort test at testcase 60.
 » 8 years ago, # |   0 Update the ratings so I can see myself everytime farther from division 1.
 » 8 years ago, # |   +1 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/3573436And while I already know the more elegant solution of using a simple formula, I'd like to know what went wrong.Thanks,
•  » » 8 years ago, # ^ |   +1 I think we can't view the full test case. At least for now. :)
•  » » » 8 years ago, # ^ |   0 I was afraid that was the case. I guess I'll have to try to find such a case myself.Thanks
•  » » » » 8 years ago, # ^ |   0 and that's a benefit of it. we try to find that test case :)
•  » » 8 years ago, # ^ |   +18 Try this:101your program should output YES but i think it doesn't :)
•  » » » 8 years ago, # ^ |   0 Thanks, now it's quite clear what was my mistake.
 » 8 years ago, # |   +11 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?
•  » » 8 years ago, # ^ |   0 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.com/blog/entry/7361Here 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.
•  » » 8 years ago, # ^ |   0 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.
 » 8 years ago, # |   0 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.Thank you!
•  » » 8 years ago, # ^ |   0 I'm not sure about this, but if bi >= 0 and ai == -1, you might get stuck in your first if-else-if case.
•  » » » 8 years ago, # ^ |   +1 Oh, damn it! Added ai>= 0 && bi >= 0 to that clause and it passed. Thanks!
 » 8 years ago, # | ← Rev. 2 →   +28 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 .
•  » » 8 years ago, # ^ |   +37 Agreed. The main reason is I underestimated the difficulty of problem C. I will try to do better next time :)
•  » » » 8 years ago, # ^ | ← Rev. 3 →   0 thank you and thanks for your contests.also I really enjoyed of problem C. :D
•  » » » 8 years ago, # ^ |   0 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"?
 » 8 years ago, # |   +1 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?
 » 8 years ago, # |   +2 I hope the editorial of this contest has no "coming soon..." phrase
•  » » 8 years ago, # ^ |   +3 And no need to use google for translation...
 » 8 years ago, # |   +12 Am I the only one who thinks why the moon in that picture is YELLOW?
 » 8 years ago, # |   -10 Sorry if I missed this but will there be an editorial/when
 » 8 years ago, # |   +12 Rating?
•  » » 8 years ago, # ^ |   +6 What's the rating?
 » 8 years ago, # |   0 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...
•  » » 8 years ago, # ^ |   +22 Train, train and train!
 » 8 years ago, # |   +59 Though I am an "antifan" of those kinds of constructive problems, I have to admit that solutions of C and D are so beautiful :)
 » 8 years ago, # |   +27 Thank you for the contest! I liked the problems, they are more natural (as in "not too artificial") than a typical Codeforces problem.
 » 8 years ago, # |   +4 Author master of greedy :)
 » 8 years ago, # |   +5 first time to do cf，I felt very nice ，thank the aurthor.Orz tourist.:)
 » 8 years ago, # |   -67 f**k zoe ~
 » 8 years ago, # |   +2 The polar bears are very cute, and the problems are very interesting..
 » 8 years ago, # |   +4 Surprised to see Chinese character^_^
 » 8 years ago, # |   +20