Всем привет,
CodeForces 180 начнется 19.04.2013 19:30 (MSK). Я (SteamTurbine), и Ivan Li (AEtheReal) являемся авторами сегодняшнего раунда.
В этот раз вы будете помогать полярным медведям решать их проблемы. Вы знаете, жизнь в Арктике не проста, поэтому они могут столкнуться с совершенно разными проблемами, например: ловля рыбы, сохранение тепла и тому подобное.
Спасибо Gerald за помощь в подготовке раунда и MikeMirzayanov за его великолепную систему, а также Delinur за перевод.
Мы надеемся, что полярные медведи вдруг не решат съесть вас. Удачи.
UPD: Разбалловка будет динамической. Задачи расположены в соответствии с предполагаемой сложностью.
Good to see new authors here. what is the score distribution? standard maybe?
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. :)
wish all luck :-)
Я даже догадываюсь, кто мог это нарисовать ._.
Hаркоман? :D
Paint master :)
if the problem contains picture, would it drawn with paint too ?
new authors and new heroes.
thank you for the contest and wish everyone lucky.
Thanks for the nice bears, I really enjoyed the picture.
Very cute polar bears~ :D
Looking Forward to the Round tonight.
Рисунок шедевр =)
Nice picture!!
Thanks for the great contest theme :-) I expect great problems "stories" and statements. Polar Bears , here we come !
От лица
снежныхбелых медведей благодарю всех за помощь.On behalf of
snowpolar bears let me thank you all for your help.Just noticed that the polar bears are mirror images of each other!
they are twins, I suppose :p
Everybody good luck!=w=
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.
It seems that you have Deep Meaning Search Syndrome.
for some countries the contest in not at night :))
It will be good if there will be short statements :)))))
Looking forward to meeting a polar bear...
http://cdn.memegenerator.net/instances/400x/37126323.jpg
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
Yes.
Have you noticed the stars between the horns of the Moon? :)
Hope Short stories and statement of problems.
Thanks to the authors and CF, This is my first round.
I love this contest.
I admire good art !
In problem "C div(2)" what does parity(a) mean???
It is explaied in statement. Read carefully.
parity(a) = c % 2, c is count of '1' in a
Thanks and sorry my mistake!!
One ticket to Div — 2, please.
me too :( , those ratios ( ceil(n/3) and 3/4 ) killed me
Haha, now your rating is exactly 1700 :D
I think it's early :))) you are still in 1 st division :)))))
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 ?
Как решать С?
Я решал так. l1-количество единиц в первой строке, l2 -во второй. Тогда если (l1%2+l1)>=l2 то YES.
Дивизион спутал
упс. Извините. Не посмотрел
The answer is always
YES.On last minute I've submitted the following construction.
Sort
sand use the following pattern foraandb:where
k = (n+2)/3.The diagram means values in arrays
aandbwhere each#can be found froms[i] = a[i] + b[i].UPD Failed system tests :(
The correct solution to use
k = n/3.Previous version fails on
n=1 s[1]=0.Thank you, it's nice solution.
Будем исходить из того, что s отсортирован и в нем 3x элементов. Если это не так, то добавляется чуть гемора, но решение не меняется. Тогда пусть в первой трети a[i] = i, в третьей трети b[i] = 4x — i, а во второй трети мы будем брать не занятые в массиве а в третьей трети числа по возрастанию. Тогда можно заметить, что во второй и третьей третях а все числа различны, как и в первой и третьей третях b
У меня была такая конструкция (после сортировки):
x x x x x x x x x(0 1 2 3 4 5 6 7 8, например)становится
x x x 0 0 0 x x x(0 1 2 0 0 0 4 6 8)и
0 0 0 x x x 2 1 0(0 0 0 3 4 5 2 1 0).Very interesting problems. I've never tried these 'within x% of an optimal solution' tasks.
Any tips on C and D (Div 1)?
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.
when K>2 ?
We use only two colors, even if K > 2. There is no need to use all colors.
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:
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
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.
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).
Thanks!
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
Thank For Good Questions :) and i enjoyed polar beards :D
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. .......:(( :((
Your links will lead us to Our submissions, not yours. So the links should be :
3567559
3575518
start system testing pls!
Good Luck!
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.
indeed, he/she failed div2 D :)
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.
How to approach div2:E/div1:C ?
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.
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.
What the Contest! Div. 2
Thanks for the problems!!!
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.
3565982 Почему это не работает?
Why it doesn't works?
for (long i=a1-1;i--;i>=0)должно было быть
for (long i=a1-1;i>=0;i--)?спасибо, я уже голову сломал. epic fail.
Just have realized what was embarrassing me. The stars on the dark side of the moon on picture
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 :)
I think he means the moon shouldn't allow us to see them.
Nice observation :)
зачем в задаче D(div. 2) дается k во входных данных?
Чтобы массивы сортировать, а не увеличивать количество рыб k типа на каждом считывании.
not in the brain but in the ass! XD
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#.
Maybe because Array.sort? See this: http://codeforces.com/blog/entry/4827
Edit: Oh, I didn't see that it's in C#... Sorry for the mistake :P
It's antiquicksort test. C# has the most stupid implementation of quicksort (
pivot = a[(left+right)/2]).Arrays.Sort uses a quicksort algorithm with a[(l+r) div 2] median. There's an anti-quicksort test at testcase 60.
Update the ratings so I can see myself everytime farther from division 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/3573436
And while I already know the more elegant solution of using a simple formula, I'd like to know what went wrong.
Thanks,
I think we can't view the full test case. At least for now. :)
I was afraid that was the case. I guess I'll have to try to find such a case myself.
Thanks
Try this:
101your program should output
YESbut i think it doesn't :)Thanks, now it's quite clear what was my mistake.
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?
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/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.
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.
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!
I'm not sure about this, but if bi >= 0 and ai == -1, you might get stuck in your first if-else-if case.
Oh, damn it! Added
ai>= 0 && bi >= 0to that clause and it passed. Thanks!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 .
Agreed. The main reason is I underestimated the difficulty of problem C. I will try to do better next time :)
thank you and thanks for your contests.also I really enjoyed of problem C. :D
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"?
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?
I hope the editorial of this contest has no "coming soon..." phrase
And no need to use google for translation...
Am I the only one who thinks why the moon in that picture is YELLOW?
Sorry if I missed this but will there be an editorial/when
Rating?
What's the rating?
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...
Train, train and train!
Though I am an "antifan" of those kinds of constructive problems, I have to admit that solutions of C and D are so beautiful :)
Thank you for the contest! I liked the problems, they are more natural (as in "not too artificial") than a typical Codeforces problem.
Author master of greedy :)
first time to do cf，I felt very nice ，thank the aurthor.Orz tourist.:)
f**k zoe ~
The polar bears are very cute, and the problems are very interesting..
Surprised to see Chinese character^_^
Задачи с А до D были чисто на мышление. P.S. На счет остальных — я их не читал =)
Screencast
Разбор в студию!
Уже есть давно.
http://codeforces.com/blog/entry/7437