Приглашаю всех участников Codeforces принять участие в VIII Открытой олимпиаде ЮФУ по программированию в г. Таганроге.
Как и в прошлом году, в программе Олимпиады ЮФУ два независимых турнира: Личный и Командный. Командный турнир будет проводиться по правилам ACM ICPC. Правила личного турнира ещё в процессе обсуждения — планируется 4-х часовой контест по правилам TopSpeedCoder с частичной оценкой решений и выбыванием участников, но окончательное решение и описание правил будет на днях.
Каждый турнир (как личный, так и командный) включает:
- отборочный этап (онлайн, 14-17 марта 2014 г. на www.contester.tsure.ru)
- финал (19-20 апреля 2014 г., Инженерно-технологическая академия ЮФУ, Таганрог).
К участию в Олимпиаде приглашаются все желающие без ограничений.
Для участия в Олимпиаде необходимо не позднее 13.03.2014 заполнить регистрационную форму на рабочем сайте Олимпиады www.contestsfedu.org.
Оргвзнос за участие в Олимпиаде не предусмотрен!
На задачах финала Командного турнира планируется проведение этапа Гран-при Приазовья XIV Открытого Кубка имени Е.В. Панкратьева по программированию.
В состав жюри, помимо представителей ЮФУ, входят aropan, cmd и ivan.popelyshev.
Все остальные подробности — на страничке олимпиады.
FINAL: Олимпиада завершена! Благодарим всех за участие и надеемся, что Вам понравилось. Результаты обоих турниров здесь. Задачи: личный турнир и командный турнир. Разбор всех задач в обсуждении ГП Приазовья.
UPD: Добавлены тренировки: личный турнир и командный турнир.
Через несколько минут стартуют оба отборочных тура. Участники, не успевшие своевременно зарегистрироваться и не отображаемые в списке на страничке олимпиады, могут заполнять регистрационную форму до 18:00 14.03.2014. Логины и пароли этим участникам будут высланы до 23:59 14.03.2014
Не понял, как проходит отборочный тур. Разъясните, пожалуйста, для особо непонятливых вроде меня.
я вообще залогиниться не могу
Выявили некоторые проблемы с логинами/паролями. Разбираемся. Если у кого-то ещё аналогичная проблема, пишите на ContestSFedU2014@gmail.com с указанием фамилии/логина.
http://contester.tsure.ru/ Авторизуетесь, находите в списке соревнований отборочный тур, решаете.
После ввода логина-пароля выводит "Доступ запрещен"
Проблемы с авторизацией участников решены. Приносим извинения за ожидание.
Что с contester.tsure.ru? Он уже довольно продолжительное время лежит (чекал здесь http://www.downforeveryoneorjustme.com/).
В настоящее время решаем эту проблему.
Работоспособность сайта восстановлена.
учитывать штрафное время(а не попытки) в соревновании, которое идет 3 дня и началось в будний день, действительно классная идея. :)
Поддерживаю, какой тогда смысл делать отбор 3 дня? Да еще личный и командный одновременно?
Временно прекратили приём решений (убраны win-компиляторы из интерфейса отправки) по причине неисправности на сервере, которую жюри сможет устранить только завтра утром.
Функционирование win-чекера восстановлено. Попытки с вердиктом [Неустранимая ошибка тестирования] перетестированы.
Только что сделал 2 сабмита и получил [Неустранимая ошибка тестирования].
В Вашем решении выделяется гигантский (в 3 раза превышающий ML) объём статической памяти. По хорошему — это Memory Limit на тесте 0, а "Неустранимая ошибка тестирования" срабатывает, потому что чекер трактует этот случай, как невозможность запуска программы на выполнение. В общем, known-bug системы.
Ок, спасибо.
ну вот, сервак лежал по пол дня и даже не продлили. :(
По ходу соревнований жюри не получало от участников запросов по поводу продления соревнования, из чего был сделан вывод, что имевшие место технические проблемы существенно на ход соревнования не повлияли.
ну жюри нигде и не объявляло, что нужно просить о продлении, если необходимо. Кажется логичным, что когда сайт недоступен днем(да еще и на выходные) это как-то да влияет.
А может все-таки продлите на одни сутки?
Например, так сделали на идущем параллельно соревновании Codechef March Long Challenge всего лишь из-за проблем с одной задачей. А тут проблем было гораздо больше.
Коллеги, соревнование официально завершено, и с 12-00 сегодняшнего дня повлиять на это нельзя. Трое суток — это более чем достаточным срок для спокойного решения 3-4 задач в обоих контестах, чего скорее всего будет достаточно для попадания на финал. Участники, которые не попадут на финал личного турнира, как всегда смогут участвовать вне конкурса со своих ноутбуков.
Конкретно в Вашем случае за трое суток не было сделано ни одной попытки сдать задачу в личном туре. Согласитесь, с Вашей стороны несколько несправедливо просить продления контеста по отношению к тем, кто соревновался и пытался успеть решить задачи в эти 3 дня :)
Думаю, что запросов на продление не было, исходя из того, что обычно в случае технических проблем контесты продлевают.
А что за сообщение было по задаче C командного турнира? Объявление о сообщении есть на главной, но в соревнование уже не войти ибо оно закончено. Кто-нибудь успел его заметить?
Мы сразу после обнаружения ошибки пофиксили условие, поэтому если условие качали не сразу, то не должны были заметить ошибку.
Разбор задач будет? Если нет, как решать 6ую с личной? Заранее спасибо за ответ
Ответ может быть двух видов.
Склейка не влияет ни на что (максимальная область где-то внутри одной из фотографий). Такое решаем тривиально. Находим максимальный по площади прямоугольник из 0 по всем фотографиям и говорим, что это — текущий лучший ответ, разве что потом получится найти что-то лучше благодаря склейке.
Благодаря склейке получается улучшить ответ. Если мы зафиксировали высоту, то нам нужно максимизировать ширину. Ответ имеет вид левый крайний прямоугольник — внутренние прямоугольники — правый крайний прямоугольник. Внутренние наш ответ покрывает по всей ширине, левый — только по какой-то части справа, правый — по какой-то части слева. Понятно, что внутренние нужно использовать все, какие подойдут; левый и правый — выбрать из лучших возможных (некоторые неудобства из-за того, что лучший правый и лучший левый могут совпадать, и надо будет на одну из позиций использовать второй лучший).
Для каждой клетки посчитаем высоту столбца из 0 вверх от нее. Теперь можно втупую перебирать: фиксируем строку, фиксируем высоту х; тогда для каждой фотографии можно определить, может ли она быть внутренней (для этого на этой строке все столбцы нолей должны быть высотой не меньше х), а также насколько она выгодна в роли левой и правой (аналогично). Строим из этого лучший ответ для данной строки и высоты, сравниваем с глобальным лучшим ответом.
Как нормально решать 5ую командную? Я сдал K+L+N*M*N*M, но это как-то не похоже на авторское решение.
5ую я решал так:
нужно решить две основные задачи: (1) сумма чисел на косом отрезке, (2) минимум ромбов, центр которых на косом отрезке. Обе эти задачи решаются построением дерева отрезков на массивах, которые строились выходом из некоторой фиксированной точки поля в некотором направлении, пока не случится цикл.
Когда решили первую задачу, нужно предпосчитать ромбы от каждой клетки N*M с радиусом k и l, а затем на основе этих данных решить вторую задачу. Предподсчёт ромба происходит так: вначале считаем ромб от точки (0,0), а затем идём вниз на N, таким образом относительно предыдущего шага можно за log(NM) узнать текущий ромб, и соответственно от каждой из таких клеток вправо на M, таким же способом и сложностью.
После всего просто пробегаемся по каждой клетке и на основе решённых задач считаем ответ.
Не помню тонкостей реализации, но получается что-то около O(K+L+NMlog(NM))
Детали не очень понятны, но в общем суть ясна. Спасибо за ответ.
Нормального решения 5ой тоже, к сожалению, нет (Сдали очень неаккуратно реализованные частичные суммы и sparce table на диагоналях, а вот N * M * N * M не зашел в силу кривости моих рук). По-прежнему прошу авторов выложить разбор. Хотя бы основные идеи
Вечером выложу презентацию с разбора 2011 года. Задача принадлежит перу aropan — может дополнит, если будет недостаточно.
(не в ту ветку)
Обещанный разбор задач "В поле ягода навсегда" и заодно "Студия звукозаписи" тут.
Чтобы нормально зашло N*M*N*M, достаточно после группировки считать промежуточные ответы в int вместо long long (считаем все N*M*N*M остаточных слагаемых в int'ах, а потом уже окончательный ответ суммируем в long long). На СF в запуске решение целиком на long long работает примерно 0.7, решение с использованием int — менее 0.4.
Вообще NMNM автором не предполагалось засчитывать. По моей информации ни на оригинальном контесте, ни на Opencup того года такая асимптотика не проходила. Авторское решение работает за 100 мс на C++, но ставить TL 0.5 секунд не рискнули, чтобы не зарубить лишнего))
У меня сложность решения max(n, m) * n * m и зашла за 0.75 секунды примерно, хорошо что 0.5 не поставили.
Все задачи доступны для дорешивания в банке задач.
Командный турнир:
Личный турнир:
А расскажите как решать D в командном? Интернет-Зависимость — Подстветить все буквы строки.
разбор задачи А
Можно еще проще, без автомата.
Во-первых, заметим, что ответ не превышает 51 (все вхождения каждой буквы можно вычеркнуть за 2 хода, а последнюю даже не надо будет вытирать).
Построим по входной строке "обрезанный бор", в котором все, что глубже 50 — удалено. Т.е. есть только те подстроки, размер которых не больше 50.
Как выглядит наш ответ в терминах этого бора? Мы стартуем из корня, куда-то идем, потом или возвращаемся назад, или опять куда-то идем... В результате — куда-то приходим, в этот момент подсвечиваем уже всю строку, останавливаемся. Что мы "находили"? Путь от корня к месту финиша прошли 1 раз, все остальные ребра, по которым ходили — дважды (вниз и обратно вверх). Понятно, что все "двойные" ребра можно вынести на уровень корня бора, т.е. идти с корня по такому же ребру вниз и обратно вверх — от этого хуже не станет. Таким образом приходим к выводу, что есть смысл набирать не более одной строки длиной более 1, а остальное убивать по одной букве.
Далее дело техники, пишем dfs по нашему бору, который для каждой вершины считает ее глубину dep и то, сколько различных непокрытых букв dif остается, если набрать подстроку, которой отвечает эта вершина. Ответ для вершины — это dif*2+dep (набираем и удаляем все плохие буквы, потом набираем эту подстроку). Итоговый ответ — минимум из ответов по всем вершинам.
Чтобы быстро пересчитывать покрытые/непокрытые буквы — делаем прекальк, сколько всего есть вхождений каждой из букв в строку, а так же в боре храним для вершины список позиций, в которых заканчивается такая подстрока в оригинальной строке.
Решал аналогично. Вот только проблема с построением такого бора. У нас 10^5 строк по 51 символу. Итого бор занимает памяти O(26 * 51 * 10^5). Как с этим нормально бороться? Сам делал эвристические отсечения для большой строки.
Будем хранить сыновей вершины в виде списков ребер, а не с помощью массивов на 26.
Понятно, что суммарно сыновей не больше, чем вершин в боре (и рассматриваемых подстрок вообще) — это можно оценить сверху как 5*10^6.
Тоже так делал, но тогда для того чтобы понять по какому из ребер переходить при построении бора необходим бинпоиск. Тут я упирался в TL.
Зачем бинпоиск? Это решение получает АС с линейной проверкой (просмотрим все ребра и выберем нужное).
Да и как вообще нормально туда прикручивать бинпоиск? Я не умею. Если ребра отсортированы, то мы можем бинпоиском найти нужное нам. Но если нужного не нашлось, и его надо добавить? Вставить его, сохранив упорядоченность массива — это уже линия, а не логарифм.
Кстати, у меня один из compilation error (Java) случился потому что я описал несколько классов в одном файле. Пришлось сделать эти классы внутренними.
Ну и коль вспомнил, кф зачем-то не даёт запускать main из abstract класса. Почему бы не добавить в паттерн поиска public class слово abstract?
Задачи добавлены на contester.tsure.ru:
Командный турнир: SFU_2014_A — SFU_2014_I.
Личный турнир: SFU_2014_PERS_A — SFU_2014_PERS_G.
Давайте тренировки сделаем. Наверняка же, в Полигоне задачи готовили.
Хорошая идея — сделаем) Нужно только наши логи перевести в удобоваримый формат. В общем в личку напишем, если будут вопросы.
Можно просто запарсить ранклисты визардом. Конечно, это чуть хуже, но тоже хорошо.
Сделал тренировки для личного и командного контестов с информацией обо всех посылках с онсайта.
Расскажите про динамику в задаче А с личного тура, пожалуйста.
d[x][y][z] — минимальная стоимость товаров, где x — количество товаров, которые мы всего перекинем в конец ленты (0..n), y — количество товаров, которые мы уже перекинули в конец (0..x), z — количество уже рассмотренных товаров (0..n). Параметр x нам даёт возможность при рассмотрении z-го товара точно говорить о том, заплатим мы за него или нет (можно утвержать, будет он k-й, если мы его не перекинем (z-y)%k==0, или будет ли он k-й, если мы его перекинем в конец (n-x+y)%k==0).
Спасибо
Но ведь такая динамика не влезет в память? Получается, нужно хранить 2 слоя, но по каким параметрам это корректно?
можно перебирать x сверху, и для каждого его значения считать динамику по y и z
Спасибо. А почему именно сверху? Что-то я пока не могу сообразить, какие переходы будут между слоями...
Я говорю о том, что x перебирается в цикле уровнем выше. внутри цикла заводишь двумерный массив и считаешь динамику. слои между собой вообще никак не связаны.
О, теперь все понял, спасибо большое.
Как решать задачу B с финала личного турнира?
http://mirror.codeforces.com/blog/entry/11805#comment-166037
Какое авторское решение D с финала личного турнира?
Безидейный HLD? Или можно что-то менее очевидное и более простое?
И еще вопрос, на каких машинах проходил контест? Я в тренировке сдал по ней корневую, которая на CF работает за 0.25. Потом вспомнил, как приходилось пихать задачи в отборочном туре.
По D: Можно считать количество пар пересекающихся и потом вычесть и общего числа пар. Предполагалось что-то такое:
Подвесим за любую вершинку дерево.
Теперь для каждой пары вершин ui и vi образующих путь посчитаем вершинку wi = lca(ui, vi).
Раскидаем все запросы по wi. Т.е. для каждой вершинки заведем вектор
куда сложим по wi пути: 
.
Теперь будем обходить наше дерево dfs'ом и что мы имеем: пусть мы рассматриваем вершину u. Все пути лежащие в
пересекаются между собой (можно сразу к ответу добавить количество таких пар). С какими еще путями пересекутся пути из 
? Это те пути которые начались где-то выше и их концы заканчиваются в поддереве вершины u.
Таким образом, каждый раз когда мы входим в вершину u — суммируем количество помеченных вершин в поддереве. И затем помечаем концы каждого из путей в
. Когда завершаем обработку вершины u — разотмечаем их обратно.
Помечать вершину и находить сумму в поддереве можно с помощью обычного фенвика.
Спасибо, ощутимо проще HLD)
Если я правильно понял, то можно даже без Фенвика? Написать dfs, который будет возвращать set путей, проходящих через данную вершину, у которых корень не в этой вершине. Тогда на входе в один из концов пути, не являющийся корнем — добавляем в set этот путь, в корне — удаляем его из set'a.
Да, похоже на то. В таком случае даже и
lcaискать не надо. Вроде Fcdkbear примерно так и решает здесь.Будет ли в этом году проводиться олимпиада?
Я сегодня у Deamon спросил. Он сказал, что планируют, но пока еще все не официально.
Олимпиада будет. По датам отбор планируется 13-14-15 марта, основной тур 18-19 апреля. Пока это неофициальная информация, на днях будет объявление, где точно всё озвучим.