Всем привет!
Уже сегодня (25 октября) в 15:00 пройдет очередная командная интернет-олимпиада для школьников. На этот раз вас ждет встреча с Альфом.
Продолжительность — 3 часа в базовой номинации, 5 часов — в усложненной. Подробнее о номинациях и правилах можно прочитать здесь.
Если вы еще не регистрировали команду на интернет-олимпиады в этом сезоне, то сделать это можно тут.
Условия появятся на сайте в момент начала олимпиады. Сдавать задачи можно в PCMS2 Web Client (русская версия).
Олимпиаду подготовили Дмитрий Филиппов (DimaPhil), Илья Збань (izban), Евгений Замятин (Odeen), Захар Войт(zakharvoit) и Григорий Шовкопляс (GShark).
Удачи!
Спасибо авторам за хороший контест и как решать F?
У нас на эту задачу написано что-то, похожее на мерджсорт.
Чтобы в n-той очереди получить все 2n чисел в порядке возрастания:
Первый и третий пункт выполняются рекурсивно. База рекурсии — в первой очереди каждый отрезок из одного элемента отсортирован.
Решение придумал и написал Alex_2oo8, который дописал идейную часть за пару минут до конца, приделал к ней аутпут, заслал, получил TLE, вспомнил, что аутпут большой, увеличил размер системного буфера и, за 37 секунд до конца соревнований, заслал решение, которое получило AC.
А что случилось с тестированием задачи G?
Мы её заслали где-то за полтора часа до конца, когда по ней ещё не было ни одного акцепта (или вовсе ни одного сабмита?), но в это же время появилось сообщение о реджадже D, так что мы особо не рассчитывали на быстрый фидбэк. Но время шло, другие команды получали акцепты, в том числе MishCo значительно позже нас получили плюс и по G, а у нас всё ещё было «Judging...», и так до конца контеста и осталось.
Мы об этом ещё во время соревнований сообщили жюри, но только минут через двадцать после конца получили ответ «исправлено», после чего с удивлением обнаружили, что мы-то плюс получили, а вот MishCo свой потеряли :) Как так?
С тестированием задачи G случилось неправильное авторское решение :( Сначала мы не заметили ваш UD, потом, когда вы нам написали, мы начали разбираться и уже после конца контеста нашли багу в решении и исправили ее. Решение MishCo работало так же, как и неправильное авторское решение, поэтому и получило свой минус (правда уже после конца контеста, плохо довольно получилось :( )
Кстати, можешь рассказать ваше решение? Просто есть подозрение, что у нас плохие тесты, и на самом деле ваше решение не должно получать ОК :)
У нас решение такое:
С графской стороны — у нас множество циклов. Все циклы должны быть четной длины и в каждом цикле мы выкинем ровно половину ребер (через одно). У нас есть два варианта для каждого цикла — выкинуть все четные или все нечетные ребра.
Если в одном цикле пересекаются два ребра с одинаковой четностью, то в данном цикле ребра с этой четностью обязательно нужно выкидывать. Если в каком-то цикле нужно выкинуть и четные, и нечетные ребра — ответ NO.
Если пересекаются два ребра из разных циклов, то это нам дает условие, что в этих циклах мы выкидываем одинаковые (или разные) по четности ребра. UPD Неверно!
Оставшаяся задача — покраска графа в два цвета (по четности ребер, которые выкидываем), где вершины — циклы, а ребра означают одинаковые/разные цвета. Для некоторых вершин заранее задан цвет (пересечениями внутри цикла).
Прикольно. Довольно просто идейно получилось, у меня решение посложнее. Предполагалось, что в этой задаче надо написать 2-SAT
А тесты будут?
Архив олимпиады появился на сайте. Разбор задач появится позднее
В задаче J тест #9 некорректен, четвертое число с конца — 0, хотя в условии 1 ≤ ai ≤ 109.
А в G действительно нужен 2-SAT и наше решение не верно. Вот тест:
PS В ветку выше коммент упорно не хочет отправляться.
Спасибо, я в тренировке его удалил.
Да, действительно. Спасибо за тест, добавил его :)
Дайте точный тест (можно номер в архиве). Надо и в тренировку же добавить.
В задаче "Ломать — не строить" все авторские решения не проходят предложенные тесты: segments_dp.cpp, segments_zv_bipartition.cpp — падают на первом, segments_zv.cpp — на 19.
Решения _dp и _zv_bipartition не должны работать, заменил их на _dp_wa, _zv_bipartition_wa. Решение _zv должно быть правильным, но я случайно залил старое решение с багой, которую мы нашли уже на контесте. Все исправил, залил заново. Теперь на сайте лежит правильный архив
UPD. Только сейчас заметил, что авторское решение падает на тесте от Alex_2oo8. Будем разбираться. В архив положил правильный ответ на тест (тест 7).
Слишком много баг для одной задачи :( Приношу свои извинения за такую некачественную подготовку
Добавил в Тренировки:
Похоже, что в задаче D не слишком сильные тесты.
Мы писали дерево отрезков и выделили под него 200000 массивов по 1230 чисел (количество простых делителей у произведения в текущем узле; порядковый номер простого числа устанавливался с помощью решета Эратосфена). Такая реализация занимает около гигабайта, и понятно, что это решение не пройдёт (ML16). Зато когда мы заменили тип данных int на short, то получили уже WA36, а когда поставили unsigned short, то получили AC. Хотя по идее оно проходить не должно, например, на таком тесте:
То есть, в верхнем узле для простого делителя 2 должно храниться число 50000×13=650000, что в 16-битную переменную никак не укладывается.
Ну вообще цели отсечь такое решение не было — оно идейно правильное. Но то, что такое заходит — не очень хорошо, да. В авторском решении вместо дерева отрезков просто дерево Фенвика
А авторское решение на джаве точно не получает ML? И сколько памяти тогда оно тратит?
У меня ровно такой же расход памяти, но от ML пришлось спасаться как раз ДО для подсчёта количества простых больше 100, а это уже ведёт к таймлимиту.
PS Считаю как 1300*50000*8 байт ~ 520Мб.
PPS нагуглил, что int == 4 байта. Тогда почему такое решение получает ML?
У меня это решение получило TL 16, использовав 509 Мб памяти. А вообще у вас при каждом запуске factorize создается новый массив cf. Если сделать его глобальным, решение тоже получает TL 16, но уже с 326 Мб
Авторское решение на джаве работает за 1.3 секунды с 326 Мб
Если с памятью проблемы, то можно написать корневую — 8487595 использует всего 1.7 мб.
P.S. Перечитывайте лишний раз условия, которые составляете, это ведь не сложно. "кратчайшее расстояние от его дома до всех интересных мест города изменится у максимального числа интересных мест" — это еще куда не шло, но "Два сообщения не могут в данный момент по одному ребру может проходить максимум одно сообщение" напомнило мне цитату Кличко:)
Можно маленькие делители (до корня из 10000) хранить в int, а остальные — в short. Но есть более изящное решение — для каждого отрезка хранить факторизацию в виде списка пар делитель/степень, отсортированного по возрастанию делителя. Слияние таких списков осуществляется как в сортировке слиянием. Так как число до 10000 может иметь максимум 5 разных простых делителей, получается серьезно сэкономить на памяти — моя реализация на C# потребяет всего 34МБ.
Изначально у нас было именно такое решение: мы хранили пары делитель/степень в векторах и использовали сортировку слиянием для объединения. Но мы получали TL. Потом просто в качестве эксперимента попробовали написать без векторов, кто-то предложил "костыль" с uint16 — и зашло. :) В архиве тестов, из того, что я видел, такого теста, который я предложил, нет.
Вот что недавно мне пришло в личные сообщения:
Что характерно, в этой задаче был написан валидатор, содержащий строку
ensureLimits(n, 1, 15, "n is out of range");То есть он просто не был запущен. Ну правда, может вы перейдете на Полигон? Это классический пример раздолбай-бага, который невозможно допустить с Полигоном.А еще в условия http://neerc.ifmo.ru/school/io/archive/20141025/problems-20141025-basic.pdf в колонтитуле выразительно написано вторая олимпиада, 12 октября, хотя олимпиада третья и была 25-го.
Приятно удивился, что подход с раздачей прав на редактирование тренерам работает — в усложненной секции некорректный тест был кем-то разумно удален. Работает система )
Да, такая ошибка есть. Посмотрел пакет, выложенный сразу после олимпиады -- в нем нет этого теста. На олимпиаде так же присутствовал этот некорректный тест, и единственная команда, сабмитившая эту задачу (Progmeistars AAI) каким-то чудом после TL29 догадалась поднять константы в своем коде до нужного числа и получить OK. Хочется поздравить ребят с таким умением угадывать ошибки авторов :(
Мы понимаем, что в наших задачах по "странным" случайностям всплывают непонятные баги, и сильно извиняемся. Честное слово, этого больше не повторится.
PS: Данный баг, видимо, произошел из-за конфликта версий задачи на тестирующем сервере и в svn, где готовились задачи, и был вызван ошибками сразу нескольких человек. Я считаю полигон очень удобным средством для подготовки задач, но по некоторым причинам в ИТМО он непопулярен.
Спасибо. Я час назад скачал файл archive-20141025-basic.zip, там этот тест есть :(
На сайте выложен разбор базовой и усложненной номинаций. Приносим свои извинения за столь большую задержку.
А еще у нас нововведение! Появился рейтинг ИТМО всех участников (спасибо Aksenov239 за него). Он также выложен на сайте