Здравствуйте все!
Сегодняшний раунд был подготовлен для вас SergeiFedorov и мной. Мы приложили максимум усилий, чтобы раунд получился разнообразным (как по сложности задач, так и по темам) и рейтинговым (ведь многим это так важно). Все ваши вопросы, пожелания и конструктивную критику (деструктивную мы и сами горазды производить :-)) оставляйте в комментариях.
Тем кто будет писать раунд предстоит окунуться в атмосферу ледяного февраля в городе XXXvodske и помочь компании друзей не умереть от холода. Помните, какая ответственность на вас лежит)
Пользуясь случаем хотелось бы поблагодарить всю команду Codeforces за то большое дело, которое они делают, Артема Рахова (RAD) за помощь в подготовке задач, Марию Белову (Delinur) за перевод условий на английский язык, маму, папу, нашего звукооператора и виноделов провинции Тоскана за то, что мы не заболели и смогли готовить для вас этот раунд.
Разбалловка ожидается следующая:
div. 1: 500-500-1000-1500-3000 (да-да, последняя задача того стоит)
div. 2: 500-1000-1500-1500-3000
Good luck & have fun!
Пост улыбнул :) Всем удачи!
Ай чёрт. Не туда.
Текста анонса готовил небось, дольше, чем какую-нибудь из задач?)
Ты даже не представляешь, сколько времени ушло на последнюю)
http://acm.timus.ru/problem.aspx?space=1&num=1589
Нафиг регистрироваться ради одного сообщения, со своего акка запостить чтоль нельзя?
М-да, я бы предпочел не прикасаться к этой Е даже двадцатиметровой палкой :\
Good luck all.
3000 point problem In both division :O . That would be amazing (either for solving or learning) :)
3000!! Is the problem something like writing an OS? :)
Yeah, perhaps more difficult. \m/
Можно ответить на вопрос, зачем SergeiFedorov зарегистрировался на контест? Какие-то фишки codeforces с точки зрения недоступности авторам условий и доступности их участникам или Сергей тупо хочет рейтинг поднять о_О?
Дурак ты. Много раз уже обсуждалось, авторы контеста затем логинятся в контест, чтобы видеть полновесную админскую панель, все необходимые плюшки. Самому никак догадаться?
Спасибо за ответ, именно это я и хотел услышать. Еще бы хотелось услышать, что именно недоступно из админской панели(как и было написано в моем посте).
Проведи контест и узнаешь :-)
ежу понятно, что не второе. мог и не писать второй вариант
Система так устроена, что надо сначала зарегаться, а потом поставить галочку, что ты админ
Ясно. А если не регаться, то, как понимаю, у автора будут полностью связаны руки?
Уже довольно долго не так, наверное Сергей об этом не знал.
Опоздал на регистрацию((
Вот почему нельзя продлить регистрацию вплоть до начала ?
чтобы успеть разбить по комнатам, очевидно
По-моему, это уже давно пора добавить в ЧАВО.
For problem B div 1, substring means contiguous sub-sequence?
Did you know that there is "Ask a question" function here?
I asked the same question during the contest, and they said "NO".
[Edit] I was wondering why I am getting negative votes, but when I read my question again,
what I asked was 'Is "ac" a substring of "abc"?'.
What a foolish mistake! I am sorry for the confusion.
Weird. I asked this question too, and they said "yes".
В оповещении было написано undefined, а не тот текст, что должен быть
Причем два оповещения — два лага.
а еще в первый дивизион пришло оповещение из второго.
Да, и из-за этого бага я сначала не поняла, к чему вообще это и довольно долго продолжала разбирать дебажный вывод по второму тесту.
Раунд рейтинговый или нет?
Не первый раз понимаю, что по-хорошему раунд должен быть нерейтинговый, но самому хочется, чтобы рейтинговый был :-) Ну, если многим участником помешало. Я думаю, многим — если не читать этого анонса, то можно надолго засесть над дебаг-аутпутом в C, что я и сделал.
Не пропадает
PS: если уж это сделано не всем, а не только тем, кто что-то спрашивал:
Может стоит кидать оповещение(как о взломе), о том, что на вопрос ответили
Думаю, что до конца контеста не пропадет.
Наверное, просто в HTML-разметку всех страниц встроили это.
У меня это появилось, когда я задал вопрос, думал фичу сделали, что сообщаяется, когда ответили. А тут видимо всем сделали
ну нееееееет, не анрейт, пожалуйста!!
У меня у одного сегодня как-то жутко лагали взломы? После нажатия на кнопку взломать страница залипает, и никак не реагирует на твои действия (хотя по-хорошему должна редиректить на страницу взломов). Тем не менее, сами взломы проходили (на это не жалуюсь :-)
было один раз такое
не у одного. потратил лишнюю попытку из-за этого.
Я из-за этого два раза неудачно вламывал одного участника одним тестом. Правда уже минут через 10, мой второй неудачный взлом, в системе отображался со статусом "Игнорирован".
Во-во.
div1, B. What if (k > n) ?
mn
Я час потратил, чтобы это понять. В конце от безысходности изменил так условие и прошло:(
какого чёрта? "строк длины ровно n", "ПОДСТРОКА длины В ТОЧНОСТИ k". у меня у одного проблемы с пониманием того, как любая строка может подходить?
Покажи мне хоть одну подстроку длины 42 в строке abacaba, которая не является палиндромом.
спасибо. условия кривоватые.
any string is OK. So ans in mn
Than any string will do as there is no restriction
Why is that... when k>n there doesn't exist any string satisfying the constraint shouldn't the answer be zero...?
We do not need a string, that should satisfy the constraint. We just required that ANY string must satisfy the constraint
That's totally misleading statement... :( (or I was too stupid to figure out at the time :P)
If you've worked with logic you come to think like that.
The statement "If 1=0 then 2=3" is always true, because 1 isn't 0. After some time you forget that that's not the way normal people think, (They think the statement doesn't make sense), and confusion can happen.
However, I very much recommend thinking the logic way. It just works more often :)
I also thought 0. :(
Me too. The problem statement is not well written.
When k > n, there are 0 substrings of length k. And there are 0 substrings of length k that are palindromes.
0 = 0, therefore all substrings of length K are palindromes. In this respect, the problem statement was written correctly.
However, it IS a common confusion specially if not familiar with how the "For every" quantifier works on empty sets. And after all, (n > k) is a silly test case to include — its only addition to the problem is this confusion. I think at least it would have been better if (k > n) was not allowed or was an example.
Five minutes or so after receiving WA #3, I raised a clarification asking that, for K > N, whether I should output N^M or 0. And the reply I got is:
"No comment."
I asked if for K > N is 0 correct answer and reply was "no".
[Posted to the wrong position] I am really sorry.
why the answer is not 0? I got lots of wrong answer on case 3..
Here is your answer ;-)
За какую сложность решалась D? Я хоть убей ничего круче пятой степени не придумал, написал, оно очевидно ТЛилось, поэтому бросил дебагать.
Авторское решение — четвертая степень.
Какая идея?
Скоро будет разбор.
Гут. У меня тоже 4я, и я боялся, так как ограничения намекают на 3ю
Оффтоп: Спасибо за взлом, кстати =)
Я за четвертую степень написал. На макстесте на моем компе чуть больше 2 секунд работает. Хотя скорее всего упадет из-за stackoverflow
С 64 Мб стека? Или у тебя вызовов 4я степень?
нет, ведь на CodeForces стандартный стек не 64МБ. Хотя, я сейчас запустил на макстесте на сервере, отработало нормально.
Хм, я почему-то был твердо уверен, что на КФ стек 64m. Наверное, из RCC отложилось
Дайте кто-нибудь, ответы в задаче C div 1, для второго семпла, для каждого запроса.
+1, я никак не могу догнать, как у них вышло такое число во втором сэмпле...
2517434
90682
27243
4000
2517434
7772
2517434
4000
(Всё следует поделить на 100)
Хмм, каким образом считается в таком случае мат. ожидание? Расскажи на примере для 1 пассажира
Посмотрим, что происходит, когда какой-то пассажир проезжает сегмент с X[i] до X[i+1] без билета. Матожидание прибыли за этот отрезок — 0.5*(X_[i+1]-X_i) — c*p_i, потому что мы выигрываем с этим отрезком его длину пополам — столько нам пассажир даёт выигрыша, и с вероятностью p[i] мы ещё потеряем на этом отрезке c. Назовём эту величину X[i]
Теперь у нас встаёт вопрос, как бы выбрать в отрезке [A;B] отрезок с максимальной суммой X[i]. Это боян — делается деревом отрезков, где мы храним в каждой вершине четыре величины — отрезок с максимальной суммой в поддереве, отрезок с макс-суммой, утыкающийся концом в левую границу поддерева, отрезок с макс-суммой, утыкающийся концом в правую границу и сумму по поддереву. Через эти четыре штуки пересчитываются следующим кодом:
return node(max(a.l, a.s + b.l), max(b.r, b.s + a.r), a.s + b.s, max(max(a.v, b.v), a.r + b.l), a.len + b.len);Как-то так.
Что-то математическая разметка не работает :-(
Xi
А можно c и d для предпоследнего пассажира (который едет с 4 по 10)?
Как по мне, доход на каждом отрезке такой: [-19.31, -152.69, -101.55, 40.0, -107.0, 77.72, 194.71, 634.39, 24267.52]. Вот я предлагаю продать ему с 4 по 5 и с 6 по 10 (т.е. c=5, d=6) и получить доход 25214.34.
Э, да вы запутались :-) Вы не то максимизируете. Надо максимизировать не сумму вот этой хитрой величины, которую вы правильно посчитали (
но я бы на вашем месте аккуратненько заменил отрицательные числа на нулименя клинит, не обращайте внимания) на [A; C] и [D; B], а наоборот, максимизировать сумму на [C; D]. Потому что то, что вы посчитали, это сколько можно получить профита, если соответствующий отрезок не включить в билет для пассажира.А... условие ж подправили... теперь стало даже проще. Спасибо за ответ!
25174.34
906.8199999999999
272.42999999999995
40.0
25174.34
77.71999999999997
25174.34
40.0
Для первого запроса если продать чуваку билет с координаты 0 до координаты 70, кажется наша выручка будет ((51100-70)-(100+44+67+3+4)*187/100) / 2 = 25311.17,
штраф не делится на двоих ;)
Понял свою ошибку: я не учитывал то, что кондуктор иногда всё равно получает прибыль от пассажира, даже если контролёр "запалил" его :)
C решается за n*ln(n) или проходит n*sqrt(n)?
Решается. Давайте предподсчитаем для каждого отрезка между соседними остановками матожидание прибыли. Теперь нужно ответить на кучу запросов "найти подотрезок данного с максимальной суммой". Решается деревом отрезков. Храним в вершине: ответ, сумму, максимальный суффикс и префикс. Как-то пересчитывается.
Блин, как просто-то)
Ну надо же в этом коде 1187859 если входным числом будет 2, то d[0] в котором находиться 2 будет умножаться на элемент локального массива, в котором содержится мусор. Оказывается что там будет 0 =(
Условие задачи A мне показалось каким-то сложным для понимания, я умудрился неправильно понять, что же такое "ход", можно было и попроще написать. А вот косяк с условием в задаче C ставит в очередной раз под сомнение качество проверки задач перед раундом. Супер-крутая команда вычитывальщиков в очередной раз не замечает тотального провала в условии, благодаря которому даже ответа на тесты из примера получить невозможно. В ходе раунда сайт падает на пару минут, а broadcast сообщения почему-то не работают. Codeforces для меня мертв.
Паша, всегда легко пенять на авторов контестов, однако ты же понимаешь, что основа твоего проигрыша — твои косяки. Ведь все были в равном положении. Никто не торопил тебя и не заставлял во второй задаче забывать брать по модулю ответ, например. И, кстати, в условии С мне сразу стало понятно, что там подразумевается, НЕ продавать. Видно, что опечатка. Конечно, это серьезный косяк, но решаемый и понять его можно. Я не отрицаю вины авторов, но все же и всю вину только на них свешивать не стоит =)
"И, кстати, в условии С мне сразу стало понятно, что там подразумевается, НЕ продавать."
Я тоже так хочу, научите?
"Однако кондуктор может продать пассажиру билет от остановки c до остановки d (c < d), или вовсе не продавать билет." Ключевой момент в том, что он может вовсе НЕ продавать билет, здесь было написано все именно так. не пропустили только в первом случае. то, что он может продать билет на весь маршрут следования — очевидно из остального условия. в общем-то у меня эта фраза вызвала нехилый диссонанс в мозгу и заставила задумать. после небольшого размышления я пришел к мысли, что здесь логичнее всего было бы дописать НЕ перед продать и что это с большей вероятностью опечатка, чем тотальная неграмотность автора =) В общем вопрос к жюри назрел, но клары подоспели вовремя =)
Павел, уже в который раз после своего очередного слива Вы пишете о косяках codeforces. Безусловно, эти косяки имеют место быть (как и на другом небезызвестном сайте), но всегда проще винить других чем найти ошибку в себе. Разумеется, я даже не буду говорить Вам о том, что условия у всех одинаковые, и точно так же, как и вы, не могли вычитать условие еще более ста человек(и наверняка не смогу вычитать его я, когда буду прорешивать данный раунд виртуально — учитывая, что я очень "хорошо" читаю условия) — Вы сами это прекрасно понимаете, просто почему-то не хотите признать. Конечно, кто я такой чтобы Вам советовать, и, конечно, я не хочу Вам навязывать своего мнения, но, на мой взгляд, весьма продуктивен подход когда после каждого раунда вы делаете его анализ по каждому Вашему действию, по каждой Вашей удачной или неудачной посылке, по каждому рисунку который Вы нарисуете в блокноте во время контеста.
Почему в В, если k > n , то mn ? Я наоборот специально сделал, чтобы выводило 0, и весь контест не мог третий претест пройти.
Потому что для любой строки любая(из 0 существующих) подстрока длины k подходит. Что нам и нужно
Я это понял так, что нет ни одной подстроки длины k, значит ни одна строка не подходит, значит ответ — 0. Я один такой?
Ни одна строка не подходит. Это правда. Но при этом все строки проходят. Это тоже правда.
А у нас вопрос, про ВСЕ
любое утверждение для пустого множества верно.
+1, в итоге 4 бревна
Тоже самое. Весь контест на это убил, не понимая, что не так.
Ну ведь правда что в строке abacaba все подстроки длины 42 палиндромы?
ну подстрок длины k просто нет, поэтому все они являются палиндромами :)
Так же. Совсем не очевидно, что для k>n надо выводить m^n. Если подстрок длиной k не существует, то значит, что они все — палиндромы?)
UPD: Можно подумать, что любая из 0 строк — палиндром. Но точно так же — любая из 0 строк — не палиндром.
ну если бы вам нужно было посчитать кол-во строк, где неверно, что "любая строка- не палиндром", вы бы не считали ни одну строку, т.к был бы верно второе.
Построение отрицаний, 5 класс средней школы %)
Там не k > n, а для этого случая получается, что мы не можем выбрать подстроку длины k из n символов. То есть подстрока длины k из n — это пустая строка, а пустая строка — это палиндром. Значит в ответом будет количество всех строк длины n.
Скажите пожалуйста, какой ответ в B div 1 для нечетного k? ( Все пограничные случаи проверены)
Видимо, m?Я не умею читать.
m*m
Почему так, в ведь у нас есть m^((k+1)/2) палиндромов и мы можем поставить их на n-k+1 мест, еще отсечение палиндромов с одинаковыми символами(m)?
все строки имеют вид 121212121212121(вроде не сложно понять)
Теперь ясно, вот это мне было и не понятно. Спасибо.
Хех, вот он, герой контеста — 1197076 :)
после тестирования увидим)
Ну что ж, почти.
Безжалостный TL растерзал нашего героя на мелкие кусочки :(
Though my rating may increase i think this round should be unrated. CF was down for about 7-8 minutes and also got down several times last 20 minutes. I lost valuable points because of server down,it got down just when i tried to submit C,and i had to wait for 7-8 minutes to submit it.
The worst part is that the problem statement for C changed. I didn't check the statement again and spent lots of time trying to produce correct output for C.
Statement for D was also changed.
Do they only happens in the English version?
If D also changed then they really should have updated the problems page with that message.
I mean really, there are messages for problem C/E so that if you read 'undefined' in a popup you will get to know that the problem statement was changed.
But if dolphinigle's report that D changed is true, then there should have at least be a note in the problems page saying that it was changed...
It was sort of minor I suppose (replacing "until" with "while"), though it did cost me some good time, since I turned off my common sense during programming contests.
Maybe I should rethink that protocol :S
I was the same
Same here... somehow did not get the clarification broadcast, couldn't understand what's wrong before refreshing out of despair
I've got a javascript alert which said "undefined". In last contest i've got same alert and than found that my solution have been hacked. But this time it was the clarification. Hope admins will fix it soon.
Ahh... There WAS also that "undefined" alert box for me. Somehow I wasn't in the mood or something I didn't think much about it and simply ignored the alert. Now that you've mentioned it there was indeed the JS alert box with unknown intention... Should have thought it's trying to tell me something though :p
Indeed when I got this "undefined" prompt, I had a first impression that, this may be due to some bugs in Codeforces system, or admin accidentally broadcasted a wrong message. (Meanwhile I was busy thinking for problem C sample test case #2, and I simply ignored the box.)
Perhaps I did this because in previous codeforces testing round, there was some prompt like "Don't worry, it's just a testing."
очень хорошие задачи. Спасибо автору(-ам). Интересно было решать.
I think it should be fair to make this round unrated. Lots of problems came up and affected vast of coders.
What datastructure do you need for maximum subarray part of div 1 C? I was thinking maybe use a segment-tree with several fields for combining the segments in the tree.
It can be done without segment tree.For each interval [a,b] its length(b-a+1) can be uniquely represented in binary number system.Let this number has m ones in binary form: length=2^k1+2^k2+....2^km..(k1>k2>...>km)..Then we can solve for intervals [a,a+(2^k1)),[a+(2^k1), a+(2^k1+2^k2) ),.... individually and also check for the subarrays which lies in several consecutive intervals.
Числа C и D различны для всех пассажиров? Не обязательно. Могут совпадать, а могут быть различны. Нет.
Ну почему этот клар не разослали всем? Ни хрена ведь не очевидно! "Более формально: Кондуктор выбирает не более одного отрезка..." Ну почему не написано, что не более одного отрезка ДЛЯ КАЖДОГО ПАССАЖИРА? Кучу разных отрезков выбирает ведь на самом деле...
+1
Блиииин, а я то весь контест понимал условие как написано: то есть, что кондуктор выбирает не более ОДНОГО отрезка -- хрен знает как такое решать. :(
такое то кажись проще — нужно найти только 1 отрезок с макс.суммой, вместо m.
Да, точно. Ну ладно, значит сам дурак, что не решил.
Нет конечно. Для фиксированного человека [A; B] учитываться будет только пересечение [C; D] с [A; B], то есть в ответ будет вклад [max(A, C); min(B, D)]. Поэтому не факт, что нужно брать отрезок с максимальной суммой. Не?
хмм. Для каждой клетки надо будет просто предварительно посчитать кол-о людей тогда вроде бы. Да, это видимо можно сделать тем же ДО, но уже более очевидным.
Это можно сделать тупо за линию, ДО как-то overdo
Эм, я видимо туплю. Как?
ЗЫ: умею еще тучей способов за nlogn
добавим 1 к текущему счетчику за каждого, кто садится на этой остановке и вычтем за каждого, кто выходит. Теперь в счетчике число человек, которые едут следующий отрезок
А как мы считаем те кол-ва?
UPD: А ну видимо можно предпосчитать.
Ну, в массивчик, не?
Ага, че-то я сегодня не слишком быстро соображаю:(
Ну, надо домножить на количество человек, которые "проезжают" данный отрезок
D решается формулой и с несколькими условиями. Гораздо легче чем С.)))
А я не додумал до конца :(
Я начал было разбирать случаи, потом забил и написал просто перебор. Можно построить граф связей, где ребро между i и j есть, если они противоположны в каком-то палиндроме (пробегаем по всевозможным палиндромам — ограничения позволяют). Тогда ответ это m в степени количество компонент связности.
проснулся перед контестом, в голове каша, начался контест затупил на чем можно было в А и Б, но все таки сдал, отделался малой кровью) ну к концу хоть соображать начал
Чёрт, почему (и одному ли мне) E[div 2] кажется идейно проще D? Расскажите D, если не сложно)
Решение в E придумал следующее: при помощи одного дерева отрезков подсчитаем, сколько пассажиров проезжает между соседними остановками. Тогда выгода кондуктора, если на этом отрезке билеты не продавать, составит(длина отрезка — вер-ть проверки * штраф) * к-во пассажиров. Соответственно, с помощью второго дерева отрезков найдём подотрезок с максимальной суммой. А больше ничего и не надо :)
Мне во время контеста казалось, что для различных пассажиров отрезки могут быть разными. Сейчас перечитал, сомнения остались.
Можно, в принципе, сослаться на "примеры и пояснения к ним — тоже часть условия". Но я тоже считаю, что такие места стоит уточнять в условии, а не примерах. Примеры — это совсем крайний случай.
А я вот никак не могу понять, как там можно понять иначе чем для каждого пассажира выбирается [C,D]
Более формально: Кондуктор выбирает не более одного отрезка с C по D (C <= D) на который он НЕ ПРОДАЕТ БИЛЕТ.
Ну это часть текста, где говорится об одном конкретно взятом пассажире, а значит для данного пассажира будет не более одного отрезка.
http://codeforces.me/blog/entry/3899#comment-79022
Жаль, что столько фейлов, задачи-то хорошие.
Кстати (если проигнорировать, что это решение не той задачи), обе описанные операци проще сделать без дерева отрезков: первую (offline RSQ) сканирующей прямой с дельтами, вторую (отрезок с максимальной суммой) — чем-то, что проще всего объяснить кодом:
Эм, вы находите только 1 макс. отрезок за
O(n), а надо бы такое делатьmраз.Или я что-то не понял?
Ну, это решение задачи, где C и D должны быть одинаковы для всех пассажиров.
Ты тоже неправильно понял эту задачу?
Нет, я понял правильно и не сомневался. Увидев в комментариях альтернативное понимание, стал сомневаться и сомневался минут 10, пока не посмотрел в код сдавших ее участников. А не решил ее потому что дурак :)
объясните пожалуйста, до меня все не доходит
я вот так и не понял, почему нельзя использовать сканирующий алгоритм поиска максимальной подпоследовательности для массива мат ожиданий каждого пассажира. А потом сложить их все?
вроде бы один отрезок ,на котором не продает, для каждого пассажира
Потому что это медленно.
В D (div. 2) рассматриваешь несколько случаев:
k > n: подстрок длиныkв строке длиныnнет, а, значит, они все удовлетворяют условию и любая строка будет ответом, т. о. имеемm^n;k = n: подстрока такая одна и, значит, она удовлетворяет условию тогда и только тогда, когда сама строка является палиндромом, а всего палиндромов длиныn—m^((n+1)/2);k = 1: каждая подстрока является одной буквой, а, значит, падиндромом, т. о. все подстроки удовлетворяют условию и любая строка нам подойдет, а всего ихm^n;k % 2 == 0: в этом случае ответом будетm, ибо нам подойдут лишь те строки, в которых все буквы одинаковы;Ну и
k % 2 == 1: в этом случае нам подойдут все строки форматаabababa, гдеaиb— различные буквы, т. о. всего таких строкm^2.Не забудем помодить, конечно же)
что за дискриминация див1, постоянно проверяют сначала див2! может стоит как-то чередовать?
Can anybody tell me what is the problem with using below code in problem B div 2?
it was working fine on my system but was giving wrong answer on pretest and also on custom as it wasn't erasing last ",". It cost me 2 penalties :(. Solution id 1192671.
Because
'\b'is a char too. It doesn't have any special meaning outside terminal.Does
\bmean backspace ?Yes, it does.
Thanks.
'\b' only means backspace on terminal, but it cannot erase you already output in the stream.
Thanks.
Ah, I very much like what you were trying to do. Those final ','s are so annoying :)
кажется С див1 все таки стоит 1500
Не, это была бы честная тысяча, если бы не ряд досадных оплошностей.
Спасибо за контест, интересные задачи) Для меня он не очень удачный, ибо я больше часа искал в D багу и так ее и не нашел. Бага же была в том, что для случая
k > nя выводил ноль, а не(m^n) % MOD, как же сложно было понять, что если таких подстрок в строке нет, то, значит, что все такие подстроки удовлетворяют условию и любая строка будет ответом, а не наоборот :(C-Div2. "Number's divisor is called non-trivial if it is different from one and from the divided number itself."
I thought it means that for number N, the divisor d should not be equal to 1 and N/d. But now my friend tells me that it meant not 1 and not the number itself.
Now, it makes sense. But why add the word "divided"? I took the long route of solving the problem because of this condition and now it is wrong.
Divided != divisor. If text was "...from one and from the divisor number itself", you'd have been right.
Кто сможет объяснить почему в задаче B div 1 если K > N то ответ M^N?
UPD. вопрос снят
Ну прочитай комменты выше. Три поста уже таких было.
Can anyone explain how the solution to the second example case of Smart Cheater is constructed?
I thought the conductor should not sell tickets for the last four segments, resulting in an expected profit of 466.32 + 973.55 + 2537.56 + 72802.56 = 76779.99, but this 80 less than the reference output. I can break down these numbers further if it helps, but I wonder what I'm missing here!
Conductor should choose C and D for each passenger.
For each passenger conductor may choose his own [C;D] in [A;B]. This segments [C;D] may be distinct for various passengers.
I got the same output as Soultaker. (And of coz, after quite considerably long time to find that the problem C's statement is updated.) The problem statements are so ambiguous... I could only understand it right now.
I think that these ambiguities are due to the English translations. The problem setters are usually programming contest veterans, so I assume they know how to write clear and unambiguous problem statements, but those qualities may be lost in translation.
For example, for this problem, I think for this part:
However, the conductor can choose no more than one segment NOT TO SELL a ticket for. We mean that conductor should choose C and D (С <= D) and sell a ticket for the segments [A, C] and [D, B], or not sell the ticket at all.
The original Russian text reads:
Однако кондуктор может не продать пассажиру билет от остановки c до остановки d (c < d), или вовсе не продавать билет. Более формально: Кондуктор выбирает не более одного отрезка с C по D (C <= D) на который он НЕ ПРОДАЕТ БИЛЕТ.
I don't know Russian so I'm not entirely sure whether this is much more clear, but at least I spot the word "пассажиру" (meaning "passenger") in there. The English version doesn't mention the word "passenger" at all, and in fact underscores that there is a no more than one segment chosen by the conductor.
I can't complain too much, though, as there were plenty of non-Russian competitors that were able to solve this problem, presumably using the English translation. Still, I would enjoy these contests more if for me there would be more actual problem-solving involved and less figuring-out-what-the-problem-is, especially since the problems on CodeForces (once I understand them) are often quite interesting.
Thanks for the clarification! That was not at all clear from the problem statement.
The Problem C's description's change waste a lot time of me or someone else...I think today's round should be unrated>_<...
+1 and Orz
ym clj!!! I think the sample 1 is too simple, and it is hard to work out sample 2 by hand.
Я один, кто написал в D (она же B div 1) систему непересекающихся множеств? :)
Нет, 1187876. tourist делал так же.
Да нет. Довольно очевидно, что она пройдет, а раз так — чего еще думать?)
Написа адекватное решение, не зашло из-за того, что я корявый и не до конца раскрутил наличие левого символа, переписал на dsu
объясните решение с СНМ пожалуйста
Условие задачи даёт нам много штук разных равенств вида S[i] = S[j]. Такие равенства дают разбиение на сколько-то классов эквивалентности — с помощью СНМ, видимо, предлагается сжать номера символов с одинаковыми значения в один класс, а потом вывести m в степени количество классов.
Переберем все подстроки длины k. Переберем все пары 1-k, 2-(k-1) итд в ней. Для каждой пары скажем, что они одинаковы, т.е объединим множества.
Посмотрим, скоько осталось множеств
Переберем все палиндромы (O(N)). В каждом палиндроме одинаковые буквы положим в одинаковые множества (O(K)). Посчитаем, сколько различных множеств получилось в итоге.
Я можно сказать также делал. Вот я описал своё решение http://codeforces.me/blog/entry/3899#comment-79080
Авторам за контест от меня минус.
Начало. Открываем первую задачу. Боян. Даже если не видели раньше, то очевидная. Ну ладно, это первая, так и должно быть. И код коротенький:) Открываем вторую. Опять боян? Ну ладно, нам то что, пишем. Еще и ступил, не вписал один из случаев, лишний сабмит делал. Смотрим третью... Условие длинное, давайте четвертую. Ок, четвертая дп наверное, надо подумать, как сложность срезать хотя бы до "быстрых n^4", а пока что раз третья только 1000 стоит, то попробуем третью сначала. Прочел третью. Кое-как вкурил условие. Понадобился еще вопрос жюри, чтоб понять, есть ли глубокий смысл в том, что буква c обозначает 2 переменные в условии. Как оказалось, "_Нет, буквы совпадают случайно._". Ок, наконец-то понял условие. Хм. Опять боян?! Да не смешно уже. Ладно, сначала пишем тупизну, чтоб потом тестить правильное решение. Тут начинаются проблемы — тупизна не проходит пример. Тестим, рисуем, дебаг-оутпутим... Не помогает. Тут и клар попал в глаза... Как бы "извините, Вы решаете не то...". Подумал... Так ведь условие не меняется :D Только оценочную функцию переделать. Ок, тупизна запахала, сел писать норм решение. Правда, убил 40 минут на написание кода, который где-то слетал, забил и пошел содрать готовое с e-maxx (я уже употреблял слово "боян" в этом сообщении?).
А я не почувствовала боянистости ни в одной из задач.
Первую задачу в немного другой формулировке (но задача та же... если дописать к решению сегодняшней работу с мультитестами, то должно проходить) видел на каких-то китайцах. С учетом того, что китайцев много, и у каждого свой личный АСМ-архив на пару тысяч задач, то вряд ли я смогу ее найти и показать за разумное время, поэтому обвинение с моей стороны не сильно обоснованное. Третья... Считаю, что все, что разобрано на e-maxx — или "алгоритмы, которые надо знать", или "очень популярные задачи". В сегодняшней задаче отклонение от задачи с е-макса было только в понятии "матожидание", которое в 2 строки кода сводило задачу к выше указанной. Я понимаю, что задачи в явном виде, наверное, не гуглились:) :)
Довольно правильно было подмечено ниже, халяву боянами называть не совсем верно. Но халява для каждого своя. Я думаю, что понятие "халявы" для Гены и для среднестатистического "фиолетового Васи" сильно отличается. Если для Натальи или кого-то еще эти задачи сравнительно простые, то, может быть, такое даже и не запоминается на контестах... Или что-то в этом духе. Я от уровня финалов мира пока ниже не то что на несколько ступенек, а, скажем так, на 2-3 этажа:) Поэтому мне над таким думать приходится, и я запоминаю...
По-моему задачи как раз вполне адекватные.
Но вот подготовка...
Я один не нашёл, где здесь боян? Для вас любая задача, которая сводится к нетривиальному дереву отрезков (которое вы и то скатали с e-maxx) боян? А называть халяву A и B боянами глупо. Халява должна писаться по пять минут каждая и забываться.
Я считаю что Е мердж двух задач которые уже были по стопятсот раз. В частности это задача quality с IOI-2010 и race с этого IOI (и еще штук 8 за этот год). Если конечно имелся ввиду Nlog3. А в чем смысл задачи, которая в таком случае придумывается за 3 минуты и не пишется в формате 2-хчасового контеста я не понимаю.
Это другой вопрос :-) К тому же человек, которому я отвечал, про E ни слова не говорил, а выдвигал претензии к другим задачам.
Я бы не сказал что все эти задачи были 100500 раз, но согласен что каждая из идей по отдельности встречалась.
Я посмотрел ваш разбор. Разделяй и властвуй решение действительно я сходу только на сборах помню. А то что медиана сводится к сумме бинпоиском... ну реально много раз было.
Problems were nice.
I think each contestant should be able to decide if their rating is updated for this round.
lolwut? A round should be rated or unrated for ALL. If not our ratings would become inflated and meaningless.
This has been done before. I guess that'll make everyone happy at least.
Neither of them are good reasons to do such thing. I think frank44 is right about the risk of inflating ratings if a vote becomes a habit.
I think it should be unrated for all.
And I don't think so.
There were problems with statements in D and E.
And I still don't think so.
Problem D of Div. 2 sucks when k > n.
It really doesn't. While it's a bit of a "silly" case it makes perfect sense. The requirement is that all substrings of length k should be palindromes. Since there are no substrings of length k, all strings pass. It makes perfect logical sense.
Задачи хороши, жаль, что возникла проблема в С (видимо, легенду меняли в последний момент?) Мне вот интересно, а каждый какой раунд в комментариях половина посвящена пустому множеству и его соответствию каким-либо условиям?
Я, конечно, неясно выразился. Я долю имел ввиду
Да я понял, шутка же ;-) Достаточно часто, что. Раз контестов в пять точно.
Задача С совсем не понравилась,даже если бы в ней не было ошибки. История вместе с поправкой высосана из пальца. В начале было совсем не очевидно,что кондуктор продает РОВНО 1 билет каждому пассажиру,после поправки нужно было много думать и несколько раз перечитывать условие,чтобы свести задачу к банальному подотрезку с максимальной суммой.В итоге много времени потеряно непотяно на что. Кажется,история к задаче на явную структуру данных должна все таки делать задачу более интересной или помогать понять ее математическую суть, а не наоборот прятать ее за кучей слов и нереалистичных примеров(Где вы видели чтобы кондуктор поступал подобным образом?).
В оригинальном (до поправки) условии, когда кондуктор может продать единственный билет на какой угодно участок пути [C;D] вместо участка [A;B] условие было вполне похоже на реальность. Да и решение совершенно не отличалось.
Я потратил некоторое время,решая для себя,что слова "может продать билет" означают,что может продать ровно 1 билет. В английском языке в таких случаях всегда пишут "exactly" one ticket.
Ну... Вот с этим я бы не согласился, когда решаете задачу, надо использовать, помимо всего, здравый смысл (если в условии явно не указано противоположное :D ) Я думаю, что среди участников матча очень малая доля тех, кто никогда не пользовался общественным транспортом.
В любом случае,мне кажется что это предложение требовало пояснения,(В начальном варианте-стоило добавить что билет продается ровно 1,и пассажир с билетом от C до D может быть пойман на участках от A до С или от B до D) и если бы авторы его сделали сразу возможно и бага бы не было.
Ага, главное было прочитать что (С;Д) НЕ ПОПАДАЕТ. Как я так умудрился?
Many people complained about the not working announcements before. It always says undefined whether it's a hack or announcement. It has been like that for at least 3 round. Could you please fix it.
Добавьте в задачу A (div. 1) тест
9316358251200. Это число с очень большим количеством делителей.Я сломал NALP на тесте
6599669076000(сейчас это 29-ый тест), но9316358251200посерьезнее.И вообще это решение проходит все тесты, кроме 29-го: 1197803.
Также можно добавить
6746328388800и8995104518400.Интересно как.. а я придумал, что надо искать 2 раза мин. делитель от 2 до корня из 10^13. Меня такие тесты не пугают :)
Ну вот, к примеру, мое решение, точно такое же, но с удачно поставленными break-ами: 1188543. Если их не поставить, вычислений будет слишком много, т.к. делителей слишком много.
Я вообще очень удивился, когда увидел, что в моей комнате всего 2 подобных решения, помимо моего. Суть такова: состояние выигрышное, если из него есть переход в проигрышное (оно и достанется сопернику). Я думал, что это пишется на автомате, сдается и забывается.
This is another contest where I've run into problems with writing solutions in Python. This time I spent AN HOUR trying to figure out why my solution for C div2 gets TLE. I didn't even care to check other problems because this one was so frustrating. After the contest, when I ran my solution locally, it turned out that on one of testcases in Codeforces environment it took 2000ms, whereas on my machine it took < 700ms. I vote for adjusting the time limits to the runtime performance of languague, in a similar manner as Codechef does. Otherwise there's no sense in allowing to write solutions in Python, knowing that it might fail, even though the same algo would run within limits in C/C++.
Choosing right language is a part of problem solving process.
I use Python for almost all problems on Codeforces, because it's often much faster to code solution in it (for example, for today's "Quantity of Strings" it has built-in modular exponentiation).
But for some problems Python is not fast enough, it's OK.
Also you can use "custom test" functionality to test execution time on the Codeforces server.
If there is going to be a voting, then count me for unrated. (I cannot keep refreshing the page , sorry, I have exam tomo.)
Very bad, that it is rated. X-(
How can you make it rated ? Problem B (div1) :: "Any its substring of length k" should have been "**All of** its substring of length k"
Could you elaborate? What's the difference in this context?
"aaaab" satisfies any substring of length 4 which is Palindrome. but does not satisfies "all" substring of length 4, since aaab is not palindrome.
Also, in the case of k > n. behavior is undefined, so it should have been clearly mentioned what to do.
By behavior being undefined, i mean to say, "any substring of length k", what of you mean by a substring of length 7 in a string of length 2 ?
You should count number of strings under the constraints mentioned in problem statement.
If k is more than n , we have n^m possible strings.
I think contest should be rated for we Div 2 because there was a problem in only E and I dont think it affected more than a 3-4 people ( only 1 person had solved before the updation of the statement at 7:47. So all of the people were doing the other problems then and I dont think anyone starts off with E especially when its 3000 UPD: And yes it is rated
хм, мне кажется в B возникает неоднозначность, что выводить при k>n: 0 или m^n Думаю надо было бы в условие об этом сказать
Победа, всё-таки rated! Пётр решил, что Гене хватит форы и начал догонять :-)
Еще одна бага контеста, напишу здесь. Уже не первое соревнование такое происходит — когда приходит сообщение о какой-нибудь ошибке в условии или еще о чем-нибудь, то в Chrome заголовок и содержимое этого сообщения отображаются как "undefined", вместо того, которое должно быть.
Я отправлял задачу C, проверил у себя на всех 53-х тестах, работает правильно, и выдает правильный ответ, но тут она даже не компилируется.Что делать?
у меня та же проблема была. отправь тоже решение на free pascal
upd кстати почему такая строчка недопустима в delphi
пробовал, пишет Comilation error, причем если вместо int64 сделать longint то она скомпилируется, но число q не влезет в этот тип уже на 7-ом тесте, хотя на компьютере работает корректно =(
хм я отправил просто под free pascal и все прошло
На Delphi нет sqrt для int64, поэтому отправлять нужно так: sqrt(q+0.0)
спасибо. не знал.
Посмотри протокол компиляции на CF. И выложи его сюда, там посмотрим.
А еще переменная-счетчик i не может быть типа int64.
Забавно, что я сегодня показал свой лучший результат на codeforces, хотя болею и температурю. Вроде бы голова ничего не соображает, а пальцы сами пишут решение :)
Вспоминая тему примерно полугодичной давности "контесты <=> алкоголь", я готов поверить, что в не самом адекватном состоянии человек может прекрасно решать контесты :)
Макс наверное температура защищает голову от неправильных мыслей))
На мой взгляд, есть вполне объективные причины, по которым раунд должен был бы быть нерейтинговым. А именно, неправильное условие в задаче С, которое было исправлено на 48 минуте контеста и о котором часть участников узнала даже не сразу после объявления, потому что вместо объявления пришел текст "undefined". Учитывая, что для div1 это задача C, которую все-таки многие пытались решать, проблема (вероятно) задела значительное количество участников.
В любом случае жду пояснений относительно рейтинговости раунда со стороны авторов или администрации.
Если такое технически осуществимо, прошу предоставить возможность каждому сохранить рейтинг от этого раунда, или признать раунд нерейтинговым.
Я с тобой совершенно согласен, но, кажется, он рейтинговый. Да в рейтинге ли дело? Это же не Yandex Open.
Мой рейтинг упал только на 3, поэтому нет, не в рейтинге. Дело в том, какую планку ставит себе Codeforces для нормального (= рейтингового) раунда.
После этой фразы, я с трудом могу найти в себе силы что-то ответить. Мне кажется авторов и администрацию можно попросить, а не
ждать в любом случае пояснений.Конечно, этот раунд не был образцовым. Администрация и авторы не имели единогласия относительно рейтинговости этого раунда. Большинством голосов было принято такое решение. Вот почему. Проблемы были более-менее только в одной задаче. Условие было быстро исправлено авторами (10-15 минут). Различие в понимании условия не принципиально меняло решение (т.е. его можно было быстро поправить на правильное понимание). Получилось досадно с undefined, но именно поэтому был добавлен бокс с информацией сверху. Один из сэмплов существенным образом использовал авторский вариант условия, что не привело к сабмитам, основанным на неправильном условии. Мы не считаем, что этот инцидент делает результаты раунда существенно нерелевантными (хотя, конечно, он повлиял на некоторых участников).
А мне кажется, что в нештатных ситуациях, повлиявших на большое количество участников, важно, чтобы жюри и авторы объяснили публично, какие решения в связи с этим были приняты и почему. Тогда в аналогичной нештатной ситуации участники будут хотя бы знать, чего ожидать. Если же, напротив, решения по нештатным ситуациям не объяснять, общий уровень доверия участников падает. Так что логично ожидать такого объяснения и логично его дать. Не то чтобы мы вас заставляли... ;)
Лично мне, кстати, была бы ещё интересна проблемсеттерская часть, если она у вас появилась и вы можете ею поделиться, что-то типа "какую дополнительную проверку можно было бы сделать, чтобы заранее найти несоответствие условия и авторских решений?" Потому что так бывает, к сожалению, далеко не только на этом раунде и не только на Codeforces.
Конечно, очень круто иметь тестера, кто все прорешает (и при этом раньше не видел задачи), когда условия на 99% готовы. Если такого человека нет, то круто хотя бы найти такого, кто просто прочитал бы все задачи и ответил координатору на контрольные вопросы по пониманию. Ну и конечно, в обоих случаях важен любой фидбек.
Например, на наших ЧФ мы активно используем второй подход, когда спец. член жюри вычитывает задачи непосредственно перед печатью (раньше он их не видел и не слышал) и я с ним довольно долго беседую по пониманию (убеждаюсь что он все правильно понял, без сложностей).
Группа Div2-авторов Gerald+Polichka+NALP работают по предложенной мне схеме — двое готовят раунд, один его прорешивает, когда он почти готов. Первый блин там был почти комом, но два других раунда проведенных ими — удались.
Конечно, Артем может пропустить какую-то тонкость, так как он один, да и работает с задачами наполовину придумывая их (т.е. фактически часто соавтор). Нам неоднократно помогали волонтеры-участники и это было очень ценно. Мы даже немного поддерживали такую помощь. Сейчас таких нет, но мы с радостью примем помощь от квалифицированных участников. Вероятно, в самом деле надо расширять тестерскую поддержку, хотя бы анонсировать, что она нам нужна. Что-то в стиле: "А ты записался в добровольцы?".
Спасибо за ответ!
Когда есть человек, чтобы прорешать всё, или хотя бы прочитать всё и обсудить с авторами, что он понял — это, конечно, огромный бонус. Но иногда приходится готовить задачи и без таких бонусов, да и на более ранней стадии, когда автор ещё один готовит свою задачу, тоже хочется иметь какие-то рецепты "более низкого уровня", чем общая организация процесса, люди и время. И соответствие условия и решения — одно из слабых мест, потому что автоматически его не проверить.
Например, во многих задачах можно написать тривиальное решение, которое делает ровно то, что написано в условии, самым простым и читаемым способом. Если такое решение в задаче есть, тот, кто вычитывает условия, может прочитать его сразу после условия и убедиться, что в нём делается ровно то, что просят, без помощи других людей.
Ещё можно при вычитывании условия разбирать примеры. Для этого составлять примеры можно так, чтобы они покрыли как можно больше случаев (классический пример: если дана прямоугольная таблица, хотя бы в одном примере количество строк должно отличаться от количества столбцов), но не слишком сложные, чтобы их можно было разобрать и понять при чтении за несколько минут. Это тоже возможно не во всех, но в очень многих задачах.
Наконец, нередко условие перестаёт соответствовать решению, когда что-то меняется в последний момент. Если это не идейное расхождение, а техническое, скажем, разные ограничения в условии и во всём остальном, может помочь памятка вида "когда вы считаете, что задача готова — проверьте эти десять пунктов".
Наверное, круто было бы организовать, записать и выложить куда-нибудь такие "технические" проблемсеттерские рецепты. Может, кто-то это уже сделал? Отзовитесь тогда!
А вам не кажется, что вы берете на себя роль бога, которого можно только просить?
Такое ощущение, что не все поняли. По пунктам.
Сообщение явно указывает на необходимость особого обращения. "не соблаговолите ли вы, сударь?"
Сообщение крайне надменно. "как вы вообще посмели?"
Сообщение содержит снисхождение "ладно, так и быть, спущусь с неба".
Сообщение содержит вырванную из контекста фразу, в которой вводная конструкция
в любом случаепреобразована в требование.Я думаю, ему можно писать и не из фейкового аккаунта.
По-моему, уж кто надменен, так это те пара личностей, недавно [недо]покинувших кодефорсес, которые почему-то решили, что это они здесь хозяева-баре...
What should the output for the following case for problem B (div2) be?
My Output is:
System answer is:
Haven't both Alex and Mula got the same number of phone numbers of each type?
Can someone please spot the issue with my output. Thanks.
Ok, I figured the issue. Thanks.
Taxi numbers consist of six identical digits. 12-12-12 isn't taxi number, that's your failGot it, thanks.
Why? Alex don't has a taxi number, but has "other" number. Both have one pizza number
Yep, I messed up the check for taxi numbers. Thanks.
No. The problem statement says, the numbers of pizza deliveries should necessarily be decreasing sequences of six different digits (for example, 98-73-21) So, 99-87-76 is a call girl number.
This was my challenge. Sorry about that!
ЧЕЕЕЕЕЕЕРТ!!! Почему я не прочитал то сообщение про задачу С? И все время не понимал почему 2й претест не заходит, думал что написали, что нельзя два отрезка брать. Кто я после этого?
forever blue
С возвращением =)
Может, стоит сменить ник и аватар?
смени
Я не голубой и не синий(где же Петросян с его намеками?)
Great :D I want that to be in unicode!
editorials from the author???
English version will appear tomorrow. Sorry for delay.
Could you please give specific examples of confusing phrases in English statements?
Aw, if you told us when we were preparing our contest months ago with your translation of statements, I would show you some places, we had fixed. But now I even don't remember what were the corrections.
I think it's good practise to give someone English statements before the contest, so he could fix confusing phrases with you (or with one, who translates statements).
I usually have a look at the corrections applied to my translations after a contest so don't worry, the odds are I didn't miss those ones!
Your idea is great but first, sharing problem statements before the contest might be against the Codeforces rules and second, I actually do check the phrases that seem confusing to me. What I'd like to know is what the programmers find confusing...
Incidentally, do you know anybody who translates statements? I know only one linguist apart from me... Thanks for the sound advice!
Upsolving the contest after 9 years, still couldn't get what Div. 1 C is asking until I read the comments.
No, I still don't understand what should I calculate.