Задача A. Покупка велосипеда.
Идея: Виталий Аксёнов.
Реализация: Дмитрий Филиппов.
Разбор: Дмитрий Филиппов.
По условию задачи нужно сказать, можно ли по данным числам a, b, c найти такие числа a1, b1, что a1 ≤ a, b1 ≤ b и a1 + 2 · b1 = c.
Решение у этой задачи простое: почти всегда достаточно проверить, что суммарный номинал наших монет не меньше c: a + 2 · b ≥ c. Исключение — когда c нечётное. Тогда ещё нужно проверить, что a ≥ 1.
Задача B. Цифровые корни.
Идея: Григорий Шовкопляс.Реализация: Григорий Шовкопляс.
Разбор: Григорий Шовкопляс.
В этой задаче нужно по числам a и b определить, какие из значений цифрового корня встретятся на этом отрезке наибольшее количество раз.
Заметим, что у цифрового всего девять значений, а также они циклически повторяются. Таким образом, нужно вычислить только цифровые корни от a и b, а чаще всего встречаются цифры между значениями этих цифровых корней. Единственное, что нужно было дополнительно учесть — это случай, когда цифровой корень a больше чем цифровой корень b. Также нужно было не забыть, что ответ нужно выводить по возрастанию.
Задача C. Две улитки.
Идея: Дмитрий Филиппов.Реализация: Николай Ведерников.
Разбор: Николай Ведерников.
В этой задаче две улитки днём поднимаются на ai, а ночью опускаются на bi. Требуется определить, сколько по времени первая улитка обгоняла вторую.
Задача решается моделированием. Рассматриваем часы последовательно. Для начала узнаем сейчас день или ночь. Посмотрим положение улиток до начала этого часа и после. Если до начала часа одна была выше другой, а после окончания часа, также была выше, то обгона не было. Тогда, если выше была первая, то к ответу добавим один час. Если же в начале часа была выше, а потом ниже, следовательно одна обогнала другую. Для того, чтобы узнать время, когда одна обгонит другую, надо посчитать расстояния между ними и поделить на разницу скоростей. После этого добавить к ответу время, в когда первая улитка была выше второй в этот час.
Задача D. Игровые автоматы.
Идея: Анна Малова.Реализация: Виталий Аксёнов.
Разбор: Виталий Аксёнов.
Нам даны кнопки, которые умеют выключать какой-то набор из лампочек, и кнопки, которые умеют включать какой-то набор лампочек. Задача: с помощью кнопок перевести лампочки из выключенного состояния в заданнное, или сообщить, что такое сделать нельзя.
Сначала, поймём, что дважды нажимать одну и ту же кнопку не имеет смысла, так как мы всегда можем оставить только последнее её нажатие, и конечное состояние не изменится. Далее, рассмотрим задачу с конца. У каждой лампочки будет три состояния: включена, выключена и неизвестно. Когда мы обращаем нажатие кнопки, помечаем все лампочки, за которые она отвечала, что их состояние неизвестно.
Мы могли нажимать кнопку, если:
- кнопка выключает лампочки, то состояния изменённых лампочек должны быть или выключены, или неизвестны;
- кнопка включает лампочки, то состояния изменённых лампочек должны быть или включены, или неизвестны.
Смотрим на последнее состояние, и нажимаем кнопки, каждую по одному разу, если это возможно. Пусть ни одну кнопку нажать нельзя, то нужно проверить, правда ли лампочки или выключены, или неизвестны, что соответствует стартовому состоянию. Если правда, мы можем последовательностью нажатий перейти в заданное состояние, иначе — нельзя.
Задача E. Интернетопровод.
Идея: Виталий Аксёнов.
Реализация: Илья Збань.
Разбор: Илья Збань.
В задаче дано n точек, и нужно найти некоторую прямую l и расстояние d такие, что количество точек, расположенных ровно на расстоянии d от прямой l было максимально.
Любая прямая задается тройкой коэффициентов a, b и c таких, что ax+by+c=0. Две прямые (a1, b1, c1) и (a2, b2, c2) параллельны, если коллинеарны векторы (a1, b1) и (a2, b2).
Проведем прямые через все пары точек, и приведем их к нормальному виду: GCD(a, b)=1, и a>0 или a=0 и b>0. Такое представление единственно для любой прямой. Перебрав все прямые, проходящие через пару точек, мы получим все углы, под которыми есть смысл проводить прямую-ответ (в случае, когда ответ больше двух, какие-то две точки из ответа будут лежать на одной прямой). Зная угол, под которым проходит прямая-ответ, несложно указать оптимальное d: для фиксированных a, b, задающих угол наклона прямой, нужно выбрать два самых часто встречаемых с этими значениями a, b значения c, и мы получим две прямые, параллельные искомой, находящиеся от нее на расстоянии d. В случае, если такое значение c всего одно, то, если не все точки лежат на одной прямой, можно добавить к ответу еще одну точку.
Just take a look at this post: http://codeforces.me/blog/entry/18265
После публикации архивов жюри в проверяющей программе к задаче D был обнаружен баг. Архив на сайте обновлен.
Мы провели перетестирование всех решений с исправленным багом в проверяющей программе. В результате у 8 человек, у которых эта задача была сдана, при правильном чекере она бы не прошла.
Из этих участников 5 человек проходят квалификацию как с задачей D, так и без нее, 2 человека не проходили до перетестирования, не проходят и после.
Один из участников после перетестирования перестал бы проходить квалификацию. Заметим, что от того, что он поднялся, никто не пострадал — сейчас проходят трое поделивших 200-202 место, если бы этого участника не было, проходили бы те же трое, поделивших 199-201 место.
Конечно, нечестно проводить перетестирование после конца раунда — если бы участник получил WA на контесте, у него был бы шанс исправить. Поэтому мы приняли решение не менять официальные результаты.
Жюри приносит извинения участникам за ошибку в проверяющей программе.
=(
Не могу удержаться: разбор не выдерживает никакой критики. В половине задач (прежде всего, в D и E), если ты сам задачу не решил, совершенно непонятно, что надо сделать. Корректность тоже почти нигде не объяснена, про ассимптотику нигде нет ни слова. Словом, скажем честно, это не разбор, а так, отмазка. Чтобы участники не ныли "ну где же разбор?".
Ладно, напишу здесь тоже: аССимптотику.
Не знаю, о чем вы.
Вашу критику выдержал.
Общая суть такая: разбор каждой из этих задач выглядит так, как будто автор разбора пытается убедить нас, решивших эти задачи, что он тоже их решил. Тому, кто задачи не решил, будет ничего не понятно.
Задача А: "Правильная формула вот такая." А почему она такая? Я понимаю, что авторам это и так понятно, но тем, кто эту задачу не решил, это, очевидно, непонятно. Но нужды этих участников, видимо, никого не интересуют.
Задача В: "Заметим, что у цифрового всего девять значений, а также они циклически повторяются." — а почему они циклически повторяются? Это ничуть не очевидно, если не вспоминать про остатки и признак делимости на 9. А если вспомнить, то почему было не написать об этом в разборе?
"... цифровые корни от a и b, а чаще всего встречаются цифры между значениями этих цифровых корней" -- а это почему? Это тоже очевидно только тем, кто разобрался в ситуации и, значит, скорее всего, решил задачу.
Задача С: Вот здесь уже стоило посчитать асимптотику и убедиться, что подходит простое моделирование ситуации безо всякий оптимизаций.
"Для начала узнаем сейчас день или ночь." — зачем? Дальше день или ночь не упоминается. Да, это понятно, что это нужно, чтобы понять, как в этот час двигаются улитки, но почему этого не сказано?
Задача D: "Далее, рассмотрим задачу с конца." -- после этой фразы должно было быть рассмотрение задачи с конца, а не сразу описание решения.
"У каждой лампочки будет три состояния: включена, выключена и неизвестно." — и что означают эти состояния? В какой момент и после (или перед?) каких действий она включена, выключена или неизвестна?
"Когда мы обращаем нажатие кнопку, помечаем все лампочки, которые изменили состояние, что их состояние неизвестно." — в силу отсутствия пояснений к тому, какие состояния что означают эту фразу тоже трудно понять, непонятно, что вообще означает, что лампочка изменала своё состояние. Например, если была неизвестна, а теперь выключена, значит, изменила или нет? Она ведь неизвестна, а значит, мы не знаем, изменила или нет.
"Смотрим на последнее состояние, и нажимаем кнопки, каждую по одному разу, если это возможно." — какое последнее состояние? И конечно, возможно. Все кнопки можно нажать, разве нет? "лампочки или выключены, или неизвестны, что соответствует стартовому состоянию" — казалось бы, в условии написано, что в стартовом состоянии все выключены.
Ну и в этой задаче уж точно нужен был подсчёт асимптотики, а для этого надо было указать хоть какие-то подробности реализации, как и что мы делаем.
Задача Е: "Перебрав все прямые, проходящие через пару точек," — то есть, для каждой пары точек перебираем все прямые, которые проходят через эту пару точек? Или мы перебираем все прямые, полученные на предыдущем шаге и проверяем, проходят ли это через эту пару точек? Попахивает кубом...
"Зная угол, под которым проходит прямая-ответ, несложно указать оптимальное d: для фиксированных a, b, задающих угол наклона прямой, нужно выбрать два самых часто встречаемых с этими значениями a, b значения c" — неплохо было бы пояснить, как мы всё это делаем, не получая TL
Спасибо за Ваши замечания.
Разборы готовились из фактора донести основную идею, но не преподнося её на блюдечке, чтобы участники чуть-чуть подумали дополнительно. Ваша критика была услышана, и действительно в разборе задачи D была некоторая неоднозначность, я попытался её убрать.
К сожалению, я не вижу комментариев от участников, которые не смогли решить задачу, и задали конкретный вопрос — что же в разборе непонятно.
По поводу комментариев с опечатками: в будущем, пишите в личку, пожалуйста.
Я совершенно согласен, что не надо всё разжовывать. Однако во многих задачах основная идея, наоборот, скрыта и именно это мне не нравится. Например, в первой задаче читателю предоставлена голая формула. Донести основную идею можно было бы так: "Заметим, что если максимальная сумма, которую можно составить, равна m и есть хотя бы одна монета номинала 1, то можно составить любую сумму от 1 до m".
По поводу комментариев от не понявших разбор участников — как преподаватель физматшколы с десятилетним стажем (я сожалею, что мне проходится совершить отсылку к этому факту моей биографии), я по опыту знаю, что КРАЙНЕ малое число людей обладают способностью сообщить о том, что им непонятно, особенно публично. Большинство людей либо решают, что эти задачи (пока что или же окончательно) слишком сложны для них, раз они не понимают даже разбора; либо им лень вдумываться и они забивают; либо они пытаются додумать этот разбор ещё несколько дней, и у них, может быть, даже получаются, но они остаются с ощущением, что эти задачи были очень сложны, хотя на самом деле это не так.
Правда на все 146%. Прочитал вот решение задачи D (которую не решил), и подумал: "черт, какой же я тупой, даже разбор понять не могу".
По задаче D, мы поддерживаем одно состояние лампочек или нет? Т.е. если мы можем "отменить действие" кнопок A и B, то то мы независимо друг от друга рассматриваем эти состояния и получаем, что то на подобии BFS?
Какая асимптотика у задачи?
Короче так, в задаче требуется, чтобы в итоговой позиции после наших действий определённые лампочки оказались включены, а определённые — выключены. Рассмотрим кнопочки, которые не портят эту ситуацию, то есть, которые выключают, причём только те лампочки, которые и должны быть выключены, любо включают, но только те, которые и должны оказакться включены. Именно такого рода кнопка должна оказаться в конце наших действий. Если таких нет, значит, выигрышную позицию получить нельзя. Если есть, то нажмём все такие кнопочки в конце нашего процесса. Вследствие этого состояние некоторых лампочек окажется гарантированно правильным, независимо от наших предыдущих действий. Помечаем эти лампочким "выигранными" (логика названия "неизвестные" мне неясна), а нажатые кнопочки — нажатыми. Далее решаем ту же задачу, игноруя выигранные лампочки и нажатые кнопочки. И так, пока не придём к положительному или отрицательному результату. Асимптотика O(nm2), по O(nm) на каждую такую итерацию.
Благодарю, по такому объяснению и становится очевидно почему это верно.
Что ж, ничего необычного для КФ. Кто в плюсе — тот и прав.
Да забей. Люди не любят когда у кого-то претензии, вот и минусуют, хотя сами этот контест даже не писали. Согласен почти со всеми твоими замечаниями к разбору.
Спасибо.
Да мне-то ладно, у меня запас вклада большой. Но жаль, что комментарий скроют и его мало кто увидит, а организаторы могут решить, что участники не согласны с этими замечаниями и с разборами всё нормально.
Разбор правда не то чтобы сильно хорош, но некоторые замечания выглядят как явные придирки — например, тот факт, что цифровой корень числа связан с остатком при делении на 9, вряд ли можно назвать нетривиальным. Всё же разбор предполагает некоторые усилия и знания (и/или умение гуглить) со стороны пытающихся понять решения, и если, например, среднестатистическому семикласснику неочевидно решение даже простых задач, это вполне нормально.
Как и всю задачу в целом. Однако же многие участники её не решили. Если участник не знал и за 100 минут не разборался сам и не загуглил факт об остатках при делении на 9, то, думаю, настала пора ему об этом сообщить явно, пусть даже не доказывая. Зачем это от него скрывать? Так разбор будет нести некую образовательную функцию. А по такому разбру задачи В чему можно научиться? "Если просят посчитать количество чего-то на отрезке, проверьте, а не циклятся ли оно?"
Совершенно не факт, что такой участник сильно старался. Ну и да, стремление посмотреть, как последовательность себя ведёт на достаточно больших отрезках, выглядит довольно разумным.
Да, пожалуй. И всё-таки, зачем скрывать факт об остатках при делении на 9?
А зачем упоминать о всех деталях? Подобные факты могут сильно раздуть разбор — можно с тем же успехом спросить, почему «любая прямая задаётся тройкой коэффициентов», почему прямые на плоскости параллельны, когда коллинеарны их нормали, ну и так далее.
Но там ведь сказано "любая прямая задаётся тройкой коэффициентов". Я же не предлагаю объяснить, почему — только сообщить, что имеет место такой факт.
Ну ещё бы не выдержал.
Правда, уже из двух мест в Mail.Ru Group уволили...
Даже решив D, я всё равно не понял то, что написано в разборе
Попробую объяснить почему корректно D.
Обозначим результат работы алгоритма (массив лампочек) через res. Обозначим массив кнопок, "нажатых" алгоритмом, через btnres, а массив кнопок из ответа btnans.
Пусть есть ответ, но алгоритм из разбора не нашёл ответа. Тогда в res есть лампочка, которая в неизвестном состоянии. Но тогда в btnans есть кнопка b, которая переводит эту лампу в нужное состояние. Очевидно, что кнопки b нету в btnres. Тогда добавим b в самое начало (то есть она нажмётся первой) btnres. Тут три варианта: 1) привели лампы в нужный вид 2) привели какую-то лампу к противоречию (а именно, выключили её, вместо того чтобы включить и обратно) 3) всё ещё остались лампы в неизвестном состоянии.
Ну с 1) всё ок.
С 2) поступим так. Так как мы привели лампу к противоречию, то в btnans должна быть кнопка (которой опять же нет в btnres), которая ставит эту лампу в нужное положение. Добавим эту кнопку в btnres так, чтобы она нажималась после всех добавленных нами кнопок, но до кнопок полученных алгоритмом.
С 3) ровно так же как и с 2). Должна быть нужная нам кнопка в btnans.
Очевидно дальше мы вновь переходим в одно из этих состояний. Но. Пусть мы добавили уже все кнопки из btnans, но всё ещё есть "плохие" лампы. Тогда опять же, должна быть кнопка в btnans. Что приводит к противоречию.
Когда мы обращаем нажатие кнопки, помечаем все лампочки, за которые она отвечала, что их состояние неизвестно.Не ясно, как гарантируется атомарность операции: то что все неизвестные лампочки после одной операции будут иметь одно и то же неизвестное состояние.
К сожалению, не понял вопроса. Неизвестность состояния означает следующее: мы вольны выбирать состояние лампочки до нажатия этой кнопки, когда нам это понадобится, потому что мы переписали её значение нажатием кнопки.
Спасибо, понял.