Всем привет!
Совсем скоро, 13 января в 19:30 MSK состоится Codeforces Round #160, автором которого являюсь я. Это мой третий раунд на Codeforces и я надеюсь, что не последний.
Спасибо Жене Соболеву и Диме Соболеву (Seyaua и sdya) за помощь в тестировании задач, а также Геральду Агапову (Gerald) за помощь в подготовке раунда. Отдельное спасибо Марии Беловой (Delinur) за перевод условий на английский.
Разбалловка стандартная в обеих дивизионах.
Настоятельно рекомендую прочитать условия ВСЕХ задач.
Gl & hf ! :)
Контест окончен, надеюсь вам понравилось :)
Поздравляю победителей див1:
1). PavelKunyavskiy
2). Dmitry_Egorov
3). Nerevar
4). Egor
4). gawry
И победителей див2:
1). Pad
2). nirvanafreak
3). pablobce
Разбор по ссылке.
Good luck everybody!!! :)
Пора бы уже ввести рейтинг авторов контестов. Я думаю, сегодняшний проблемсеттер был бы в нем высоко :-)
Идея хорошая, я тоже об этом думал. Есть мысли, как это хорошо сделать? Например, ориентироваться на оценки поста — так себе. Они зависят от широты аудитории и, например, фейл сервера повлияет на оценку, хотя автор не виноват.
Может идея, возможно. не — очень, но как один из вариантов.
Трудно додуматься до критериев "хорошести" раундов, но недостатки можно выявлять, например гробы на контестах (обидно, наверное, когда только один — два человека решили задачу), поэтому предлагаю примерную схему системы баллов: за проведение контеста очки, вычитать из них определенное количество за недостатки
Не очень понятно, почему гробы — это сразу недостатки. Бывают такие симпатичные гробы, что за них хочется автору руку пожать да медаль повесить.
мне казалось это мнение большинства (серого — синего) на кодфорс
а какая польза и удовольствие от контеста, где только легкие задачи?
А почему не сделать систему оценки самих задач (как это сделано, например, на contester.tsure.ru )?
А как сделано там?
Кстати, можно действительно сделать какую-нибудь систему оценки задач.
И сделать топ задач, с указанием для каждой задачи ее автора.
Так как задач в архиве заметно больше, чем авторов, то по этому критерию можно выделить, к примеру, топ-20 или топ-50 задач (потому как топ-50 авторов — пока что не сильно отличаются от "всех авторов").
С одной стороны, каждый автор будет рад попаданию его задачи в такой топ. С другой, быть последним среди топ-50 — не значит быть последним в глобальном плане, т.е. пропадает проблема "обижаем нижних".
вот так выглядит банк задач (рейтинг указывается в таблице напротив каждой задачи)
а вот так окно с условием задачи
каждый, кто читает условие задачи, может ее оценить по пятибалльной шкале. тут, разумеется, можно подумать над ограничением круга пользователей, которые могут оценивать задачу. Например, ввести параметр сложности и разрешить оценивание только людям с достаточным рейтингом для этой задачи (ну или с проверкой, решал ли этот человек ранее задачи подобного уровня сложности).
Весьма спорно. Кажется любой проблемсеттер достоин похвалы и было бы неприятно быть последним в этом рейтинге.
UPD. На мой взгляд, максимум, что может быть, это количество проведённых контестов.
Но если рейтинг, например, будет просто равен количеству проведённых контестов, то обижаться будет не на что.
Как раз upd такой же написал :)
Только при этом теряется оценка качества раунда например. И непонятно с каким весом учитывать Div1/Div2. И еще много подобных мелочей и не очень мелочей.
Идея хорошая, только вот слово "рейтинг" тут звучит плохо, т.к. подразумевает некоторое сравнение на лучше/хуже. Которое для начала попросту некорректно, да и его сложно сделать объективным. Кому-то нравятся сложные раунды, а кто-то любит когда у 20 человек сдано все. И к сожалению многие меряют качество раунда своим выступлением на нем.
Количество != Качество. По-моему, один хороший контест с интересными задачами должен быть оценен не хуже, чем, например, два контеста с неинтересными (ну или Div-2, где обычно задачи не идейные, а "на реализацию", которые придумывать гораздо легче).
А если по количеству, а в случае равенства -- по среднему рейтингу поста с анонсом? Просто часто люди снижают рейтинг поста в случае некачественно проведенного контеста.
" Problems’ point values will be published before contest. " So the point values may not be as general?
"I strongly recommend you to read ALL the problems.". Probably.
Sereja always recommends to read all problems and it doesnt mean that point values may not be as general.
I suggest this phrase means that E will be easier than usual. At least, E from the last Sereja's round was simple segment tree.
So sad,I have a important final exam in tomorrow moring.I have to sleep early so I can't participate this round. And wish all the participants get high rating :)
You're lucky if you're sleeping not preparing last night :)
Good luck everyone ! Anyway, does anyone know any good book to prepare for Codeforces's contests ?
Uh, I think doing past problems on codeforces will help.
CLRS
Codeforces Gym.
The Codeforces Tutorial page is a good resource if you get stuck on a problem.
Edit: However, it's currently missing the most recent rounds. It would be nice to have them all collected somewhere.
В задаче B, k меньше n?
Ops, всё. Догадался. :)
У меня появился вопрос по заданию C: в 3-ем примере правильный вывод должен быть 5 Поправьте,если я неправ.
Там все правильно — берем 1 товар и 2 бесплатно, потом ещё раз (уже 6), остается 1 который покупаем. Итого 3. Но это не единственный способ.
Почему не получается отправить файл для взлома? Формат .txt, размер меньше 256 килобайт, формат верный.. Баг какой-то, или у меня у одного такая проблема? Выдаётся сообщение Невозможно обработать взлом, попробуйте еще раз
Не только у тебя, я тоже не мог отправить файл и выдавало точно такое же сообщение.
Sorry but a little question for pro C div.2 (it's not clearly stated)
can any item be left out (not using the discount)?
No. You need to buy all the items.
The statement wasn't clear to me either :-/
You are asking two questions in fact:
In my case I was lost in how the discount works. It works so, you have something in basket, and you add new (0, 1, 2) items to the basket that are for free than, but the condition from statement have to hold.
In problem A (Div 1), can somebody explain me what the sentence "_each of them mustn't be more expensive than the cheapest item out of the qi items in the cart_" means?
do you mean problem A (Div 1)?
I'm sorry, you are right
It means that, after using the i-th discount, and buying its qi items you are able to select (0,1,2) items cheaper-than or equal-to the cheapest among qi
It simply means, that if you want a discount, you can apply it only to the item, that's cheapest in your cart.
Sorry, I'm just noob
In div1 :)
for problem B in Div 1 , I could not find any way to fit values in any data type except big int. So I had to go for python (though I could not complete the code) . I would like to know how guys managed to do in c/c++.
EDIT: I had underrated power of double. :(
double works fine because answer is floating point number
I've computed factorial using long double and it passed. value of 50 factorial using long double have significant difference with actual value, i thought i wont pass. I am curious to know what is the reason that long double didn't cause bigger error? (my code got tle system test just because i forgot to set dp array :(, it passed later in practice).
actual value of 50! is, A=30414093201713378043612608166064768844377641568960512000000000000 & using long double it is, B=30414093201713378039796484017234741538658648106343392576177963008 so the relative error is 100*(A-B)/A = 0.00000000000000001255 % which is very little, & thus can be ignored
If you solved the problem using DP to count how many subsets of a given size can appear before the i-th element for each i, you can also use long long int since the answer will not exceed 2^50. One can also use long double to compute the factorials and the "final" answer if one doesn't trust enough on double.
огромное спасибо за этот контест. Задачи были очень интересные, на мой взгляд
In Div1 E, does author's solution consider the following case? When you want to write 64, 7 moves is optimal: (1,0) -> (1,1) -> (1,2) -> (1,3) -> (1,4) -> (4,4) -> (16,4) -> (64,4)
Yes, ofcourse :)
wn will u publish tutorials??
As soon as it will be done :)
Если в A задании учитываются только счастливые числа 4 и 7, так почему же в первом примере ответ 3, когда там только одно счастливое число 4? Или же всё-таки речь идет о любых числах не превосходяших k?
Ноль счастливых цифр (0 < k)
В условии речь про количества цифр, а не чисел.
Very nice problems ... I have learned some new tricks ;))
what exactly?
This tricks or tips or whatever you would like to call them apply to me, I don't know about you, but maybe you can learn something from here
:)
Any ideas for solving C ?? I was trying to find some pattern but of no use.
Number of one's in the last row if the matrix has a size of m http://oeis.org/A048896
Number of ones in i-th row equals to 2bin(i) - 1, where bin(x) is number of ones in binary representation of x. It's quite simple fact: if you draw a picture 100x100 you'll see lots of Serpinsky Triangles, also known as Pascal Triangles modulo 2. And number of ones in a row of Pascal Triangle modulo 2 has well-known formula (One way to prove it is using Luka's Theorem).
very fast system testing!
Even during the contest, pretest results were very fast. Nice Work
Как приятно, когда систест быстрый!
А зачем такой странный TL по D?
У меня решение работает за 0.6 с. На джаве что ли настолько медленнее работает?
У меня решение работает чуть больше 2х. (на плюсах)
Ну, у меня вот решение 5k^2 * log 100k * 10. Уложилось в 3 с правда
Ты уверен, что о той задаче? Мне даже страшно представить откуда взяться количеству тестов в квадрате?
Где ты видишь количество тестов в квадрате? Тестов 10
Тогда я запутался в обозначениях и не знаю что такое k. Ладно не суть важно, я уже обсудил с автором, что у нас разные решения просто.
5k = 5000
Я кстати думал, что такое точно не зайдет, долго сомневался насчет 10 * 5000^2, потом написал, и заработало на случайных быстро.
Ну вот 2.5 миллиарда, казалось бы, должно проходить в 6 секунд. А 250 миллионов и в секунду легко
Как решать B (div1)?
Для начала переберем первого человека, который не влазит за стол, пусть его номер — k. Для всех оставшихся людей подсчитаем динамику dp[i][j] — сколько существует подмножеств из i людей, таких, что их суммарная толщина равна j. После этого для каждой суммарной толщины width, удовлетворяющей условию width + a[k] > p перебираем количество людей, которые набрали эту толщину. Пусть это количество равно q. Тогда у нас есть q! вариантов размещения людей перед k-м человеком и (n — q — 1)! вариантов очереди после k-го человека. Следовательно, к ответу необходимо прибавить q * q! * (n — q — 1)! * dp[q][width].
В конце не забываем поделить ответ на n!.
WOW ! That was a very cool contest . I liked the problems very much :) , the system testing was very fast :) and there weren't any bugs with the system :). With one word — great :) !
Какой-то чекер неправильный...
wrong answer 1st numbers differ - expected: '21.28731', found: '2.83180', error = '0.86697'http://mirror.codeforces.com/contest/261/submission/2919636Это относительная погрешность
Почему в задаче С для теста 6 4 ответ 1?
там мы имеем дело не с m, а с m + 1 строками и как раз на этой последней строчке будет 4
can div 2E be solved using http://oeis.org/A048896 and binary search ???
Контест прошел феерично... Сначала чуть не проспал начало, и в результате какое-то невообразимо долгое время решал B и C (непонятно, кстати, какая из них сложнее, мне кажется, B). Остается 25 минут до конца, читаю D. За 15 минут до конца начинаю писать явно треш с бинпоисками. Как и все на этом контесте, заработало далеко не сразу, да еще и упало на претесте. 5 минут до конца. Много бинпоисков... Много бинпоисков... Ну, конечно, указатели! Исправляю, остается 22 секунды до конца, отправляю. AC:)
Задачи, кстати, очень интересные, и в первых четырех кода совсем мало. Спасибо большое автору!
Задача С div 2, A div 1, кто подскажет хитрость 4 претеста? У многих падало на нем, а полностью он не влазит в окошко отчета. Или кто может подсказать ошибку моего решения? http://mirror.codeforces.com/contest/262/submission/2920411 Спасибо.
Посмотри, когда
minimal = 1. Не уверен, но пока что только это увидел, как тонкое место.UPD. Никогда! Вы слышите? Никогда не меняйте
iв цикле поi! Может ошибка-то и не из-за этого, но это очень очень плохая привычка.попробуй тест 1 2 -1
Спасибо, ошибка подсказали, она была в строчке min, вместо нее для коллекции нужно min_element.
There might be an issue with the testcases for problem div1-C.
My solution: http://mirror.codeforces.com/contest/261/submission/2919058 and ACube's solution: http://mirror.codeforces.com/contest/261/submission/2919909 give different results for the test case 1505335291 524288 . On my computer my output is 42353463, while ACube's is 42353462.
Wow! Fast System test and no bugs and etc. Thanks.
Вот это я еще чуть чуть и попал бы [1968 мс 2156 КБ] на Java 6 и то же самое на Java7 [171 мс 308 КБ] :)
На Java6 мое решение не прошло. Один в один символ на дорешивании с Java7 прошло :-(
Есть что намотать на ус: "Всегда! Всегда выбирай Java7!"
Это довольно странно, вроде можно построить тест и против сортировки в седьмой джаве, пофиксили что ли недавно?
Скорее всего просто был взлом антиквиксорт тестом решения на 6 джаве и этот взлом добавился в финальные тесты, а решения на 7-ой либо не использовали встроенный квиксорт, либо их просто никто не взламывал.
Thank you Sereja and everyone else for these great problems. Have fun everyone with great coding time :)
In order to get in div1, it took me a year to learn and practise, while you only needs one contest :)
where have u learned these stuffs??
practice.
In my case, it took about 2 years. I started solving problems from 16th January, 2011. That day I was introduced to my mentor by my friends :)
we can solve any riddles, my preciousssss
What have I got in my pocket?
it isn't fair, my precious, is it, to ask us what it's got in it's nassty little pocketsess?
Servers are fast these days! For Div1 B, I submitted a O(p * n^4) solution, and to my surprise it got accepted! It took 1/2 second on the toughest test.
Problem C div-2 wasn't clear. The statement says " To use the discount number i, the customer takes a special basket, where he puts exactly qi items he buys." and that wasn't clear enough to state that a basket may have less than qi items in it.
No. A special basket must have exactly qi items in it. But there was also said that he can buy items normally without discounts. I overlooked it at the start, too, but that's the first thing one needs to ask: could there be "no solution"?
can anyone tell me for div2 C why the correct output for this test case is 5 ?
24 771 1 1 1 1 1 1 1according to this statement "where he puts exactly qi items he buys", isn't the correct output is 7 ? because if we use first discount, it can't be fit with the number of items in any ways ?
1 1 1 1 1 1 1
b b b b f f b( b == buy; f== free)
answer — > 5
I also struggled on this part for a minute. If you read carefully the problem statement says you can use the same discount multiple times
Проблема С (див2.). Помогите, пожалуйста, кому нетрудно. Сообственно вопросик, верно ли, что если : 1.Упорядочить 2 массива( скидок и вещей) по возрастанию. 2.Брать всегда количество вещей, которое будет в массиве скидок на 1 позиции.(тоесть наименьшее количество вещей). 3.Брать всегда самые дорогие вещи, тоесть идти по массиву вещей с конца. 4.Брать всегда 2 вещи по скидке. То я получу верный ответ? Падает на 5-ом тесте, к сожалению, баг отловить не получается. Кому нетрудно, пожалуйста, помогите. Буду очень благодарен! Спасибо, взаранее. Вот собственно код: http://mirror.codeforces.com/contest/262/submission/2919820
Верно. Где-то в реализации набажил, наверное.
offtop: научитесь передавать массивы как параметры процедуры — не придется копипастить qsort.
Я новичок, если нетрудно, можно ссылочку на пример, пожалуйста.
Ссылочку на пример попросите у гугла)
Хорошо))) Всё равно огромное спасибо=)
Подсказка:
http://mirror.codeforces.com/contest/261/submission/2921577
Код ваш, добавлено лишь {$r+}.
в "обОих" дивизионах:)
DIV 2: Problem C
Statement: The only condition imposed on the selected "free items" is as follows: each of them mustn't be more expensive than the cheapest item out of the qi items in the cart.
Input: 1 2 4 50 50 100 100
Output: 200
Note: In the first sample Maxim needs to buy two items that cost 100 and get a discount for two free items that cost 50. In that case, Maxim is going to pay 200.
Am I correct? If i take 50 50 in the cart and take a discount of 1 item. Then 100 100 in the cart and take a discount for 1 item Total Cost=150
According to the statement it's allow.
If i am wrong, please explain. Thanks in advance.
You need to use all space in the cart
Of some other item, which is cheaper. So, if you "take 50 50" you can't have any discount in this testcase (because other items are more expensive).
DIV 2: Problem C
Statement: The only condition imposed on the selected "free items" is as follows: each of them mustn't be more expensive than the cheapest item out of the qi items in the cart.
Input: 1 2 4 50 50 100 100
Output: 200
Note: In the first sample Maxim needs to buy two items that cost 100 and get a discount for two free items that cost 50. In that case, Maxim is going to pay 200.
Am I correct? If i take 50 50 in the cart and take a discount of 1 item. Then 100 100 in the cart and take a discount for 1 item Total Cost=150
According to the statement it's allow.
If i am wrong, please explain. Thanks in advance.
50 50 100 100 if you take 50 50 you can't use discount because according to statement:"The only condition imposed on the selected "free items" is as follows: each of them mustn't be more expensive than the cheapest item out of the qi items in the cart."
I think you understood it wrong. The free items you get are not the ones you have in your discount but additional ones.
Wrong, in your case, you will pay for (50, 50) and get extra 0 items for discount, and you will pay for (100, 100) and get extra 0 item for discount.
You are paying 300 in total, discount doesn't mean you can deduct value for what you've paid for.
Hope this helps.
For me the statement wasn't clear too.
Most important is this sentence: "..in addition to the items in the cart the customer can receive at most two items from the supermarket for free...". That means, that you choose items to buy, add those to cart and as a bonus you can choose 0-2 items as free ones.
In this case you choose 100 and 100 in cart and then you get 50 and 50 as a bonus items, so you pay 200.
I asked 3 questions during the contest how the discount works and none of the answers helped me to realize that, later I somehow realized...
So, at the end of the test case any of the free items price has to be less than or equal to the item that has been bought. :)
Now, i have understand. Thanks.
У меня одного открылись права редактирования тегов к задачам это контеста? Такого вроде не должно быть)
Чтобы иметь права редактирования тегов, ты должен: иметь синий цвет и выше + решить задачу. Так что все норм.
Спасибо за пояснения, это просто мои первые часы в "синем цвете")
Скринкаст: http://youtu.be/25FMrfEPRBI?hd=1
if( j < 0 ) { break ; }
just absence of this line in my code has cost me 2nd place in div 2 today :(
Когда опубликуете разбор?
Codeforces Round 111 (Div. 2)
i just want to ask about problem C. in this test case :
1 2 3 50 50 100
why the answer is 150 ? why not 100 ? if he got the first and second he'll get '50' free .. so 2 items of 50 and 1 item 50 free .
please if someone can explain
You must put in cart exactly qi items ...
There is only one qi, which is 2. So you must buy 2 items to get a discount.
You buy 100 + 50, and get free 50 => total cost = 150
You buy 50 + 50, you get no discount, because 100>50. This way you buy everything so the total cost is 200.
aha okay got it .. thanks man !
Who can explain this http://www.codeforces.com/contest/261/submission/2917414 solution for Div1-B?
In Div1 Problem A, I was confused because the problem statement considers the terms "basket" and "cart" to be the exact same thing.... Maybe that also caused many people confused about the discount system.
Yes, I was also confused about problem A, & had to ask 2 questions to understand the problem clearly .
I solved three problems in yesterday's contest 160 in Division 2 . The contest page shows 3 out of 5 solved . However the problems page shows the "solved" color in only two of the three problems I solved . The third problem "Maxim and discounts" is not colored as solved . My rating has gone down from 1620 to 1579 . Last time my rating increased when I solved only two problems correctly . This time my rating has gone down after 3 successful submissions . I suspect there is some error in record keeping .
Number of solved problems on its own doesn't matter. Only place in contest standings matters. Your place in this contest is worse than in previous, so it's natural that your rating decreased.
Yes , but what about color code of problems solved successfully in the problems page . It is colored only for 2 of 3 problems I solved .
Rating is recalculated after each contest based on your contest rank, not number of problems solved. About 'color not showing solved' in the problem set page, it is because the last 3 problems of div 2 is added from div 1. I solved 4 in div 2 and problem set page shows 2. See the problem ids in the problem set page — (262B,262A),261E,261D,261C,261B,261A. Only 262A and 262B will show solved. Rest are from div 1.
But should that happen when the same problem appeared in both the divisions . 261A is same problem as problem C of division 2 .
They only upload the div 1 version, otherwise if they added both problems, same problem will be added twice, I guess that's why they do it.
Okay , thanks for your replies .
Надо полагать, разбора на русском не будет?
Добавил разбор на русском.
In problem-C Div2, the problem statement first uses "special basket" then "cart". And I think, maybe, it will be helpful to use only one of them so that contestants which have bad English ( for example : me ) would not get confused. ( I didn't know "cart" == "basket" )
edit : oh, missed something "where he puts exactly qi items he buys"