Всем привет!
Совсем скоро, 4 октября в 19:30 MSK состоится Codeforces Round #204, автором которого являюсь я. Это мой восьмой раунд на Codeforces и я надеюсь, что не последний.
Спасибо Геральду Агапову (Gerald), Евгену Василиву(yvasyliv), Максиму Бевзе(Cenadar) и Максиму Ахмедову(Zlobober) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.
Настоятельно рекомендую прочитать условия ВСЕХ задач.
Разбалловка в первом дивизионе: 1000-1000-1500-2000-2000.
Разбалловка во втором дивизионе: стандарт.
Gl & hf ! :)
ну наконец-то мы тебя дождались!:D
Maybe a bit weird my question, but anyway, which are the numbers of the other rounds you have prepared? I just want to see the style of your problems.
Thanks.
You can easily figure that out by checking his blog entries.
You are absolutely right. Thanks a lot :D
I think it is "Friday, October 4th".
Fixed. Thanks :)
Two matches in one week. I like it.
I like Sereja's contests!!
Sereja's contests like you too!!
i think you mean, Friday, October 4th at 19:30 MSK.
Yes, thanks)
One of my friends (SeyedParsa) likes Sereja's contests because he improves his rate rapidly in Sereja's contests and I wish I can improve my rate in this contest too:))) Good luck everyone;)
And now I should say I like Sereja's contests too!!
Because I improve my rate after a long time in this contest!!
Thank you Sereja:)
И опять вечером в пятницу! :(
Неужели никак нельзя дела с вечера пятницы перенести на вечер субботы, например?
Пары перенести, да. Думаю, преподаватель поймёт и согласится, это же КФ.
Ну я, например, никак перенести не могу. Точнее так, освободиться в пятницу до 19:30 возможности нет. Понятно, что любой день и любое время будет кому-нибудь неудобно. Но если один и тот же день всегда выбирается для всех раундов, то одни и те же люди будут вынуждены их пропускать.
Следующие 2 контеста в четверг и субботу, так что все замечательно :)
Это будет здорово. Спасибо.
Static or Dynamic problem weights?
Hope the problems would be fun!
a question what is different of Div1 and Div2?(i am new here!) and how can i register for them?
Div1 is for high ratings and Div2 for others ! Problems in Div2 are easier than Div 1 !
http://mirror.codeforces.com/help I think you'll find your answer in point #15(What are the rating and the divisions?). You can check the rest of the answers for information since you're new here, you'll find it very interesting.
reading all problems strongly recommend :D
Thanks Captain.
Just out of curiosity... But why is this comment being down-voted so much?
Maybe because the same is written in the blog post itself? That makes the post sort of a spam. At least I downvote exact cliches (those that don't have anything unique) unconditionally.
Plus, the grammar's bad.
I rather thought that these down-votes kind of ruin the harmony here at Codeforces... Most of the down-voted comments are posted by newcomers, they may simply want to express that they're here, that they want to be part of the Codeforces community... Maybe what they say contain nothing important but that's not a reason for down-votes... I would think that down-votes are for those who insult people or are impolite... Furthermore, about grammar... As there are people from all over the world, with most of them are from non-English-speaking countries, I think bad grammar is very understandable...
I don't see many comments that are rude, but still not in the "should be deleted by admin" region. There are so few of those that if we really limited the reason for downvotes to be rudeness, the downvote button would just become a tool for trolls and it'd be better off removed. And that'd be weird.
While I realize it's a bit cruel, writing can be good or bad, and I try to vote accordingly. It's also unfair if someone writes a good comment, and gets around as many votes as someone who copies a sentence from the text on top of the page.
You're totally right... I just find it quite uncomfortable to see a lot of comments getting down-voted for no obvious reason... I really hope everyone can think before they vote like you do...
Sereja, есть ли возможность сделать хотя бы раз контест в субботу? Было бы очень замечательно.
Это, как бы, не автор решает.
Извиняюсь. Не знал.
Ну да, сломал самолетик, делать нечего, можно и раунд дать =)
что бы накопить на новый самолетик;)
А за подготовку контеста на кф платят разве?
Естественно, платят. Мне кажется, довольно странно предполагать, что авторы каждого из 200 контестов выполняли довольно объемную работу по подготовке своего раунда бесплатно :)
Div.1 + Div.2 раунд: 10500 + 1500*,
Div.2 раунд: 4500 + 1500*.
сумма со звездочкой — это бонус за качество.
Пруф
Это очень замечательно, спасибо :)
Вам все равно не дадут провести раунд.
Пока идей для написания контестов все равно не было, а то что за это еще и платят — это дополнительный стимул. Я думал, что люди на голом энтузиазме контесты составляют :)
Господа минусующие. Напомните-ка мне раунды, которые давали люди вне рейтинга.
HASP просто спросил, платят ли за контесты.
Злой ты просто.
Ну, раз об этом заявили только 1 января 2013, до этого контесты, скорее всего, не оплачивались. Следовательно, 158 контестов (и это только те, которые "нумерованные"), должно быть, были проведены бесплатно.
Да и не вижу ничего странного в том, чтобы готовить раунд бесплатно. В этом процессе есть довольно много плюсов и помимо потенциальной оплаты.
Оплачивались, но немного меньше.
Блин, действительно. Глупый невнимательный я =(
Формулировка увеличить поощрение как бы намекает, что и до этого времени поощрение было.
По-моему фраза:
значит — что поощрение таки увеличено, а не появилось.Тот же пост о Новом годе
thx...I hope everyone will get high score;
Best author's (in my opinion) contest exactly on my birthday, really awesome present :) GL &HF everybody )
We have a national level university contest in Bangladesh tomorrow. Hope it would be a good warmup.
Good Luck for all~..
Good luck to everyone !!!
What about the score distribution? :)
seens to be a little bit hard? well, hope everyone can figure out all the problems && enjoy every contests:)
shit !!
first time writing div 1 round
Wow... More than 4000 participants :D What is the record, by the way? :)
we will be having acm icpc regional qualifications this month hence the increased number of participants :)
Hope that doesn't affect on stability of the contest :)
Looks like no 500-points problem for Div 1 ... It may be thought round for me, first time participant @ Division 1 ... ;-)
Hope better results 4 everyone!
Как решать В(div.1)?
Понятно, что на перестановку можно забить, важно только число инверсий. Пусть инверсий n, ответ — dn. Тогда
, это сворачивается в формулу, считающуюся за O(1).
То есть, если без формулы, ДП по количеству инверсий?
Да, но ДП прямо таки напрашивается свернуться :) di = 4 + di - 2.
Что-то мне подсказывает, что финальная проверка будет очень быстра))
Интересно, много участников честно доказали формулу для B div 1?
Эм, а чего там доказывать-то? Что на перестановку можно забить и важно только количество инверсий? Это очевидно.
Я про формулу, написанную в этом комментарии
Эм, а тут чего доказывать? Мы можем сделать +-1 инверсию, оппонент — тоже. Итого — переходы либо (+2, 0), либо (0, -2); первый хуже второго в силу монотонности di (докажте по индукции ;)), значит, надо делать второй.
Что там такого в претесте 9 в див1 А ?
How solve problem C?
Initially round down all the numbers. Now, you have to round up 'n' numbers. Choose as many as you can so that difference becomes less. Next choose as many as you can so that this minimum difference remains (by choosing integers). If still you haven't chosen 'n' numbers, choose the rest. 4667241
It can be solved by DP:
You should think how to calculate what's the best state as you just have two of them.
I thought of this, but I thought that somehow the sign of the difference would matter. So I added another state and I calculated the maximum from the negative differences and the minimum from the positive differences. Can anyone explain why the sign doesn't matter? Especially when you can reach a state with both x and -x. Thanks!
It can be solved linearly. Unless a_i=0 (discarding the integer part), it doesn't matter whether you round a number up or down. If you round up, you add 1-a_i to the difference. If you round down, you add -a_i. So you end up with the total difference being n-sum(a_i). Now, when a_i=0, rounding up gives 0, not 1. So you count the number of a_i=0 and count how many of those to round up. Subtract this number from n-sum(a_i) and you get the answer.
Thank you for the answer! But it's still not clear for me: in the test case
0.000 0.500 0.750 1.000 2.000 3.000the N - sumai becomes 1.750, which can't be transformed to the answer of 0.250 by substracting 1s...Sure it can. Note that at the end you have to take absolute value of the answer. As cfk said you need to count how many a_i=0 you round up. In this case 2, so |1.750—2|=0.250.
i solve it using greedy, sadly, after contest :)
we just need calculate the elements that have same value, whether rounding up or down, as this number have same value, it doesnt matter we treat this numbers as round up operation or round down operation, let's call this total of elements 'sama'
assume we have sum of all rounded down numbers, let's call this 'h',
then, iterate from i = 0 to n, and take the minimum difference of original sum and (h+i) that satisfy i+sama >= n
http://mirror.codeforces.com/contest/352/submission/4676368
sry for my bad english, hope you can understand
E — тот ещё троллинг. Очень надеюсь, что очевидная фигня — неправильная по каким-то мистическим соображениям и у всех попадает. Но вероятность этого исхода к сожалению не очень высокая :(
На низкую вероятность этого исхода мне намекают стрессовые 9000 запусков рандома для перестановок без повторений и >3000 запусков для перестановок с повторениями, которые не смогли сломать "очевидную фигню".
У меня есть некоторая очевидная фигня с доказательством правильности. Ты про какую из очевидных фигней?
Ну да, она самая, с доказательством правильности. Возьмём максимальный по модулю элемент, он даёт инверсии либо со всеми слева, либо со всеми справа. Выберем минимум из этих 2х количеств, выкинем элемент, повторим пока не закончится. Я минут 15 не мог поверить, что в задаче E всё так просто :) Троллинг удался.
Дело в том, что у меня еще ДП было для равных. Немного недооценил задачу :(
У меня, видимо, то же самое, но объяснение чуть другое.
Фиксируем все элементы, кроме одного, пускай он равен p по модулю. Для двух его положений количество инверсий будет отличаться на (количество элементов, по модулю меньших p, справа) — (количество элементов, по модулю меньших p, слева). Независимо от расположения остальных наше положение определяется однозначно.
А как же учесть количество элементов равных p со знаком + слева(если текущий взять со знаком -) и количество элементов равных p со знаком — (если текущий взять со знаком +)? Эти пары ведь тоже дают инверсии.
Хм, звучит убедительно. Слабые тесты?.. Надо бы попробовать придумать челлендж на это дело.
Если я понял вопрос правильно:
Там монотонно получится, автоматически первые выйдут отрицательные, остальные положительные.
Действительно, не заметил это факт)
Кажется, что на них можно забить, потому что нам никогда не может быть выгодно сделать в какой-то момент p, а где-то потом - p, поэтому равные нигде не дают инверсий.
Если честно, я не думал об этом во время контеста. Немного повезло. =)
Можно узнать, что за мистическая фигня имеется в виду?)
Сделаем все числа положительными. Далее будем идти слева направо, если изменение знака текущего числа не увеличивает число инверсий, то сделаем это число отрицательным, иначе оставим как есть.
Блин, я думал, что там что-то такое) В итоге написал динамику
Что зашло у меня: В цикле (пока массив меняется), пытаемся изменить знак очередного числа(идем слева на право) на обратный, при условии, что число инверсий уменьшиться. http://mirror.codeforces.com/contest/351/submission/4660777
Почему в компиляторе С++(5.4.2) вот этот код проходит претесты,но в С++(4.7.0)(версия компилятора в кодфорсе нет)?
Потому что вы объявляете массив double a[n], а элементов у вас 2*n. Когда вы обращаетесь за предел массива у вас происходит рандомная фигня, иногда работает, а иногда — нет.
thank Sereja for this contest , so nifty contest :D
I guess many submissions (including mine) for Div1-A will fail because of small array size (2000+etc) :(
Liked the problem set (y)
I'm ready !!
Sereja, Вы явно перестарались с С(div. 2). Всего 100 решений!
Он скорей перестарался с Е див1 ))
Там какая-то магия то с точностью что ли. Я очень долго вчитывался в решения других и искал ошибку в своем, но так и не нашел. Сама суть решения довольно простая и понятная. Мне кажется, многие просто, как я, неаккуратно написали и завалились.
There are 644 contestant in Div. 1 and there are almost 200 contestant who have no point.
My 2nd Div1, I am very happy with 57th. Thanks for the problems, I really liked them. If only I didn't do A so slowly!
What I am wondering is how people hacked A. I noticed that many people got caught on system test for A, but when I was trying to hack I couldn't find anything! So does anyone know common mistakes in A?
The contest is over and I still can't understand the statement of problem B. An explanation for the second test (not for the one with a single number in the array) would have been great ... Could somedody explain it?
You look for each number in which distance (according to indices) they occur. In the second test case, 1 is on the indices 0-2-4-6, means distance 2. 2 occurs on indices 1-5, means distance 4, and so on. If there would be a number that doesn't have a repeating distance (for example indices 1-3-6), then you shouldn't print it.
you need to check all the indexes of all distinct numbers can represent an arithmetic progression 2nd sample indexes of (1) are 1 3 5 7 arithmetic progression with diff =2 indexes of (2) are 2 6 arithmetic progression with diff =4 all other numbers are unique so print them with 0 as the problem states
It means you should output like this:
Whether the indexes of each number you choose in array meet arithmetic progression?
Yes, output the common difference. (output 0 when the number appears only once)
No, do not output this number.
You have to output all the numbers x in the array such that their indices (the positions at which x are located) form an arithmetic progression. If x doesn't appear, then you discard it. If it appears once or twice, it's okay. If it appears more than once, you determine if the indices (say the 1st, 3rd, 5th elements are x) form an arithmetic progression. (To clarify, this is the criteria for if you output x, not how you actually solve it).
For the second test case, only 1,2,3,5 appear so we only consider those. 1 appears at indices 0, 2, 4, 6 (0-based) and 2 appears at 1, 5. 3 and 5 appear only once. So all the numbers work. If 1 had also been at index 7, then it would not have been included as 0, 2, 4, 6, 7 is not an arithmetic progression.
Well, I really wonder can Problem C in Div.2 be solved by greedy algorithm?
Why did my solution come out like this in Test #11?
4671464
I am surprised your submission worked on the first 10 tests, but I guess they are pretty simple. Anyway, the problem states that half the numbers must be floored and half must be ceiling, but you do not take this into account. Also, I don't think a greedy idea like what you are attempting would work anyway.
Thanks for answering. My negligence.
Why was E E?
I thought it was hard, but I was wrong :)
I guess they may have a O(n^2) and hard solution and didn't come up with the O(nlogn) and easy one.
UPD. After reading rng_58's solution, I found what I said is wrong. The O(n^2) solution is much easier to implement :D.
Stupid question: why did all these solutions pass? It seems that for multiple equal elements we can take them with different signs, and this additional cost is not taken into account by straight-forward solutions. Is it possible to somehow exploit this effect and construct a challenge? Or maybe prove that this effect does not matter for some reason...
Upd: in russian thread people say that it does not matter, since if we take some element with "+", it is impossible to take some next element equal to this one with "-". I wonder how many people actually thought about it during the contest...
If we choose signs greedily, -x will never appear after x.
Well, if you have multiple elements with same absolute value, in optimal solution they will have minus sign until some point and plus sign after that point. So there will be no inversions between them.
Well, another reason that this task is not good for E is that the following "stupid" solution passed:
It will WA on test 11. But if we do the step 2 twice, it can pass the system test: 4673192
Is it actually correct solution?
If in step 2 we take "answer does not goes worse" instead of "answer goes better" then we even don't need to repeat this step twice)
And why does it WA, when we do it just once?
Because it's totally wrong. We could need to change several x[i], which would make the answer larger, and then change several other ones that would make it smaller. It just shows the weakness of tests.
Someone can prove, that if there are no i, such that if we change ("update") x[i] to -x[i] the answer goes better, then we could'n improve the answer.
This is such a natural type of statement, but in this particular case it's hard to believe in it. Of course, there is no guaranty, that after step 2 in our solution there are no such x[i] that we can update.
The idea of proof: Call the operation "inverse" of x[i] is multipling it by -1. Assume the contrary: there are no such i, that if we inverse x[i] the answer goes better, but we could improve the answer inversing number x[i] = a and x[j] = b to -a and -b (in a general case we have to inverse k numbers, but for more clearness we take k = 2). Let us consider numbers ka and kb. ka = (number of inversions in initial array — number of inversions after inversing a to -a). The definition of kb is analogous.
By assuming ka >= 0 and kb >= 0. Put the number of inversions = inv Case 1: ka > 0. When we inverse a and b, inv_new = inv + ka+kb. But we don't take in account pair (a, b), that can be "bad" (i.e. this pair is inverse), but (-a, -b) is "good". Then the number of inv_new >= inv + ka + kb — 1. Hence inv_new >= inv. A contradiction Case 2: ka = kb = 0. Let inverse a and b not simultaneously, but one by one. Then we can choose the correct order of chain of inversions (we inverse a, and then b OR b and then a), so that inv_new >= inv (Note, that a > b (elsewhere we have a contradition the same way as in case 1). Assume, that -a < b. First inverse a. inv_new = inv + ka = inv. Then inverse b. Since the pair (-a, b) is already "good" (and (-a, -b) too) and kb = 0, we have inv_new = inv. Again a contradiction. If -a < b is false then we will first inverse b, and then a)
I did step 2 just once (with "answer gets better") and it passed. And I think that it is correct. Reason:
We don't care about equal elements, as discussed here http://mirror.codeforces.com/blog/entry/9056#comment-147490 .
If we have Pa, Pb;|Pa| > |Pb|, then |Pa| > |Pb| ≥ - |Pb| > - |Pa|, so if we change Pb to - Pb, the "inversness" (whether they made inversion, or not) of these two numbers doesn't change. Thus inversness of two numbers can only be changed by inverting greater of them. That means that effects of inverting numbers on total number of inversions are totally independent. So we can do it greedily.
while(true){ System.out.println("THANKS SEREJA"); } contest very-very good.
A question: when i run problem A(in Div2) in custom test, it works fine without error but when i submit it, it shows runtime error! what is wrong?
In these line
You only read one char and set it to the line string ...
So the length of line string is 1 ...
Run-time Error occur when you try to divide a number by zero or accessing a index less than zero or more than the size of array ...
Here when index goes more than the 0 Run-time error occurs ...
But its not the only problem in your solution ... Find the others too ;)
it works fine on netbeans, next() read a string. i will try to find why index goes less than zero or more than length,
thanks,
It reads one string but until the space .The numbers are separated by space so it reads only one number.
You can easily check it by printing.
Anyway you need better debugging , Asking such questions may consider as spamming here.
Can somebody hint towards the solution for Div 2 C?
Hint: Round down all elements and then see how many you need to round up.
http://mirror.codeforces.com/blog/entry/9056#comment-147487
Can anyone help me on Div2 B Why my code outputs negative numbers in Test#11 4670950
I think sorting is not stable.
May be the left of the "or" condition was not intentional. I think the following was your intention
A friend of mine made a correct submission for Div2 B during the contest but he found out it was "Skipped". What's wrong? This is quite unfair.
Here's the link: http://mirror.codeforces.com/contest/352/submission/4665780
He made another submission on the same problem afterwards. For every problem, only the last submission is counted, and every submission before it (that doesn't get compilation error or WA on sample tests) gets -50 pts.
He did make a submission later but it was post-contest. During the contest that was his only submission. You can clearly see that here: http://mirror.codeforces.com/submissions/mahmouder
Oh, right. Sorry, I didn't notice. I have no idea why, then.
Я завалил С (див 2) только потому, что 0.096 вывел как 0.960 ((
Why do contest writers offen misspell "standard"? I'm not blaming anyone, I'm just curious.
Because of Russian word "стандарт" which means the same.
and "т"is usually transliterated as "t"
Oh, I understand. Thanks.
When will the rank be updated ?
its updated 10 minutes back :)
i dont like problem C in this contest! so trick for div 2 pro C, in fact, in div 1 dont much people can slove it fast such as normal
hey, can anybody tell me why my submission 4674576 for Div-1 A is giving wrong answer? thanks in advance.
What is your algorithm? It would be easier to identify the source of the error then.
got my mistake, thanks!
I wonder why this input (n = 2000 and 4000 zeros) was unsuccessful in hacking this code : 4663057, because the size of array in this code is 2010!
Array overflow doesn't necessary mean wrong answer or runtime error. It means undefined behaviour.
But in my case , it correctly gave a runtime error : 4662420
Exactly. It "doesn't necessarily mean WA or runtime error". It's undefined behaviour.
Screencast