Здравствуйте!
Рад пригласить Вас принять участие в моем первом кратком соревновании на codechef.com, в воскресение, 20:00 по Москве. Раньше я уже давал несколько задач для длинных контестов, но это первый полный контест, все задачи которого подготовлены мной. Стоит также отметить, что контест мне помогал и помогает готовить Anton_Lunyov, за что ему отдельное спасибо.
Для участие в соревновании Вам достаточно зарегистрироваться на сайте, дополнительной регистрации на соревновании не нужно. Контест пройдет за стандартными правилами ACM-ICPC, Вам нужно будет решить 5 задач за 2,5 часов. Первые 10 участников получают призы от организаторов.
Сразу после соревнования будет опубликован разбор. Также после соревнования здесь можно будет обсуждать задачи а также написать мне все что Вы думали об задачах и что хотите увидеть в будущем.
Удачи!
Lucky numbers again? I like them! :P
CodeChef = Lucky number :D
Как решалась LUCKFILL? Мой перебор почему-то получает WA.
Возможно что-то лишнее отсекаешь. Мой перебор упорно ловит ТЛ, хоть локально и летает.
Возможно. Но стресс с перебором без отсечений проходит.
Предподсчет.
Для всех Н <= 50, K = 50 запомним ответы, а потом на каждый тест просто возьмем и проверим все что нашли: для Н=11 их максимально кол-во(2048).
k = 50 — опечатка? А запоминаем ответы — это значит перебираем все возможные строки с отсечением?
Нет, не опечатка. Перебор не заходит из за того что его много раз вызывают на Н=11, и он кучу раз выполняет много лишних операций. А так мы запомнили ответ для худшего теста и просто проверяем: помещается или нет строка под шаблон и кол-во различных подстрок.
А их точно 2024? Просто даже если рассуждать логически, выходит 2048. Всего у строки длины 11 есть 11 * 12 / 2 = 66 подстрок. Подстрок длины 1 всего бывает 2: "4" и "7", а мы же посчитали что их 11, значит надо из 66 вычесть 9. Подстрок длины 2 всего бывает 4, а мы посчитали что их 10, значит надо вычесть еще 6. Подстрок длины 3 всего бывает 8, а мы посчитали что их 9, значит надо вычесть еще 1. Получаем 66 - 9 - 6 - 1 = 50. Значит, нам подходит любая строка длины 11, т.е. ответ 2048.
Извини, на автомате написал. Там 2048.
у кого-нибудь еще не работала кнопка submit в последние 4 минуты контеста?
угу, same here.
Мб раунд анрейтэд будет?
У меня работало.
да как назло, отправил — получил тл, исправил через 2 минуты — уже не отправляется
Кто расскажет как решать "Little Elephant and CNSes"? А то для N>=1000 знаю решение, а вот для маленьких не совсем.
(Наверно, у меня не самое простое решение)
Рассмотрим для какой-то строки функцию f(c4,c7) — минимальное количество замен, чтобы в строке оказалась подпоследовательность из c4 четверок и c7 семерок. Эта функция возрастает по каждому параметру (и кое-где равна бесконечности). Будем использовать два "указателя": возрастающий c4 и убывающий c7. каждый раз, увеличив c4 на 1, будем уменьшать c7, пока замен слишком много в сумме по всем строкам.
Осталось научиться поддерживать f(c4,c7), умея увеличивать c4 и уменьшать c7 на единичку за амортизированное O(log чего-нибудь).
Для каждого символа (точнее, каждого промежутка между соседними символами) в строке посмотрим, какой будет функция f(c4,c7), если поместить "центр" (переход от 4 к 7) подпоследовательности сюда. Тогда f(c4,c7)=const+c4+c7, если c4 и c7 достаточно малы, иначе — бесконечность (на самом деле там больше случаев). Значит для получения f(c4,c7) достаточно уметь находить минимальное const из всех подходящих по диапазону c4 и c7. Можно поддерживать множества позиций, подходящих под текущие c4 и c7 и обновлять его при изменении c4 и c7. Много деталей опущено, там достаточно запутанная реализация получилась.
Блин, дошел до этой функции. Но писал бинарный поиск. И не понимал как соптимизить.
Спасибо за интересные задачи!
You can read the editorials here.
Setter's and Tester's solutions are not available.
UPD. Fixed.
Клевые задачи, спасибо!
что-то какой-то сложный разбор Little Elephant and Balance, напишу свой, может кому-то поможет.
поймем, когда строку можно разбить на две сбалансированые. начнем движение сначала строки, будем поддерживать количество четверок — х на префиксе, и семерок — y на суффиксе, перед началом строки x = 0, y = кол-во семерок в строке, когда мы сдвинемся на позицию вперед произойдет одна из двух вещей, количество четверок станет равно х + 1, либо количество семерок станет равно y — 1...
очевидно, что таким образом когда-нибудь х станет равен y, потому что у нужно уменьшится на y — x, y уменьшится на количество семерок в худшем случае, очевидно, что количество семерок не меньше, чем y-x, становится понятным, что этого не произойдет тогда, когда все строка равна 7кам, потому что Х <= |S|, а берем мы первые Х — 1 элемент. т.е. в ответ не войдут подстроки вида 777...77, то есть из общего количества строк n * (n + 1) / 2 нужно отнять все такие подстроки. профит
Примерно тоже самое написано в абзаце разбора "Proof of the author". Просто в начале дано совершенно другое решение с деревом Фенвика и потом я привёл ещё своё доказательство.
Мне понравилось, что в разборах на codechef есть ссылки на решения автора и тестера. Почему бы не делать тоже самое в разборах на CF? По-моему, очень помогает при разборе.
Одна из причин, как я думаю — Codeforces в принципе не позволяет никому увидеть решения владельцев контеста ни до, ни после.
Некоторые авторы дают ссылки на свои решения в разборе, так что я не думаю, что КФ не позволяет этого делать. Или я не так уловил мысль, и подразумевалось то, что это технически невозможно?
задачи хороши, даже не смотря на то, что они все однотипные (нет графов, геомы или еще чего-нибдь)
Ты считаешь, что графы и геометрия это верх разнообразности задач?
Думаю от геометрии и реализации всех тошнит. А идейные задачи нравятся большинству.
я что-то против сказал?
Тем не менее, мне как-то надоело весь контест думать примерно об одном и том же.
Ну не знаю, я совсем не рад задаче LUCKFILL. На кодшефе компьютеры какие-то ужасно медленные и очень тяжело сравнивать время на сервере с локальным временем. Я дописал кучу отсечений к перебору, он очень быстро работал локально, но на сервере всего раз получил ВА, когда я неправильное отсечение добавил. А так он то и делал что ТЛил. Я не сделал прекальк, т.к. не видел, почему оно должно было что-то кардинально изменить, т.к. в переборе и так куча оптимизиций была. А оказалось, что именно это решало.
где дорешивание?
Дорешивание, кстати, подняли.
А на codechef есть возможность смотреть ранклист контеста?
http://www.codechef.com/rankings/COOK22
While upsolving this contest, I found one Codechef feature: when you submit a problem and go to campus.codechef.com, in recent activity you see submission status. Difference with codechef.com is that if your solution is running you will also see some number in parentheses under running icon. Apparently, this is the number of test your solution is curently tested on(sometimes you can also see "running judge" with number too).
I also found out that your solution is actually tested against the whole testset even if it fails on some intermediate test. However, execution time will be only counted on first tests you passed plus the first test you failed (I mean time that will be shown to you if you get Wrong Answer). It's only my guess of course, but I strongly believe this is how their judge works.