Здравствуйте!
Приглашаем Вас принять участие в сегодняшнем раунде. Надеюсь, каждый найдет интересные для него задачи. И этот раунд понравится большинству участников так же, как и предыдущий.
Сегодняшний контест для вас подготовила команда SPb SU 4 (Alex-Gran (Александр Грановский), Dmitry_Egorov (Дмитрий Егоров), PavelKunyavskiy (Павел Кунявский)). После долгих раздумий из названия команды можно догадаться, что мы представляем Санкт-Петербургский Государственный Университет. Куда более очевидно, что мы все трое учимся на первом курсе математико-механического факультета.
Большое спасибо за помощь в подготовке задач Артёму Рахову (RAD), Геральду Агапову (Gerald) и Марии Беловой (Delinur) за перевод задач. Также большое спасибо Пете Калинину (KAP) за вычитку условий.
В сегодняшем контесте вас ждет 7 задач (по 5 в каждом дивизионе) про страну, в которой живут волшебники, и, как следствие, происходит много интересных событий. Вам предстоит поучаствовать в местных митингах, разобраться в тонкостях написания заклинаний, прокатиться на волшебных видах транспорта, попытаться унести магические призы, поиграть в любимую игру волшебников, помочь магическому правительству в управлении страной, а также свернуть шизофреническую сумму разрешить финансовый спор двух прославленных магов.
Разбалловка задач сегодня стандартная в обоих дивизионах. Хочу заметить, что стандартная — это 500-1000-1500-2000-2500, а не как обычно :).
UPD: Опубликован разбор.
Поздравляем победителей!
Div. 1
rng_58
Справившихся с 4 задачами, на этом непростом контесте. Отдельные поздравления от меня Endagorion al13n справившимся с задачей D.
Div. 2
Всем удачи!
" Куда более очевидно, что мы все трое учимся на первом курсе математико-механического факультета."-Вы же школьники!
Ваша информация устарела на пол года.
Школьники из СПбГУ, да.
Ну, мы в Петрозаводске/Харькове назывались в этом году SPb SU Belka_Strelka_Koleso и ничего. Впрочем, уже не все школьники.
То есть стоимость задач не динамическая и задачи отсортированы по возрастанию сложности?
Задачи отсортированы по возрастанию сложности с точки зрения авторов. Как всегда рекомендуется прочитать все задачи.
After a long time both there is a contest for both divisions. I really liked the previous one which had rated the problems dynamically.
Отдельный плюс за фразу
стандартная разбалловка, а не как обычно.
Надеемся, что легенды вам понравятся не меньше, да и сами задачи тоже)
А я так надеялся на див-1 раунд с динамической стоимостью :(
Будем ждать.
so,just fight!
Всем неудачи?
Разбалловка стандартная, а будет ли традиционно D самая простая в контесте? :)
Задачи отсортированы по возрастанию сложности с точки зрения авторов. Как всегда рекомендуется прочитать все задачи.
А. Вот такой вопрос. С какой скоростью будут поступать ответы на вопросы?
Как успеем, так ответим =) Надеемся что почти сразу.
Особенно хотелось бы пожелать удачи всем тем, кто сидит в КБТУ, включая авторов
Авторы не в KBTU, хотя и не далеко.
ну и ладно, Madiyar'у и azizkhan'у тоже нужна удача
One more comment.
"В первом примере, чтобы увеCти..."
"Найдите, с какой вероятностью вы выступите на сборах хорошо, но при этом сможете увеЗти все призы (то есть все выигранные здоровенные призы можно будет поместить в выигранные и привезенные сумки)."
This may be a silly question at this point but — how do I ask for clarifications? (if there is such thing)
Ask a question link on problems tab
лучше бы поспал
Задача С крутая, спасибо)
Как решать-то?
У меня таки получилось найти период кажется за 5 минут до конца. Задача действительно крутая.
Замечаем что после любой операции GCD чисел не меняется. Если рассмотрим более подробно, выйдет, что мы не можем обойти ни одной ситуации, которая получается в процессе вычисления GCD Евклидом.
Соответсвенно вычисляем оценку ситуации по этим этапам. Грубо говоря, у нас есть участок из x этапов, и мы можем пройти за ход a^0, a^1, a^2, ... или все х этапы. Соответственно, если предыдущий этап был проигрышный, этот — выйгрышный (за 1 ход проходим всё).
Если предыдущий был выйгрышный, то мы никогда не хотим использовать опцию брать все. До 1000 с брутом совпадает, что в таком случае, если в GCD мы отнимаем по y, то тогда оценка такой ситуации — выйгрыш, если x mod (y + 1) чёт, проигрыш, если нечёт.
Доказательства этого нет (может это вообще неправда), если у кого-то есть, буду рад услышать.
Для нечетных y легко понять, что достаточно чтобы x/y было четно (потому что четность x/y меняется каждый ход)
Для четного -- в конце остаток на (y+1) равен нулю, то есть четен, и это выигрышная позиция. Докажем, что нечетный остаток -- это проигрышная позиция.
Если сейчас остаток четный -- его всегда можно сделать нечетным, сделав -1, если остаток не 0. и -y, если он ноль.
Если сейчас остаток нечетный, то любой ход его сделает четным -- это легко показать для хода в -1, остальные легко доказываются по индукцти (пусть мы доказали, что y^k меняет четность, также очевидно, что y^k * (y+1) не меняет четность, потому что делится на y+1, отсюда y^(k+1) = y^k * (y+1) — y^k очевидно меняет четность).
На чём ломали?
Динамика с map< pair<long long, long long>, int> в С проходила претесты ))
Претесты в С — это квадратик [0,7]x[0,7] + что-то несодержательное большое для проверки лонгов.
Ощущение "где-то видел, решения не помню". Попытался вывести, начал тупить... Забил, написал жадность, и по результатам жадности внезапно вспомнил и какое решение, и как выводить правильно, и где видел:)
Да, задача отличная.
Вообще набор хороший. По крайней мере, первые три, последние две оценить не могу.
Ага. 80 минут ее решал, когда решил наконец, решил забить на раунд пока не поздно :)
Очень интересно, как это придумали люди — у меня получилось только методом внимательного всматривания в ответы и только за час :) Там какое-то простое соображение, или хотя бы какое-то простое доказательство?
Не знаю уж, что вы там увидели. Решение несложно доказывается по индукции, если свести к чему-то нимоподобному.
Можно на "ты" :) Я про решение подзадачи, когда есть ним с одной кучей и можно брать степени b. Доказательство AlexSkidanov выше уже прочитал, и правда просто. Остался второй вопрос — откуда может прийти в голову что важна четность остатка от деления на b+1 :)
Золотое правило — если не выходит придумать строгое аналитическое решение, надо быстро писать брут и искать закономерность:)
Ну я так и сделал, но вот закономерность увидел небыстро. Может если бы выписал для b=2 а не b=10 было бы легче и правда :)
Да, давайте учить Петра решать задачи)
Я так и сделал, мне не помогло. Потом я решил подумать и у меня все срослось.
Зависимость от четности достаточно очевидна. Осталось посмотреть, что будет происходить в местах где появляются новые ходы.
Сорри, что все еще не допираю. Новые ходы ведь появляются во всех местах начиная с b?.. Или ты имеешь в виду, что нужно посмотреть, что b+1 проигрышная, дальше понять, что тогда до 2b+1 опять будет чередование, потом опять две проигрышных, и так далее, а потом заметить что прыжки на b^2 и больше ничего не меняют? Пожалуй, да, так можно было сделать :)
Интересно, какое соотношение тех, кто так сделал и тех, кто увидел закономерность в ответах :)
Лично я решал честно. Но думаю большинство увидили закономерность.
Эх, я вот увидел закономерность, закодил, остается 2 минуты до конца и оказывается, что для четных a все же неправильно увидел. Времени исправить не было уже.
UPD: Сел за тот комп, с которого решал раунд, за 5 минут поправил код и сдал. Печаль.
Читер :)
На самом деле доказывается очень просто — почему четная выигрышная — потому что из почти всех можно сходить -1 в проигрышную, а из делящегося на a + 1 можно вычесть a и попасть в проигрышную (остаток 1). А из проигрышной мы либо увеличиваем остаток на 1, либо уменьшаем на 1 — то есть попадаем в выигрышную. Если бы я сразу допер написать для a = 2 на бумажке ответы, то сдал бы ее моментально
Ну, я сказал, что a ≤ b, что позиция (
, a) — выигрышная (иначе очевидно) и разложил b в a-ичную систему счисления (не подумав сначала про переносы). После чего осталось что-то нимоподобное, что разбилось отдельно для чётных и нечётных a a внимательным взглядом на ответы до 50.
У меня все было ровно так же до момента внимательного взгляда, ага. Надо его прокачивать, похоже :)
Спасибо авторам за то что обозначили здоровенный приз как -1 ^_^
давно такого ГРебаного раунда не было, не считаете?
а ничего что ты его не писал?
очередной фэйк.
ну да, минусуй меня со всех своих аккаунтов.
вкладодрочер детектед? и я вас не минусовал
да по монитору видно, задачи открыл — 1я нездоровая для 1й, 2я — можно сказать норм, а остальные гробы, не находите?
авторам не кажется, что с принципом "я знаю как решать эту задачу — поэтому она простая" немного переборщили?
Ну как сказать... На вкус и цвет... Сегодня вот я идеально попал в проблемсет. Т.е. весь контест мне было что решать. За это авторам плюс. Обычно после первого часа халва заканчивается, остаются гробы, которые мне не осилить:)
По Вашей логике, сложный раунд == плохой раунд?
Такого принципа не было. Изначально планировалось, что в этот раз нужно будет больше думать, чем писать. Вроде так и вышло.
Единственное, с чем я пожалуй соглашусь, что D сложнее, чем обычно. Остальные задачи адекватной сложности.
Давно не было раунда, про который бы ты сказал, что он не ГРебаный.
почему, никогда на про кф раунды такого не говорил (к тс у меня вообще неприязнь), предыдущие раундов 5 (или 6-7) были нормальными добротными раундами
То-то вы их не решали.
The problems were as if I was sitting in my English examination to read comprehensions...
Расскажите как решать C(div2), чувствую моя реализация не пройдет.
для каждого считаем за сколько бы времени он прошёл расстояние d если бы ему никто не мешал. сравниваем с максимальным временем прохождения этого пути на данный момент. ну и дальше понятно что если посчитанное время больше то выводим посчитанное и обновляем максимальное, а если нет то выводим максимальное.
Ну я также делал. Буду молиться :)
по моему очевидно что правда. проблема может быть только с точностью.
Посмотрим :) Пока, что будем ждать сис.тестов! :)
у меня (да и не только) упало на 15 тесте... пичаль
Я перед проходом по трамваям сортировал их по скорости если они выходили в одно и то же время
0 10
0 15
0 20
Стало:
0 20
0 15
0 10
Может быть именно поэтому у меня и прошло...
А вот с Б я облажался :(
Они не могут выходить одновременно — по условию. Я тоже засомневался, что делать, если они выходят одновременно, задал вопрос жюри, и мне ответили цитатой из условия, за что им большое спасибо.
Ну а я как обычно ужасно хотел спать :) Ещё курсовую доделывать :(
Ну тем не менее 800 мс :)
А я по скорости не сортировал, если они выходили в одно и то же время, т.к. по условию времена разные: 0 ≤ t1 < t2... < tn-1 < tn ≤ 10^6
у меня не прошло из за того что double переполнился и ушёл в минус заменил строчку (v*v)/(2*a) на (v/(2*a))*v и все прошло
Помню на одном из прошлых контестов меня взломали на том, что перемножал int'ы и они переполнялись :(
В смысле
int t = 1e9, z = 1e9;
long long d = t*z; :(
не пугай так, у тебя переполнился (long)int, а не double
Хороший раунд)) Думаю, скоро таких комментов будет много.
как решались D и Е в div. 2 или, соответственно, B и С в div. 1?
На чем можно было свалить трехмерную динамику на В? Там какой-то частный случай? Массивы вроде достаточных размеров сделал
Отриц.индекс не делаешь?
Имеешь в виду отриц индекс для кол-ва места в сумках? делаю...
if(j + d[z] >= 0 && j + d[z] < 401) — получилось, что больше 2ух сумок вместительностью 200 алгоритм заведомо не возмёт, даже если у них вероятность 100%.
Спасибо, теперь понял, я дибил)
Э-эх, 10 секунд не хватило сдать задачу
Это было самое обфусцированное определение декартова дерева из всех, что я видел :)
+1. =)
Я старался. Жаль, что его увидили так мало людей.
Даже после фразы, что это декартово дерево, я его не вижу. Обфускация что надо:) Надеюсь будет разбор и я в нём разберусь:)
**UPD:** Пока писал разбор появился:) Теперь понятно, почему это декартово дерево, но сам бы я до этого о-очень нескоро додумался.
**Спасибо за хорошие задачи!**
Уже есть же.
It should be 500 1500 1500 2000 2500 in Div 2
maybe 500 1000 1000 2500 2500?))
the 4rd problem is too hard to read>_< i can not analyse the samples >_<
4th, not 4rd.
maybe 2500 2500 500 500 500? why not? //sarcasm
D(Div 2) / B(Div 1)
Я вот так и не понял почему в 1 тесте нельзя выиграть все 3 тура? :(
Где написано, что нельзя? Можно же.
В первом примере, чтобы увезти все призы необходимо либо ничего не выиграть, либо выиграть третий тур.
про выиграть все ничего не сказано...
Выиграть третий тур != проиграть первые два.
Понятие "выиграть всё" входит в "выиграть третий тур" т.к. если выиграем всё, то третий тур в том числе.
да... туплю (
Я так понял либо ты выигрываешь 3ий с вероятностью 30 % либо все 3 с вероятностью 0.6 %.
Ну и выбирается соответственно случай с наибольшей вероятностью ...
вероятность выиграть все три равна 0.1 * 0.2 * 0.3, вероятность выиграть только третий равна (1 — 0.1) * (1 — 0.2) * 0.3
Значит неправильно понял задачу :(
можно. обязательно выиграть хоть один тур. Если третий тур проигрываем, то не сможем нигде взять сумки, чтобы увести призы. Значит 3-ий тур надо выиграть. а дальше уже неважно какие туры будем выигрывать/проигрывать всёравно нам хватит сумок, чтобы увести все призы. 0.3*1=0.3
Wizards and Huge Prize i think this problem is too hard to read. at first, it said it want to win all the prizes, but last it said, it want to take all the prize won......
i have read for a long time, but also can not understand the sample >_<
Не сдал задачу Д из-за следующей строки
FAIL=(
А warning на неиспользуемую переменную?
C -Wall нету warning-a=(
-Wextra есть
У меня и с ним нету, может я что-то не так делаю?
Надо ещё и оптимизацию включить (
-O2, например).Не помогает
Мне тут пояснили, что если я ЧИТАЮ переменную, но больше ее нигде не использую, то с++ считает, что она сильно используемая, и warning-а не кидает
А если сделать ее локальной, будет warning?
Если локальная, то тот же эффект, я же ее все равно считываю. А на Java кидает warning?
Если читать printf, то переменная передается по значению — и кто же ее знает, что этот злобный printf с ней делает?
В Java если переменной только присваивали значение, то она будет подсвечена в Intellij Idea серым цветом
На джаве переменную можно присвоить только явным присваиванием, и при этом будет понятно, что переменная не используется. Такое не скомпилится.
Скомпилится, конечно. Неиспользуемая переменная не повод для ошибки компиляции, вот использование значения переменной, которая до этого не во всех ветвях была инициализирована — это да
А сравнить то, что получается со вторым сэмплом?
Ну так я и сделал за 30 сек до конца контеста...
My screencast will be here shortly
Not very eventful through as I spent most of my time with pen and paper ;)
Why can you test the sample testcases so fast? That's amazing!
they are parsed and auto tested by CHelper
For Java check this
There are some tools to parse tests for other languages, cannot easily locate them through
what will happen if try to access the index which is not allocated. By default what is stored in it ( here in C++ ) ? http://www.codeforces.com/contest/168/submission/1429535
Почему так затягивается системное тестирование?
В конце контеста, система не совсем корректно обработала два взлома. Сейчас разбираемся.
When are the system test starting???
Вот вы мне поясните почему, в задаче B div 2 из авторских примеров не видно что там нужен хвостовой перевод строки?
Не оно?
Прописано то оно прописано, но когда я получаю wa1 при этом посимвольное сравнение с авторским аутпутом показывает что все норм. Почему было не сделать еще один перевод в выходных данных?
Как минимум потому, что это пустое место на странице будет вызывать ещё больше вопросов.
И мы на все честно отвечали.
Ага, "Без комментариев"
в условии прописано
Problem B div1, is a simple dynamic programming, but the Hardest part of problem was undrestanding of that (at least for me). However with help of writers I got that finally.
at last. i also cant not understand the problem。。。。。。it is too .........
Задача Б , див 2. Выходные данные: "Выведите программу, из которой удалены все лишние символы..."
До сих пор ломаю бошку над тем , правильно ли это сказано. Подскажите, разве такое возможно?
Извиняюсь, осталось от старой версии условия. Не уследили.
Ясно. Бывает.
у меня сложилась такая ситуация: задал вопрос, сначала мне ответили — читайте условия, а под конец контеста ответ исправили и дали развернутый ответ, хотел бы узанть, как происходит ответ на вопрос участников? вопрос перескатривают несколько раз?
Ответил я подробно минут через 5. Просто отвечает несколько человек, и они иногда затирают друг друга.
ну да, видимо через 5 минут, просто посмотрел вконце(
P.S. вы довольно любезны, однако) на любом другом соревновании ответили бы "без комментариев"
Я один такой выделился? В первой поленился вытащить из формулы явно время, для нахождения пути до точки максимальной скорости заюзал бинарку, и в результате ТЛ:)
Если честно предполагалось что проходит все что угодно.
у меня там еще cin cout... И точность бинарки немного великовата... Короче говоря, я постарался)
not syncing with stdio спасет отца русской демократии
Ты бы тогда хоть eps побольше бы поставил)
После В с недавнего раунда VKcup меня пугают большие eps-ы )
P.S. А банальное уменьшение точности, всего лишь с 1е-8 до 1е-6 дало АС 1.98...
Вы все еще юзаете бинпоиск по епсу?
Тогда мы идем к вам
Кажется не надо было в В значения меньшие 1E-9 считать 0...
Мне удалось завалить только одно 1E-7 в своей комнате.
Но динамику написать можно по-разному, да и тесты, вероятно, бывают получше =) .
В тестесете были специально сделанные мной тесты с ответами около 2*10^-6, которые еще к тому же набирались по большей части как раз такими эпсилонами.
С одной стороны обидно зафэйлить раунд из-за этого. С другой стороны, каждый новый вид фэйла, на котором ещё не грохался, очень поучителен. Приучился сразу как даблы, везде пихать эпсилоны — сегодня огрёб. :) Так что спасибо.
Сложный раунд. Если не слоупочить с A и B, можно было бы на 100 мест выше быть.
GREAT PROBLEMS
почему вот этот код 1429288 не проходит 1 претест в B(div2) задаче...вернее почему его оутпут отличается от того что я получаю если использовать запуск...никак немогу понять...
Вы ставите в запуске заключительный перевод строки?
Вы читаете последнюю строку. Все делаете. Далее у вас неверно что eof ибо вы еще не считали eof. Далее Пытаетесь читать, не читается, в строке остается то же самое. И вы выводите. Без последнего переноса такой проблемы нет, т.к вы сразу получаете eof
как вообще такое может быть чтобы double переполнился.. (v*v)/(2*a) вот эта строчка возвращает на одном из тестов отрицательное число. я предполагаю это переполнение (v/(2*a))*v а вот с этой строчкой получаю полное решение кто-нибудь мне может объяснить этот феномен?
v — int => v*v int потом чтобы поделить на 2*a уже может быть кастуется к даблу(если а дабл) или в твоем зыке делится в даблах
а ну да.. я дурак. спасибо. понял.
Можете указать на ошибку в моем решении задачи 168B - Волшебники и минимальное заклинание — 1426806, если она там есть, так как сейчас в Custom Test'e этот же код выдает верный ответ на 3 тест..
UPD Уже сам понял.
Это ж надо таким неудачником быть... B (div 1) упала на 89-ом тесте... Можете выложить его содержание?
Большие тесты — это все взломы. и 83 и 85 тоже. Думаю их уже скоро можно будет псмотреть в системе.
А как это сделать? Я только префикс теста вижу на странице своего решения
Да. не повезло. 83 и 85 на которых массово падали были маленькими.
А вы доступ к тестам имеете? Можете выложить его, а то очень уж интересно, где баг
Today I learned that in Java StringBuffer is much faster than String .In Div-2 ,Prob B My solution in which i concatenate two Strings give TLE while just replacing the String with StringBuffer gives accepted in this code,and that too in 330 ms. :)
and StingBuilder is even faster coz StringBuffer uses StringBulder.
It's necessary to know all language features if you write in it. Code
, after compilation and decompilation, transforms into
which works in O(length(s)+length(t))
I wonder why updating ratings takes so long.
I'm too. I'm waiting for RAD or Gerald.
update the ratings is longer than the contest it self
Honestly, I think the rating formula should be modified after seeing tourist got -1 rating for his 2nd place.
However, his rating is much higher than anyone who participated the contest.
Despite that fact (and 5 of top 10 coders didn't compete), I suppose his rating would gain 5-10. It seems tough to participate in a win-or-minus-rating round, even if he is the best.
Take a look at Topcoder, I find that there are about 600 coders with rating 1800 or higher, while that number in Codeforces is 1000. I know that it isn't necessary for Codeforces to be compared with Topcoder or something else, but above numbers probably show some "rating inflation".
Moreover, i'll like to add one more thing......the rating limit separating Div 2 and Div 1(at Present it is 1700) Should be Decreased to 1600 or 1650 at least....bcoz a coder at 1600+ is capable enough....and for him solving Div2 A and B solving is not fun, as they really very simple and implementing them is really a time waste for him(approx 30-40 mins wasted for solving first 2 problems on average)......and hence he able to give comparatively less time for problem C and D.
Instead it would be better if he can start from Div2 C which is Div 1 A.....i think this will avoid time waste for that user and he will evolve faster while competing in Div !.
Other Suggestions are welcomed..
> they really very simple
> approx 30-40 mins wasted for solving first 2 problems on average
А будут ли в ближайшее время изменены рейтинги? А то стою перед выбором, лечь спать или ждать обновления рейтингов.
Уважаемая администрация, найдите, пожалуйста, хотя бы одного читера среди участников, занявших места с 1 по 35 =)
Думаю, перенести границу красного цвета до 2199 очков проще:)
Можно, в принципе, и после 35...
Геннадий получил за 2 место здоровенный приз)
Несправедливо как-то немного) или это чтобы не расслаблялся?)
Думаю, это потому что участников было меньше, чем обычно. Но всёравно неприятно, наверное.
Что происходит с таблицами результатов? Все времена посылок обнулились.
Я уже написал MikeMirzayanov в личку. Будем надеяться, что в ближайшем времени исправят.
It was a very interesting round with good problems......I think the author is very fond of mathematical problems(my rating goes up yahooooooooo).......however the problem statement of B(Div 1) was not very clear to me and I think for many others........I guessed that participant can take the tours in any order and coded accordingly and got accepted....still I m confused what it says......anyway hoping for a better problem description in future contests.....
YOU Must'nt study hard nowadays because you are champion.:......:::::))))))))))))))[ this question is very hard you can try it you must beliave yourself; [problem:177E][Your text to link here...](http://[email protected])
Please can anyone tell me why this happened ? I could remove TLE in Div1 A after I replaced
cout.precision(10) ; for(int i = 1 ; i < n ; ++i){cout << ans << "\n" ; }with
for(int i = 1 ; i < n ; ++i){printf("%.6lf\n",ans) ; }Is printing after using cout.precision slow ?
it is well-known fact that
printfis much faster thancout.Also, try
ios_base::sync_with_stdio(false), it makescoutgo much faster than usual.Moreover, you have different precision in cout and printf! Program with small output size is faster than the same program with large output size =)
In case anybody is looking for the tutorial, it can be found here: http://codeforces.net/blog/entry/4214