Что-то никто не пишет, напишу сам...
Четвертьфиналы Украины (они же студенческие областные, они же предварительные перед проводимыми в Украине четвертьфиналами ACM ICPC) запланированы на Сб 20.04.2013. В данный момент приказ, наверно, ещё не подписан, но вероятность изменений даты очень мала.
Полуфиналы Украины (они же проводимые в Украине четвертьфиналы ACM ICPC) запланированы на сентябрь. Не смотря на то, что ранее шла речь о том, что прошлый раз сентябрь был исключением и что их вернут в апрель--май.
UPD: Приказ наконец-то появился, скачать можно тут.
UPD: Появилось расписание. Собственно тур с 10:00 до 15:00, но учитывая этап "здравствуйте товарищи", жеребьёвку и т.д. приходить надо раньше. На сколько раньше -- решает местный оргкомитет 1-го этапа.
Вообще гениальный выбор времени проведения 1/8...
Трудно было выбрать время проведения, которые бы перекрывалось с бОльшим числом контестов. Хотя, вероятно, всем плевать:(
По поводу 1/4 (получившей название "Полуфинал Украины") — мне нравится такое время проведения. Хотя оно, кажется, тоже перекрывается с несколькими соревнованиями:) Но это лучше, чем проводить весной.
Лично мне начало сентября не нравится главным образом трудностями с оформлением командировок. Может оно глобально и мелкий фактор, но лично у меня убивает огромнейшее количество времени, причём особо бездарным образом.
Ну, и именно в этом году — ещё тем, что ChNU team в сентябре уже не может выступить старым составом. Но то такое, высшее руководство ACM ICPC осознанно делает ICPC не профессиональным спортом.
По поводу ChNU team — что-то я не понял логики) Если это не секрет, можно подробнее, что там за история? Если они проходят по правилам на этот сезон — то они должны проходить на все вплоть до финала. Если же не проходят — то каким образом принимают участие в первом этапе?
Или там что-то в стиле "для продолжения участия надо идти в аспирантуру"?
По поводу профессионального спорта — в данном случае речь идет о соревнованиях с конкретными ограничениями. А не о целом виде спорта. Есть ведь множество аналогичных соревнований без ограничения на возраст участников. Если бы руководство ACM ICPC взялось переводить все в русло профессионального спорта, то надо было бы менять очень-очень многое в организации и проведении соревнований.
Именно "для продолжения участия надо идти в аспирантуру". Что, правда, в данном случае вроде как всё равно не планируется...
А, кстати, это что же — все годы (кроме единственно позапрошлого) была подстава так подстава для всех, у кого планируется, но зачисление происходит позже самых первых чисел сентября?..
Хм... Плохо что опять в сентябре 1/4... Хотелось по нормальному, весной на 1/4 попасть, другой город увидеть.
С моей точки зрения нормально! Более равномерно распределяем олимпиады и больше времени подготовится к 1/4
Подскажите, пожалуйста, как зарегистрировать команду. Хватит ли для этого пройти регистрацию на http://icpc.baylor.edu/ ? И как указать софт, который хотелось бы видеть на нашем компе во время олимпиады?
Кроме регистрации на http://icpc.baylor.edu (именно регистрации команды на соревнование), по правилам надо также отослать/сдать лично ещё анкету региональному координатору. Точного формата анкеты на данный год лично у меня пока нету. Насколько понимаю, официально он появится одновременно с приказом. Насколько понимаю, теперь это должна быть не та огромная анкета с паспортными данными которая была несколько лет назад, а примерно та же инфа что для регистрации на сайте бэйлора минус домашний адрес плюс номер студака.
Кто является киевским координатором — не знаю. Неофициально слышал, будто задержка с приказом именно из-за неопределённости с киевским координатором. Но может сейчас это уже неправда.
Новым координатором Киевского региона будет Глазунова Елена Григорьевна, декан факультета компьютерных наук и экономической кибернетики Национального университета биоресурсов и природопользования. Первый этап в Киеве играется на трех площадках — Национальный университет им. Шевченко, Национальный университет биоресурсов и природопользования, Национальная академия управления. При регистрации команды на новый сезон нужно будет указать один из университетов. Софт при регистрации указать нельзя. Совет — пообщайтесь лично с координатором первого этапа в том университете, где планируете участвовать в соревнованиях, и узнайте у него, какой софт будет на компьютерах участников. Возможно, они пойдут Вам на встречу и поставят то ПО, которое Вам нужно.
Приказ наконец-то появился, скачать можно тут.
На всякий случай, если кто-то еще не знает — сегодня (17.04) пробный тур. Начало в 16.00.
У нас наверно не будет пробного) другая олимпиада щас проводится. И вообще, почему так рано?
Это шутка такая?.. Мне сначала было смешно, но потом я вспомнил, что мне в этой системе через 3 дня контест писать...
Итак, решаемся писать пробный тур. Половина серверов не работает... Другая половина работает независимо, регистрация и мониторы — отдельные. Ну что ж, будем использовать оба, и южный и западный. Раз так можно) Ладно, регистрируемся, логинимся. Залогинились. Хм... Серверное время отличается... Ладно, не столь важно, мелочи. Во время контеста забавно было наблюдать, как разница сначала несколько секунд, потом почему-то на 15-20 минут выросла почти до четверти минуты, потом опять упала до нескольких секунд.
Ну что же, нам серверное время не помеха! Приступаем. Хотя нет, контест еще не начался. Полазим по серверу. Лазим-лазим... Забавно, ejudge по древности сборки только немного уступает моим занятиям АСМ и лично мне. Заходим на другой сервер — то же. Хотя нет, не то же. ejudge здесь на год старше, и версия другая.
Появляются задачи. Оказывается, в системах еще и компиляторы различные. Вероятно, если поставить везде одну и ту же версию компилятора, то соревнование получится слишком скучным и предсказуемым. Ладно, не так уж важно. GCC — он и в Африке GCC, решаем...
17 минут позади, первые 9 задач решены. Открываем последнюю. Сабмит, тупой баг, WA. Исправили, сабмит, опять красненький цвет. Стоп. Уже не WA — Check failed. Для гарантии спамим сервер еще несколькими сабмитами, результат тот же. Хм. Багнутая задача? С интересом идем на другой сервер. Сабмит, АС. Странно немного... Пишем клар. Приятное удивление от того, что на клар даже кто-то отвечает, тур ведь пробный. Ну и что же нам ответили?.. Упсь, задача багнутая, авторское решение дальше 7 теста не проходит, проблема решается. А у Юга другое авторское, что ли?.. Как потом окажется, проблему не решили и до конца тура, но черт с ней.
Что еще надо сделать на пробном туре? Правильно, проверить все, что только можно проверить в этой системе, от быстродействия до цвета подсветки различных вердиктов. Посылать решения с делением на 0 мне уже было немного страшно, после всего, что я увидел до этого. А то еще потом окажусь виноват в падении системы :D Ну хотя бы протестирую быстродействие системы.
Тестирую, тестирую, все очень круто... Захожу на другой сервер, сабмит — код, который работал 0.4, получает ТЛ (при том ТЛ даже не на худшем из тестов, судя по отчету из прошлого сервера). То ли машины ооооочень сильно отличаются по конфигурации, то ли я написал настолько специфический код, что он сортирует вектор интов под разными версиями GNU C++ с разницей в быстродействии в 2.5 раз?..
У нас точно в суботу 1/8 финала первенства мира?.. А то у меня такое ощущение, что это какая-то командная тренировка в полевых условиях, не более того.
По поводу быстроты работы: у нас вот несколько лет назад организаторы не прописали -O2 :)
В итоге программа со строчкой
vector<int> a[100000];получала TL. При пустом main.В этот раз с мыслей "ну чего мы там не видели" и пересекающимися делами пропустили пробный, так что спасибо за рассказ О_о Кстати, я правильно понял, что код потлешился не на южном?
Да, на южном.
Код, на котором было видно различия, выглядел примерно так:
ну или что-то в этом роде
и тестировался на задаче А+В в системе.
Юра, я только что затестил, сколько сложений проходит на крымском сервере и на нашем — у нас в полтора раза больше (при том, что наш настраивали ногами слепые сантехники). Так что пропих приближается, пропих приближается...
Ну, сейчас вы совсем мой сервер запинаете :). Да, старичок он у меня, давно уже трудится. А сколько на нем уже контестов было! Сколько раз ваша команда на нем соревновалась? Раз 5-8? Чтобы облегчить "пропих" :), на всякий случай сообщаю, что опция -О2 задана. Кстати, Олег, серьезно, если есть вопросы по серверу, и,особенно, полезные советы пожелания, которые нужно учесть послезавтра на контесте, напишите мне об этом на почту. Я сделаю все возможное.
Александр Иванович, не хотел пинать, просто очень удивился, когда увидел такие результаты, я-то думал, что наш сервер очень медленный (недавно там А+Б на Джаве нельзя было сдать, потом что-то покрутили и стало нормально) — это чисто эмоциональная реакция. Если чем-то мог задеть Вас, простите, не хотел.
Я думаю для С++ дело совсем не в настройках сервера, а в железе, с явой то понятно, там у машины что-то глюкнет и ищи сиди) А так ТЛ всегда стояли грамотно (те 0.2 сек, конечно, исключение, чтоб их:)
А вот и нет. Сервер-то по любому на виртуалке стоит. И одним из этапов, когда нам фиксили Джаву, было то, что и на С++ решения стали очень нестабильно работать — время работы случайным образом прыгало от 0.06 до 0.8.
версия 2.3.24+ (SVN r7037), дата компиляции Fri Oct 5 09:53:20 2012. - это про сервер южного региона. Собран всего лишь полгода назад. Это очень древняя версия?
Что Вас не устраивает в этой версии конкретно? И что есть в более поздней версии, чем Вы не смогли воспользоваться в установленной?
Результаты контеста, который состоится 20 апреля подводятся ПО ОБЛАСТЯМ, даже не по регионам. Это значит, что, например, команды в Одессе будут соревноваться только между собой. И конкурировать за право выхода в полуфинал Украины одесские команды будут только с одесскими командами, а львовские со львовскими. Нужно ли в этих условиях синхронизировать время на сервере, который расположен во Львове, и сервере, который расположен в Симферополе, если результаты олимпиады во Львове никак не влияют на результаты олимпиады в Симферополе или Запорожье? Нужно ли использовать одинаковые по своим характеристикам серверы (а, главное, возможно ли)?
Про задачи. Все задачи корректны, авторские решения проверены не один раз. Задачи готовил я, проверял Александр Миланин. С задачей J все нормально. И Вы могли в этм убедиться, увидев, что на южном сервере ее сдавали. Просто на западном сервере, скорее всего, допустили ошибку при выборе чекера в системе ejudge, когда ставили задачи. Об этом говорит ошибка Check failed. Дальше седьмого теста не проходил полный перебор, который был в наборе авторских решений для того, чтобы можно было выставить тайм-лимит.
Мне очень жаль, что Вы не смогли поучаствовать в пробном туре на сервере вашего региона и Вам пришлось проверить работу серверов всех пяти регионов (или смогли, тогда зачем нужно было "лазить" по серверу южного региона?). Надеюсь, во время основного тура с вашим сервером все будет в порядке. Удачи в основном туре!
У меня ни в коем случае нету претензий к авторам задач. Тем более, что тур пробный. Даже приятно было, что в системе кроме А+В есть еще задачи, и я за это благодарен))
Просто эти мелочи очень настораживают. Местами вызывают улыбку, местами настораживают. Да, авторы задач не виноваты в том, что при заливке их на локаль — кто-то натупил и задачу сдать теоретически невозможно. Но где гаранитии, что кто-то опять не натупит — но уже перед основным туром? Мало ли что. Если все более-менее централизовано — в случае ЧП понятно, кто виноват. И в прошлые годы вроде бы все получалось более-менее централизовать. А если делать кучу "независимых соревнований", с минимальным контролем из центра и максимальной независимостью, то и шансы на чьи-то весьма неудачные ошибки — сильно возрастают.
Да, формально — речь идет о разных соревнованиях. Которые друг к другу не имеют никакого отношения. Можно было вообще разные задачи дать (только ведь понятно, что составлять лень, на всех нету ни идей, ни времени). Но что имеем на практике? Кучу традиций, которые в эти "разные соревнования" не вписываются. Начиная от банальных просьб в аудитории соревнований "выведите нам общую таблицу по Украине", и заканчивая гордыми рассказами деканов/ректоров "а у нас вот команда заняла n-ное место по Украине" (и не важно, условно говоря, что у команды по задаче зашел квадрат, который в остальных регионах падал на 20% тестов) и такой банальностью, как обсуждения на codeforces после контеста "о_О как вы там куб в тл пихнули?".
Традиционно в последние несколько лет соревнования были максимально похожими между собой; и это, как по мне, в интересах всех — хотя бы из-за возможности объективно оценить расстановку сил.
Суббота покажет, как система в этом году выдержит проверку боем... Только пока что у меня первые впечатления — не лучшие. Без излишней критики с моей стороны — это просто мои личные впечатления.
А за пожелание удачи — спасибо) Но мне она не поможет)
что было в 28 тесте в С?
4 94 0 0 0 1 1 0 1 5 0 0 1 2 0 1 10 1 7 0 0 1 14 0 1 16 0 1 8 0 1 20 0 1 18 1 13 1 22 1 3 0 0 1 27 1 28 0 0 0 0 1 33 1 32 1 31 0 1 38 0 1 40 0 0 0 1 43 1 34 1 44 1 42 0 1 49 0 1 51 0 0 0 0 1 56 0 1 58 1 54 0 0 1 53 0 1 61 0 1 66 1 62 0 1 55 1 69 0 0 0 1 72 1 64 1 74 1 73 0 0 0 0 1 82 0 1 84 0 1 80 1 81 0 1 86 0 0 1 92 0
спасибо большое)
По поводу тестов пишите мне в личку. Завтра опубликую разбор задач
А есть ли ссылки на разбор прошлогодних задач 1/4 и 1/8 финала? Буду очень благодарен.
Здесь
А когда появится тренировка по этим задачам?
готово
Спасибо
А где можно результаты посмотреть, в частности для киевского тура?
Здесь
а будет ли дорешивание открыто и будет ли общий по всем регионам борд?
Да, завтра открою дорешивание и сделаю общий борд по всем регионам. Как только разморозят результаты восточного региона, сразу выложу и общий борд.
UPD. Готово
Вот саморобный общий борд.
Результаты восточного региона взяты с ejudge.
Внеконкурсные учасники никак не обработаны.
UPD: Добавлен южный регион. Ссылка. (Версия без команд, TeamName которых содержит символ "*")
Южный регион забыли=)
Результаты восточного региона еще не разморожены. Будут разморожены завтра
Спасибо)
К сожалению, западный недоступен. Кто-то может осветить первые мест 5?
http://olymp.franko.lviv.ua/contests/standings12.html
У кого какая асимптотика в Н? У нас n * ln2(n) со сливанием множеств из детей, в множество для родителя. Но что-то, мне кажется, можно легче.
А как вообще реализовать сливание множеств из детей за разумное время?
Можно NlogN(Мы сдали нлогквадрат)
Идея такова: Для начала построим эйлеров обход. Далее для каждой вершины посчитаем значение, которое сделает какое-то ребро критичным в результате выпуска сигнала из нее. Это можно сделать перебрав все ребра и модифицируя отрезки в дереве отрезков построенному по эйлеровому обходу. То есть например вес ребра l, размеры компонент на которые дерево делиn вершины — с1, с2. Тогда одному поддереву надо сказать, что ответ для всех его вершин хотя бы с2*l, второму — с1*l.
Теперь еще раз пробежимся по всем ребрам. В одном поддереве, как в прошлом абзаце, будем искать, для скольких вершин максимальное значение = l*c2, во втором = l*c1. Просуммировали, обновили максимум. Такое можно написать NlogNlogN(дереево merge sort), либо за NlogN(храним в дереве merge sort хешмапы, либо строим персистентное дерево отрезков )
Расскажи про вашу идею попобробнее пожалуйста.
Можно то же самое, только с обычными мапами и не строить никакого эйлерова обхода явно. Просто для каждой вершины найдем максимальное ребро когда эта вершина является корнем. После этого запустим второй dfs и для каждого ребра будем хранить мап всех вершин, которые ниже его. Ну и при помощи него посмотрим, для скольки вершин это ребро является максимумом.
А если вершина, для которой это ребро является критичным, находится выше ребра по дереву?
У нас есть мап всех вершин, которые ниже. Также мы можем завести мап вообще всех вершин. Значит, количество вершин с данным значением, которые выше по ребру равно количеству таких вершин во всем дереве минус количеству вершин ниже по ребру.
Блин, точно, у меня похоже, но я перемудрил, что считаю критичности рёбер в конце, а не сразу в дфсе, спасибо)
Первую часть вроде бы можно без эйлерова обхода и дерева отрезков, за линию.
Сначала для каждого ребра посчитаем, какое на нем будет напряжение, если импульс придет "снизу" (с поддерева) и какое — если "сверху" (снаружи поддерева). Вроде бы без проблем считается в dfs c размерами поддеревьев.
Потом для каждого ребра посчитаем, какое максимальное напряжение на ребрах в его поддереве можно достичь, если импульс придет "сверху". Вроде бы тоже просто, решаем задачу на поддеревьях и берем максимум из нее и импульса на этом ребре.
Потом посчитаем, какое максимальное напряжение можно достичь, если пустить импульс из поддерева даного ребра "вверх". Это будет максимум из значения на самом ребре, значения "максимума вверх" на предке, и значений "максимумов вниз" на других сыновьях предка. Если хранить первый и второй максимумы вниз для каждой вершины — тоже считается за линию.
Теперь вроде бы можно посчитать для каждой вершины "ответ" — какое максимальное напряжение будет, если дать импульс на нее. Этим ответом будет максимум из "максимума вверх" по ребру в ее предка и "максимумов вниз" по всех ребрах в ее потомков.
Не уверен в правильности выше написанного, так как сам не сдал, но выглядит правдоподобно) Если что-то не так — скажите. Дальше задачу сводим к тому, что нужно для каждого ребра посчитать, у скольких вершин в его поддереве ответ равен напряжению на этом ребре "снизу вверх" и у скольких — "сверху вниз". До этого места я худо-бедно и с багами, но написал на контесте, а здесь застрял на слиянии map'ов по поддеревьям сыновей в dfs.
Кажется один в один наше) А по поводу слияний, не знаю будет ли тебе полезным код, но я делаю так, и там вообще негде запутаться:
typedef map<long long,int> maplli;
...
maplli* merge(maplli *a,maplli *b)
{
if (a==0) return b;
if (b==0) return a;
if (a->size()>b->size())
swap(a,b);
//тут собственно слияние какое нужно, проходом по структуре а
return b;
}
Вот, а потом в дфсе, когда переходим к потомкам, делаем
g[k].mp = merge(g[k].mp,g[to].mp);
Ну и обрабатываем листья, после цикла прохода по потомкам:
if (g[k].mp==0) g[k].mp = new maplli();//Понятно что вместо new лучше pull мэпов юзать
Угу, спасибо. Ну это вообще facepalm.
Когда я добрался до этого места, у меня оставалось минут 20-30, и я сначала пробовал найти какой-то встроенный merge (мало ли что там в С++ есть, раньше ведь не пробовал :D), потом свой написал криво...
По поводу того, что надо делать swap по размеру — это я краем уха слышал где-то))) Вроде бы понятно, что таким образом можно достичь оценки времени в nlogn вместо квадрата.
А что с памятью?
Перед выходом из вершины в dfs надо удалять map'ы для всех ее сыновей? Иначе, кажется, квадрат по памяти получается — если граф цепочкой, то каждая вершина будет в map'ах всех предков.
Ну если у нас перекладываний O(NlogN), то квадрат памяти никак выйти не может :) Если хочется иметь линию памяти, то после перекладывания можно очищать второй map.
Кажется, понял.
Волшебная строка swap(a,b);, фактически, будет делать то, что я предлагал делать вручную. Если map сына больше, чем map отца, то мы переставим их местами — и, таким образом, не только выиграем по времени, но и испортим map сына. Так что после выполнения всех операций для графа-цепочки, у нас качественный map будет только для корня, а для остальных вершин — битые пустышки, и поэтому квадратом и не пахнет.
Блин, как все красиво получается. А я в очередной раз неловко ощущаю собственную неполноценность)))
У нас совсем другое решение, я так понимаю похоже на то, что Ярослав написал) Сначала для каждой вершины посчитали, какая максимальная критичность, если из неё запустить сигнал, это дфсами за О(н). Теперь будем хранить мэп, который для каждой критичности хранит кол-во вершин с таким значением. В конце пройдёмся по всем рёбрам, и для текущего ребра к его кол-ву прибавим то, что хранится в мэпе и соответствует критичности ребра, которая направлена от предка к потомку. Таким образом мы учтём все вершины, но, возможно, что вершина с такой критичностью находится в поддереве ребра, тогда нам не следовало её прибавлять, ибо для этой вершины критичность этого ребра другая(ребро направлено от потомка к предку). И кроме того может быть ситуация, когда вот эта обратная критичность является максимальной для вершины из поддерева ребра, и нам надо всё таки посчитать такую вершину для данного ребра.
Вот тут появляется log2(n). Для каждого поддерева поддерживаем мэп с количеством критичностей, когда поднимаемся по ребру из дфса, мы, если надо, отнимает у него кол-во его прямых критичностей(от предка к потомку) и добавляем кол-во обратных.
Вот такая запутанная штука получилась.
Не могу не отметить проблемсет. Он мне понравился в первую очередь тем, что был направлен на то, чтобы ранжировать команды из середины таблицы. Это имеет первостепенную важность на таких соревнованиях и выгодно отличает проблемсет от прошлогоднего. И, конечно, топ-команды не остались обделёнными. Но их грамотно ранжировать — это уже задача последующих этапов. Авторам спасибо!
Что-то и мне захотелось написать, что-то о первом этапе.
Задачи были нормальные, но я считаю, что писать их на русском, а потом коряво переводить на украинский – это не правильно. Мне-то все равно, но на левобережье и читают и говорят больше на русском. Уж лучше бы английский вариант распечатали.
Я абсолютно не вижу смысла проводить первый этап весной, во-первых слишком большой разрыв до второго, а во-вторых никто мне так и не смог объяснить его цель. Все говорят «для массовости», массовости чего, неужели уже непонятно, что количество мест в финале не зависит от массовости «украинских» команд? Зачем проводить первый тур, а потом думать, как брать школьников поступивших в сентябре и куда девать аспирантов? Если хотите , то проводите первый тур в сентябре, второй в октябре а третий в ноябре, тогда головняка явно будет меньше.
Зачем писать первый тур командам из КНУ, Соболям и т.п., неужели кто-то сомневается, что они пройдут дальше? И, по-моему, это наоборот отбивает охоту у новичков участвовать. Итак ясно, что на второй этап поедут все кто туда и так бы поехал. Если так хочет т.Мисюра, а кроме него я так понимаю всем все равно, то пусть проводят первый тур только для не профильных вузов, пусть они там выступят, а лучшие попадут в сентябре в полуфинал, а те же кто на полуфиналах окажется с нулем, пусть на следующий год начинают с первого этапа.
Абсолютно никак не организован, безынициативно и неинтересно первый этап на местах, может быть поэтому его тоже не стоит делать. Я вот слышал, хотя не пригласили(я так понял приглашали только по блату), что Неспирный с командой организует открытый кубок Донецка и еще когда-то был decoded во Львове, так может лучше вместо первого этапа что-то такое организовывать для не нулевых команд?
Мне не совсем понятна позиция ведущих АСМщиков Украины по поводу количества мест в финале от нашего региона, или кто-то считает справедливым, то что не прошла команда из Одессы? Почему ВСЕ МОЛЧАТ, что делал т.Мисюра, чтобы этого не допустить? Он Директор или КАК? Он должен быть костьми лечь, но ребята должны были попасть, ну и что, что они не с его вуза!!! И почему никто из лидеров нашего движения не поддержал ребят, неужели всем все равно??
Надо срочно что-то в этом отношении менять. Предлагаю, обсудить на встрече директоров следующее предложение, параллельно в виннице и бухаресте пишется финал нашей зоны, те кто попал в десятку, но не прошел по квоте региона допускаются для участия в ниирке, он проходит несколько позже, и претендуют на выход оттуда. Вы скажете, зачем россиянам это нужно, а для того, чтобы была еще более сильная зона, чтобы выделялось еще больше мест и чтобы все медали забирал только ниирк, усиленный украинскими командами.
По поводу "КНУ, Соболей" — я сам не особо обрадовался такому расписанию и обязательному участию, так как из-за 1/8 пропустил двойной онсайт, но я считаю, что в целом это правильно.
Относительно КНУ — у них ведь главный вопрос не в том, кто насколько крут на фоне региона, у них борьба за квоты университета, или я не прав? Не знаю, сколько у них мест на 1/4, но со стороны показалось, что среди их команд, начиная со второй, интрига есть, и ощутимая.
Что сказать о тех, у кого интриги нету? Вообще-то, половина, если не больше, серьезных команд отнеслись к 1/8 без особого интереса, и писали или очень расслаблено, или в составе 2 или даже 1 человека.
Но само участие крутых команд в 1/8 — я считаю не только не вредным для новичков, а, наоборот, полезным. И Вашу логику понять не могу. Если объясните лучше — буду благодарен. А пока что опишу свой взгляд на ситуацию.
Вот представляем картину, приходит команда (кстати, кто, по Вашему мнению, "новичок"? сколько задач у "новичка" на таком проблемсете? 2? 3? 5? 7? 9?) на соревнования. Решают свои несколько задач. И видят, что есть ребята, которые решают ощутимо лучше. Как они должны отреагировать? В моем случае, в субботу после 1/8 было много злости, гнева и ярости из-за того, что меня и мою команду размазали по стенке:) В случае более уравновешенных людей, вероятно, будет что-то в стиле "ого, они решают лучше... значит, можно лучше... есть куда расти... надо тренироваться и работать над собой". Оба сценария (как "ярость", так и "пример для подражания"), как по мне, очень позитивны, потому как хорошо влияют на мотивацию, а следовательно — и на дальнейшие результаты этих ребят. В результате, они будут над собой работать все время до 1/4... Кстати, с мыслью о том, что надо работать и можно многого достичь за это время, потому что оно есть... А если бы 1/4 была через 3 недели после 1/8, то многие бы подумали "да ладно, черт с ним, все равно ничего не успеем выучить за 3 недели, будем готовиться уже к следующему сезону"... и подготовка эта будет положительно влиять на общий уровень команд региона — и на силу региона. А отсюда квоты и остальные плюшки.
А теперь другой сценарий. Приходит команда-новичок на 1/8, а там нет топовых (хотя топовых у нас и так на весь SEERC с натяжкой 2 команды наберется), почти топовых, немного топовых, хороших, круче средних и вообще хоть немного адекватных команд. Решают эти новички все те же несколько задач — и становятся едва ли не победителями. Или вообще победителями. Что в этом такого позитивного? Я вижу 2 возможных исхода. Или реакция "ого, да мы крутые, нам и тренироваться особо не нужно, мы уже сейчас в топе", после которой быстрый рост результатов бывает не очень часто, или же это были те самые новички, которые в первом сценарии поняли бы, что это не их профиль, а здесь у них появилась мысль о том, что у них что-то получается, и надо тренироваться. Казалось бы, второй пример — хороший, ведь эта команда будет готовиться к 1/4, окрыленная успехом. Только вот на 1/4 их морально уничтожат, потому как там уже будут "те самые" команды, в которых любой участник сольно за полтора часа, попивая чай и смотря параллельно сериал, решит больше, чем эта команда за весь 5часовой контест. А раз мы говорим о том, что тотальное избиение у нашей команды-примера резко снижает желание принимать участие в соревнованиях, то какая разница — потренировались они до 1/4 и забили на АСМ, или же они забили бы сразу после 1/8?
Не знаю, кто соблюдает квоты на 1/4, но в прошлом году КНУ было представлено семью командами, т.е. столько сколько захотели ведь их регион проходит у них же.
Поэтому никакого стимула писать одной ногой сильным командам четвертьфинал нет. И есть смысл в нем участвовать только новичкам, тем кто решает за 5 часов несколько задач для того чтобы у них был стимул пройти в полуфинал, а там есть возможность попасть во вторую половину таблицы и пройти на утешительный финал. Все те кто в полуфинале не пройдут ни в один финал, должны со следующего года начинать с первого тура.
Кроме того, вот например есть ВУЗы которые прошли в полуфинал 5 и большим количеством команд, но тут сразу возникают финансовые вопросы — смогут ли им всем оплатить поездку в другой город, причем в следующий этап не может пройти больше 3 команд, поэтому скорее всего они сами выберут тех кому стоит ехать и на что-то претендовать и без первого тура.
А если бы была альтернатива для сильных команд, где были бы задачи их уровня и можно было воочию всех собрать, то это было им бы куда полезнее чем решать задачи первого тура.
"Зачем проводить первый этап", "пусть пишут только непрофильные ВУЗы", "давайте присоединимся к ниирке" — спасибо, поржал. Бедный, бедный голодный тролль...
Ну по-моему украинским командам станет значительно проще выходить на финал, если они присоединятся к NEERC. Сейчас у вас там совсем убогая и несправедливая квота.
Либо, как вариант, поменять румынского директора SEERC на украинского и уже он будет пробивать квоту побольше. Не знаю, насколько это сложно, но то, что в прошлом году был использован винницкий сервер вместо бухарестского, выглядит шагом в эту сторону.
Я не считаю что сервер нас спасет и самое главное я не верю в то, что т.Мисюра достаточно компетентен, чтобы суметь пробить квоту, поэтому и предлагаю компромисс — дополнительный отбор.
Это юбилейное, 75-ое упоминание вами т.Мисюры. По этому поводу я подготовил маленький подарок.
mihnevsev проснулся в холодном поту. Он знал, что ему только что снился кошмар, но не хотел вспоминать подробности. Все последние ночи ему снились кошмары. Впрочем, он вообще уже не помнил, когда последний раз спокойно спал. На часах было всего 6 утра. Еще слишком рано, чтобы собираться на работу, но он знал, что спать уже не сможет. Можно посидеть на Codeforces. Увидев цвет своего ника, mihnevsev вспыхнул яростью. Он вспомнил произошедшее вчера. Шел очередной Codeforces раунд. Прямо перед сдачей задачи, придумывание, написание и отладка которой заняли добрый час, у mihnevsev в доме отключилось электричество. Разумеется, включилось оно аккурат через минуту после окончания. Рейтинг был пересчитан, и игровой аккаунт был понижен в цвете. У mihnevsev не было сомнений в причинах внезапных сбоев электроснабжения. "Проклятый т.Мисюра..." — мрачно думал он.
Не желая видеть цветное напоминание о сливе, он переключился на свой аккаунт с черным ником, и принялся беспокойно строчить обличительные посты о т.Мисюре. Как обычно, в них вкладывалась вся ярость, переполнявшая его сознание. После нескольких часов самозабвенного постинга почувствовалось некоторое облегчение. Уже можно было отправляться на работу.
Выйдя из квартиры, он обнаружил, что лифт сломан. Разумеется, т.Мисюра поработал и здесь. т.Мисюра успевал везде.
Сразу после работы был запланирован визит к психологу. Он уже не помнил, почему он должен ходить к психологу. Не знал, кто оплачивает эти визиты. Но mihnevsev втайне любил их. Психолог был одним из немногих, кто хотя бы изображал интерес к общению с ним.
- Вам все еще снятся кошмары?
- Да. Но я уже давно свыкся с ними. Думаю, можно оставить все как есть.
- Но из-за кошмаров вы постоянно плохо высыпаетесь. Это очень вредно. Если выяснить их природу, возможно, мы наконец сможем покончить с ними.
- Вы же знаете, я не люблю говорить об этом. Да и не запоминаю я ничего. Сегодня вроде снился т.Мисюра, но что именно было, не помню.
- Снова т.Мисюра. Когда же вы прекратите думать о нем?
- Как я могу забыть о нем, если он постоянно лезет в мою жизнь? Не дает мне покоя!?
- Мне казалось, всего лишь на прошлом посещении вы признали, что т.Мисюра — всего лишь плод вашего воображения!
- Да? Это плод воображения вечно портит мой лифт? Плод воображения душит ACM движение Украины? Он принес такое количество зла, что у меня нет сомнений в его реальности!..
Возвращаться домой от психолога mihnevsev решил пешком. После тяжелого разговора хотелось подышать свежим воздухом. Вечером улицы были практически безлюдны. Его это вполне устраивало — никого не хотелось видеть. Лишь изредка встречались куда-то спешащие пешеходы. В полуквартале впереди на перекрестке стоял человек, ожидая зеленого света светофора. Несмотря на приличное расстояние и то, что видно его было лишь в профиль, mihnevsev казалось, что лицо этого человека ему знакомо. Он ускорил шаг. Человек обратил на него внимание, повернул голову навстречу и улыбнулся. Кажется, они действительно были знакомы. mihnevsev почувствовал смутное подозрение. Очень странно улыбался этот человек. Это скорее была ухмылка. Да, отвратительная, ехидная ухмылка. Это был т.Мисюра.
"Я убью его" — мгновенно принял решение mihnevsev, и рванулся к человеку. Тот еще некоторое время спокойно стоял, продолжая с улыбкой смотреть на приближающегося mihnevsev, но когда бежать до него оставалось еще пару десятков метров, вдруг бросился наутек. mihnevsev не отставал. В голове его одно за другим проносились злодеяния т.Мисюры, каждое из которых давало ему новый всплеск праведного гнева и адреналина. Они без устали пробежали несколько кварталов, чудом не попадая под колеса автомобилей, пересекая улицы.
Пробегая мимо какой-то забегаловки, mihnevsev боковым зрением заметил в окне ухмыляющееся лицо и резко остановился. т.Мисюра совершенно спокойно сидел внутри за столиком, и нагло смотрел сквозь окно mihnevsev в глаза. И в то же время были слышны удаляющиеся звуки его бега вниз по улице... mihnevsev не стал рассуждать о том, насколько возможно происходящее. Он ворвался внутрь, и, расталкивая посетителей, устремился к столику, за которым виднелось ненавистное лицо. Добравшись до цели, он, не задумываясь, изо всех сил ударил кулаком т.Мисюре в лицо. т.Мисюра, не произнеся ни звука, упал на пол вместе со стулом.
mihnevsev взглянул на окровавленное лицо противника. т.Мисюра продолжал молча ехидно улыбаться. Что-то дьявольское было в этой улыбке. Что-то было не так. mihnevsev оглянулся по сторонам. В забегаловке было довольно много посетителей. Каждый из них сейчас молча смотрел mihnevsev в глаза. Каждый улыбался. Каждый был т.Мисюрой.
mihnevsev сковал ужас. Казалось, он не может дышать. Но уже через мгновение он чувствовал, как тело мчит его к выходу из этого ужасного места. Но на выходе стояла толпа людей с лицом т.Мисюры. Не было возможности обойти их. mihnevsev устремился в другую сторону. Сделав несколько случайных рывков по помещению, он забежал в уборную. Там было пусто. Оттуда некуда было бежать. За дверью слышались быстрые шаги. mihnevsev не придумал ничего лучше, чем подпереть дверь очень кстати оказавшейся в углу шваброй. Можно было ненадолго перевести дух. Повернувшись, он взглянул в висящее над раковиной зеркало. Из зеркала смотрел человек с его телом, одеждой, и с лицом т.Мисюры. Он улыбался.
"НЕТ!!!" — завопил mihnevsev и со страшной силой обеими руками ударил по стеклу. Разбившееся зеркало осыпало его градом осколков. mihnevsev мешком упал на пол и затих.
*************
- Да, просто забежал, ударил посетителя, потом рванул в туалет, заперся шваброй и разбил зеркало. Псих!
- Ясно. Мы еще зададим вам пару вопросов позже.
Офицер направился в уборную, где его напарник осматривал тело ненормального.
- Отчего умер, непонятно — осколки его поцарапали, но не более. Экспертиза разберется.
- Видел его раньше?
- Да, я помню его. Был сильным ACM-щиком. Вышли командой в финал, были фаворитами. Ну, фаворитами на второе место, конечно. Но во время финала что-то у них не заладилось. За полчаса до конца сидели с тремя недописанными задачами. Они вполне могли сдать все, они были сильны. Но вот этот самый, дебажа код, случайно коленом нажал кнопку выключения компьютера. Весь код был потерян. Они ничего не успели сдать и остались вообще без медалей. Говорили, что после этого он тронулся. Зачем-то сменил имя, и жил затворником. А потом наглотался таблеток. Совершенно случайно нашли и откачали. В результате амнезия. Никто особо не старался ему о прошлом рассказать, да и он не интересовался. Жил спокойно, и забыли о нем все.
- Да уж, интересный случай. Как его звали-то? До смены имени. Записать надо.
- Ох, и не помню уже, давно было. Хотя... Тарас вроде. Да, Тарас Мисюра.
Круто, мне понравилось, спасибо.
Эпично :)
Согласен, квота печальная. И сильным командам выходить на финал станет проще. Но справедливо ли это по отношению к NEERC, где и так сильных команд хватает? Мне кажется гораздо более логичной идея olpetOdessaONU о расширении нашей квоты. ИМХО, это будет лучше для всех. Надеюсь, что когда-нибудь так и станет. "Рано, или поздно, так, или иначе" =)
ну-ну надейтесь, надейтесь, но только век студенческих олимпиад не долог.
ржать конечно легче чем трудится над задачами
Конечно, ржать легче. Почти так же легко, как начинать предложение с большой буквы, а заканчивать его точкой. Я и не считаю решенные моей командой девять задач хорошим показателем, надо работать над собой. Только что-то я не вижу вообще ни одной решенной Вами задачи, ни одного проведенного контеста... Верить в мифические способности и/или опыт? Увольте. Хотите принести реальную пользу сообществу — деанонимизируйтесь наконец. Начните работать над решением всех этих проблем, а не писать о них в "уютном бложике". Да, часть описанных Вами проблем есть. Да, среди потока (уж извините) бреда в Ваших комментариях есть действительно неплохие замечания/предложения. Как только это перестанет быть просто словами — в числе первых стану под Ваши знамена. А до тех пор считаю все это обычным троллингом, достаточно толстым, должен заметить. Хотя... Кому (и, главное, зачем) я все это говорю?
Женя, разве ты не смотрел "Иван Васильевич меняет профессию"? Его фамилия слишком известна, чтобы он её называл=).
Какая разница, кто я, вся проблема что пытаются оценить идеи через личности, а это не правильно. Я хочу чтобы АСМ движение в Украине развивалось, а для этого нужно что-то делать, а не пытаться выяснить кто автор.
Ну Вы же сами все и сказали... НУЖНО ЧТО-ТО ДЕЛАТЬ.
А кстати в Киеве был только английский вариант условий.
Можно задачи увидеть?
А лучше сделайте кто-нибудь тренировку!
У меня тесты вида %d-input.txt и %d-pattern.txt. Чекер стандартной сверки файлов. Как мне проще всего добавить тесты и чекер к задаче в тренировке? Какой чекер загружать?
Просто добавить визардом, он сам все распарсит. Лучше добавлять с решениями. Если есть сложности — пиши в личку.
И правда, сделали бы лучше тренировку! Думаю, многим бы понравились задачи)
http://codeforces.net/gym/100184
Обращаюсь к координаторам I этапа (и тем, кто может им передать). Пришло вчера письмо от Месюры с требованием подать отчёт, значительно более развёрнутый чем ранее. Отдельный вопрос, что может стОит где-то как-то обсудить, кто что туда пишет. И отдельный вопрос, что, как по мне, стОило бы в разделе "Пропозиції щодо нагородження активних організаторів олімпіади" между прочим выразить благодарность автор(у/ам) задач за хороший, сбалансированный набор, соответствующий целям именно этого этапа.
Есть более-менее точное расписание следующего этапа. По крайней мере, по словам Сергея Петрова, именно такое расписание написано в подготовленных, но ещё не подписанных руководством приглашениях.
10 сентября, вторник Регистрация участников, поселение. Торжественное открытие Олимпиады. Ознакомление с системой проведения Олимпиады
15:00-17:00 Пробный тур.
11 сентября, среда
10:00-15:00 Командный тур, определение победителей.
12 сентября, четверг Подведение итогов Олимпиады, награждение победителей. Экскурсии.
А мне интересно, что делать если учасник команды заболеет, накануне, и его заменить некем? Где будет проводится восточный регион?
Не поверишь, но ответ на вопрос "Где будет проводится восточный регион?" содержится в приказе (см. старый UPD первичной записи блога (темы)). Для того вообще-то и выкладывался, чтоб все могли совершенно самостоятельно его читать, не дёргая других.
Насчёт "заболеет" — лучше общаться лично с координатором, т.к. широковещательно и абстрактно можно сказать лишь о том, что команда должна была ещё раньше включить в состав запасного игрока.
Спасибо за ответ, но хотелось бы на Вы общатся с вами. И нет такой привычки перечитывать блоги 5месячной давности. Логично было бы создать блог за этот год и там писать, так как один блог имеет риск превратится в глубокую яму.
Не подскажет кто-нибудь, можно ли на втором этапе, в частности — в южном регионе, пользоваться печатными материалами во время контеста?
Upd. Узнал. Ничем пользоваться нельзя=(
попробуйте написать личное сообщение 977kai
Так и сделал) Спасибо.
Есть ли у кого-либо координаты организаторов восточного региона?
Я уже писАл, где они есть. Меня за это заминусовали.
Есть у кого-то табличка?
Какая табличка?)
Разве не сегодня 1/4?
11 сентября, 10-00 — 15-00
Я что-то навтыкал. Вроде слышал летом от людей, что 8 сентября :/
До последнего надеялся поехать на четвертьфинал, но увы.. Желаю всем удачи и конечно же have fun.
Поделитесь пожалуйста ссылкой на борд.
http://olimp.vntu.edu.ua/all2.php
А когда будет таблица с окончательными результатами?
Будет ли разбор задач?
Вряд ли.
А авторы задач есть?
Мои D, E, F. Насчёт других точно не знаю, не хочу сказать случайно неправду.
Чудно.
Как решать D и F?
F -- в общем-то и планировалась скорее на пропих чем на чётко спланированоое решение. Брать и придумывать как, исходя из свойств сумм и произведений, отсекать ненужные ветви в рекурсивном переборе.
D -- вроде бы вполне чёткий и внятный алгоритм, Нейтер сначала громил его как что-то странное, потом согласился... Черновик объяснений -- https://docs.google.com/document/d/18cE-1LKimQxF3NdixlBbMei6Q9Xd9jA7SzN2YETgJTg/edit?usp=sharing
Кстати, мне очень интересно услышать объяснения тех участников, кто решил.
Спасибо! Я лично подумал что D — модификация Вашей же задачи (согласитесь, есть что-то общее в идее).
Ну у нас стандартное по D: Будем считать, что все прямоугольники добавляются на плоскость так, что их левый нижний угол будет в начале координат, а правый верхний в точке (a, b).
Нам нужна структура, которая может увеличивать значение в точке плоскости и может вычислять максимум на прямоугольнике от (0,0) до заданной точки. Когда обрабатываем очередной прямоугольник (ai, bi), сначала берём максимум на (ai - 1, bi - 1), релаксируем ответ, потом в точке (ai, bi) релаксируем найденным мааксимумом + 1.
Все решения, которые я слышал отличаются только выбором структуры, кроме решения team172, я думаю olpetOdessaONU сам его раскажет) У нас зашло дерево отрезков деревьев Фенвика, но после того, как почистили всё, что могли, и переписали обновление на нерекурсивное. Вроде дерево фенвиков деревьев фенвиков заходит легче, а ДО ДО тлешится по-любому.
Насколько я понял авторское решение, мы с Milanin придумали что-то аналогичное. В ячейке номер k вместо одного оптимального прямоугольника будем хранить множество всех прямоугольников, таких что они могут завершать некую последовательность длины k, но завершать последовательность длины k+1 уже не могут. Практически очевидно, что свойство "может завершать последовательность длины i" монотонно по i. Таким образом, бинарный поиск абсолютно такой же, как в LIS.
Теперь о структуре множества оптимальных прямоугольников. Это просто дуча, в которой прямоугольники отсортированы по ширине, а ещё в голове поддерживается минимальная высота среди всех прямоугольников, хранящихся в дуче. Таким образом, вопрос "может ли прямоугольник размера axb быть k+1-м" переформулируется как "split k-ю дучу по a и сравнить минимальную высоту с b".
Сложность n log^2 n. Большая константа дучи компенсируется тем, что у нас либо одна большая дуча, а остальные маленькие, либо все равномерные. И "плохой" тест подобрать довольно трудно.
Мы искали последовательность через тривиальный алгоритм, а переход делали с двумерным сжатым деревом отрезков (http://e-maxx.ru/algo/segment_tree, тут вроде как есть какое то описание подобной структуры).
А сколько работает авторское решение на тестирующем сервере? Можно ли посмотреть на его код?
UPD: Конечно же, имеется в виду задача F.
А какая ассимптотика авторского решения в D?
N * (log N)^2 Author time (C++ ) 0.108 , C++ TL 0.500, Java TL 1.000
Вот я никак не могу понять зачем делать TL 0,5 сек.
А еще мне интересно как сочиняются такие задачи, вы сначала придумываете решение и тесты, а потом сильно оптимизируете ваше решение под эти тесты, или, не дай Бог, наоборот?
Насчёт "зачем TL 0,5 сек" -- встречный вопрос: объясните тупым мне, Петрову (Сергею) и прочим, как при TL порядка 2--3 сек, сотням команд-участниц и десяткам тестов по каждой задаче не возникает частых много-много-многоминутных задержек? Прям-таки не происходит ни обмана вида "на самом деле там 0,2 сек, но внутренними еджаджевскими множителями превратим их в 2 сек", ни проверки на десятке компов, среди которых обязательно хоть на каком-то хоть что-то не так, как на других? Хотя с TL строго меньшими 0,5 сек я по мере сил пытаюсь бороться.
Оптимизирования решения под конкретные тесты, разумеется, нет.
Использую одновременно и придумывание логики различных возможных ситуаций (и написание различных генераторов), и очень массовые стресс-тесты -- тысячи, десятки тысяч, иногда сотни тысяч запусков, где случайные тесты делаются различными генерялками (и соответственно придуманным случаям, и чисто случайным). И никогда не делаю действия "именно этот тест именно моё решение проходит долго, так что не буду давать теста". Наоборот: выбираю и тесты с максимальным временем работы тех решений, которые хочу завалить, и тесты с максимальным временем работы того решения, которое считаю лучшим.
В этом есть что-то категорически неправильное?
Господа минусующие, извольте критиковать конструктивно.
Критикую конструктивно. 160 команд на одном сервере — это мало. Никаких задержек не будет даже с 5 сек таймлимитами и тестами из пары сотен файлов. Заявляю это ответственно, так как уже не первый год провожу на своем слабеньком компьютере кучу всяких олимпиад с использованием ejudge, включая I этап Всеукраинской олимпиады. Разве это правильно, если реализация алгоритма с использованием вектора не проходит по тайм-лимиту, а эта же реализация, но с массивом, проходит (смотрите комментарий ниже)? Я считаю, так быть не должно.
Позволю себе прокомментировать.
С одной стороны, хорошо, что Вы есть, ведь в Украине критически мало людей, готовых тратить свое время на подготовку соревнований. С другой стороны, Ваше видение того, какими должны быть эти соревнования немного не совпадает с общепринятым. Вот вспоминается Ваша задача с финального тура Всеукраинской интернет-олимпиады этого года: есть два числа длины 6, или 7 символов. Можно делать циклические сдвиги в обе стороны, домножать число, добавлять число. Может что-то упустил, но, надеюсь суть ясна. Нужно из первого числа получить второе. Сразу очевидно как делать бфсом, но это не совсем укладывается в ТЛ. Сидя на контесте я знал, что у меня не пройдет, и думал, что авторское решение имеет совсем иную природу, например что-то чисто математическое, или дп, не важно. Читаю разбор: "Давайте пустим бфс из обеих чисел, и будем двигаться параллельно..." Ок, не спорю, из-за маленького радиуса (около 20, или даже меньше) графа, в среднем, это и вправду работает быстрее, но ведь очевидно что в худшем случае это ничего не даст, абсолютно ничего! Если я не прав, то это значит, что Вы умеете решать SPP в невзвешенном графе быстрее чем за О(N+M). Вы спокойной даете задачу, которую сами не умеете решать, но через Ваши тесты пихать умеете. Супер. Зато на обсуждениях другой задачи того же контеста, Вы спокойно говорите, что я ничего не понимаю, и что это решение не линейное относительно N.
Возвращаясь к тому, каким должно быть авторское решение. У меня есть небольшой опыт проблем сэттинга, и у меня самого было две задачи, которые мне нравились, но я их не умел решать. Я мог написать решение, которое на 99.(9)% тестах работает моментально, но в худшем случае дает ТЛ. Участники всегда ждут тестов, которые покрывают все случаи, ведь так? Я в этой ситуации просто делаю абсолютно рандомные тесты и пишу жирным, об этом в условии, ведь делать хитрые тесты, на которых проходит мое решение, но которое с большой вероятностью завалит другие — это полный идиотизм и неуважение к участникам.
Ничегошеньки не понимаю, почему это вдруг я даю тесты, которые под конкретное решение! Повторю: выбираю и тесты с максимальным временем работы тех решений, которые хочу завалить, и тесты с максимальным временем работы того решения, которое считаю лучшим. То есть если я напишу решение которое работает быстро только в 99% случаев, то за (десятки/сотни тысяч) случайных запусков вылезут его проблемы, я посмотрю на те несколько тестов из (десятков/сотен тысяч) и приму решение или уменьшить ограничения на размеры входных данных, или взять в качестве авторского другое решение, и, если то другое авторское ещё не прошло десятки/сотни тысяч случайных запусков -- буду запускать новые десятки/сотни тысяч.
Конечно это не универсально. Таким методом маловероятно, например, увидеть, что QuickSort из bp\examples\dos\qsort.pas иногда (очень редко) вырождается в квадратичный. Но в подобных случаях почти всегда идеология ACM "можно сдавать несколько различных решений на одном и том же наборе тестов, и насчёт каждого более-менее быстро узнаётся вердикт" работает на участника.
Разумеется, с теоретической точки зрения тоже исследую. Просто тут мне особо не о чём говорить, т.к. там нет никаких особых фишек, а просто частично следую стандартным методам, частично придумываю совершенно бессистемно.
Насчёт именно конкретно той задачи с финала NetOI о превращении чисел. Я ведь не задаю произвольный граф во входных данных! Особенности графа определяются особенностями чётко описанных в условии задачи и не зависящих от конкретных входных данных допустимых операций над числами! Разумеется, я не мог проверить все (107)2 случаев, но я узнал (не помню, то ли совершенно точно диаметр того графа, то ли верхнюю оценку оного диаметра), и убедился, что начиная с любого конкретного числА (вершины графа) общее количество вершин на пути длины до (diam+1) div 2 достаточно малО, и таким образом именно для этого графа meet in the middle действительно даёт заметный эффект.
К вопросу о той программе, на которую Вы (Rubanenko) дали ссылку -- я не могу вспомнить, о чём это вообще, уверен, что это не моя задача, и очень сильно подозреваю, что Вы приписываете мне ответ либо Пасихова, либо Присяжнюка. Я в этом году (февраль 2013) на финал НетОИ физически не ездил, а онлайн общался на 99% насчёт своих задач, к которым эта (наверно, disted ?) не относится.
В данный момент на forum.olymp.vinnica.ua нужного фрагмента обсуждений вроде бы нету. Вам остаётся только либо поверить, либо не поверить мне, что я за все 9 лет сотрудничества с НетОИ инициировал стирание сообщений из форума только n (3<=n<10) раз, где n-1 раз было обсуждение задачи во время тура и один раз откровенные маты.
1) "реализация алгоритма с использованием вектора не проходит по тайм-лимиту, а эта же реализация, но с массивом, проходит" — категорически неправильно, когда речь идёт об алгоритме, эффективном во всём остальном. Когда в алгоритме присутствует также какая-то другая существенная неотимальность — да невозможно гарантировать, что такого не произойдёт ни при каком наборе других неоптимальностей!
Вы точно знаете, что имел место именно первый случай, а не второй?
2) я прекрасно понимаю, что Ваш опыт работы с еджаджем значительно превышает мой, и не знаю, как насчёт соотношения Вашего опыта и опыта Петрова. Но всё равно не понимаю, как "даже с 5 сек таймлимитами и тестами из пары сотен файлов" не будет задержек. Ваш сервер находится в той же вселенной, где происходит соревнование? Секунды там и тут равны по величине?
На первой волне Севастополя этого года я некоторые из задач брал готовые, и в том числе для задачи "разложение в сумму кубов" (она есть, например, на http://informatics.mccme.ru/moodle/mod/statements/view3.php?chapterid=3086#1 ) нашёл готовые тесты (99 штук), а TL под тот сервер пришлось ставить 2 сек. Так почему-то при всего лишь 30--40 командах-участницах (из которых часть ещё и на соревнования не ходила, предпочитая дальние пляжи) неоднократно получалось, что когда две команды почти одновременно слали решение именно этой задачи — до десятка решений выстраивались в несколькоминутную очередь. Если я чего-то не понимаю -- разъясните, пожалуйста (Кстати: я пока что не был ответственным за еджадж ни на одном соревновании, более серьёзном, чем полуофициальная нерейтинговая промежуточная тренировка желающих школьников перед областной, так что не спешите минусовать ещё и за то, будто я якобы не знаю, а лезу рулить.)
2-а) А риск реджаджа Вы в принципе не рассматриваете? Или всё будет помещаться в разумное время даже при реджадже?
Мне определенно нравятся Ваши методы анализа: работает на 10^5 рандомных тестах, значит правильно. Может Вам и hldot не надо, ведь любая наивная реализация запросов на дереве лихо заменит его, высота рандомного дерева — O(log(N)).
Контрпример к Вашему решению: находим диаметр графа и берем вершины, на расстоянии между которыми он достигается. О чудо! Ваш meet in the middle зайдет во все вершины о_О.
С нетерпением жду Ваших комментариев.
Это один из методов, а не единственный. К тому же, было ясно написано, что не берётся только одна простейшая случайная генерялка, а пишется несколько разных генерялок с разными продуманными распределениями.
Если граф одновременно весьма далёк и от дерева, и от полного — решительно непонятно, почему meet in the middle зайдёт во все вершины.
Возьмём, хотя бы, куб, в котором присутствуют все целочисленные вершины (i,j,k) при i,j,k от 0 до 100 каждая, причём рёбра из вершины (i,j,k) ведут во все (i+di,j+dj,k+dk) где каждое из di, dj, dk либо -1, либо 0, либо +1, но не все три 0 одновременно — максимум 33-1=26 рёбер, по краям куба меньше. Вершины (0,0,0) и (100,100,100), насколько я понимаю, вполне себе находятся на максимальном расстоянии 100, т.е. концах одного из многих-многих-многих диаметров. Запускаем BFS отдельно из (0,0,0), отдельно из (100,100,100). Не вызывает сомнения, что они встрется никак не позже, чем когда оба дойдут до (50,50,50).
Приведите пример хотя бы одной точки (куда к этому времени дойдёт хотя бы один из двух BFS-ов), у которой из трёх координат одновременно есть и хотя бы одна строго бОльшая 50, и хотя бы одна строго меньшая 50.
100 0 0.
И из какой точки ((0,0,0) или (100,100,100)) BFS придёт туда раньше, чем в (50,50,50)? По какому пути?
В (50,50,50) придёт за 50 шагов из (0,0,0), по пути (0,0,0)->(1,1,1)->(2,2,2)->...->(49,49,49)->(50,50,50), а также за 50 шагов из (100,100,100), по пути (100,100,100)->(99,99,99)->(98,98,98)->...->(51,51,51)->(50,50,50). А как попасть в (100,0,0) за шагов<=50 ?
Не, ни один из двух бфсов не дойдет до нее. И вроде бы очевидно, что meet in the middle на таком графе посетит четверть всех вершин.
А, по диагонали можно ходить. Пространственный пример с другим графом — это круто.
Но ведь он показал ложность Вашего утверждения, что meet in the middle не даёт совсем никакого выигрыша. Хотя, согласен, не доказал и истинность моего утверждения, что meet in the middle даёт такой уж большой выигрыш именно в графе той задачи.
Вернитесь сами к терминам именно той задачи, и предложите тест, который завалит моё решение с двумя встречными BFS-ами.
Факты в математике доказываются не отсутствием контрпримеров. Даже на Вашем геометрическом примере, это дает неасимптотический выигрыш. Добавьте тот факт, что ставить ТЛ меньше чем 3-4 авторских — плохо, и то, что Ваше решение по-прежнему не доказано. Имеем мой первый тезис — Ваши взгляды на то, как нужно готовить задачи не совпадают с общепринятыми.
Мои G и J. G решается декартовым деревом с модификациями, чтобы можно было переворачивать отрезки и узнавать позицию заданной вершины.
Про J: степени матрицы M можно представить в виде многочлена от этой матрицы степени b - 1, используя теорему Гамильтона-Кэли. Перемножение таких многочленов требует O(b2) времени, и чтобы найти многочлен для Mn потребуется
времени. Дальше домножаем на вектор из первых элементов последовательности, и находим формулу для ответа не используя никаких операций с матрицами.
Извините, если что-то непонятно, могу расписать подробнее с формулами и примерами.
Распишите J по-подробней, пожалуйста)
Обычно для вычисления подобных рекуррентностей составляют матрицу M такую, что
и затем используют быстрое возведение в степень. Однако для данной задачи асимптотика такого решения будет $O(b^3 \log n)$ и не пройдёт по времени. Характеристический многочлен матрицы M будет равен xb - cxb - a - d, и по теореме Кэли-Гамильтона, если в него подставить матрицу M, то получится нулевая матрица. Таким образом,
и любую степень M можно представить в виде многочлена от M степени $b - 1$. Умножение двух таких многочленов можно сделать за O(b2): сначала после обычного умножения получаем многочлен степени 2b - 2, затем избавляемся от всех степеней ≥ b. Таким образом с помощью быстрого возведения в степень можно найти такой многочлен для Mn + b - 1:
Домножим её на
и получим
Т.е. ответом будет сумма коэффициентов.
Зачетный проблемсет. Чьих рук это творение?) 70 команд с нулями — это успех, однозначно. А что, ведь это даже меньше половины участников, очень даже ничего. Это называется придите на контест и почувствуйте себя чужими на этом празднике жизни.
Кстати, как там задача С, на Java на ура заходит в 0.2 секунды, правда?)
Не знаю как насчет С, но у нас тут у одной команды линейное решение по I на джаве не зашло...
А какое там линейное решение? А то мы с мэпом хешей этих префиксов промучались, но TL на 19-ом тесте так и не побороли.
Бор же.
В Е для графа с ребрами 0-1 не заходил бфс с list, зашел с двумя queue. В I не схавало с cin и vector для бора, зашло при scanf и массиве. Из того, что вспоминается сразу. На java свет клином здесь не сошелся :)
У нас в Е обычный дейкстра с кучей защел, что-то не так)
Хм... Тем временем, по Е мне кажется, что у меня зашел N^3. Я не помню, что там у меня написано, и какие костыли я туда пихал, но мне потом сказали, что это куб.
Магия, да :)
Что такое N в оном N^3? Линейный размер макс(высота, ширина), т.е. входные данные имеют размер N^2?
Да. Идея решения вроде бы такая: запускаем bfs по графу вида "координата х, координата у", вершин порядка O(N^2). Из каждой вершины проверяем все возможные переходы — т.е. валидные ходы в каждую сторону любой длины. Их О(N), отсюда общая сложность О(N^3).
Судя по всему, отминусовавшие даже не знают, что согласно официальной теории анализа алгоритмов асимптотические оценки должны считаться от размера (в битах) входных данных, из-за чего вопрос "что такое N" не является безумно глупым -- в данной конкретной задаче могут быть разные мнения на этот счёт.
Что, уточнить — хуже, чем спорить, когда разные стороны используют разную терминологию?
У нас зашел BFS с оптимизацией небольшой( добавлять не все вершины, которые встретились на линии, а только те, которые на повороте стоят). В І линия не зашла, но были cin и векторы.
Хм, у нас и без этой небольшой оптимизации BFS зашел (кидали все вершины ), а I зашла после того как переписали вектор на массив(а сin остался).
Капитан команды сказал сразу с оптимизацией писать, так что могло и без этого пройти.
можно более подробное определение "на повороте стоят"?
Отминусовавшие, либо приведите официальное издание, в котором даётся общепринятое определение термина "на повороте стоят", либо объясните, в чём я не прав, считая, что обсуждение должно содержать такой этап, как выяснение, одной ли терминологией пользуются стороны.
Мне вот не ясно, стоит ли "на повороте" центральная клеточка вот такого поля 5 на 5:
и стоит ли "на повороте" центральная клеточка вот такого поля 5 на 5:
Это зависит от того, откуда мы стартовали, но вообще на открытом поле все равно будут добавляться все вершины.
Если более формально, то я отдельно сделал массив смещений из 4 элементов(вправо, вверх, влево, вниз). Потом в цикле по смещениям просматривалась линия(все вершины до первой стены), и если і(счетчик цикла по смещениям) делится на 2, то просматривались вершины, которые отвечают соседям данной вершины и непарным смещениям, и наоборот. Скажем, если мы идем вправо(i=0), для каждой вершины справа будет просматриваться верхняя(i=1) и нижняя(і=3).
"будут добавляться все вершины" — всё ещё непонятно, почему это должно гарантировать сложность ω(N2), которую желательно отсечь. (Перед тем как минусовать, извольте вспомнить или посмотреть в классических учебниках, что такое O, o, Ω, ω и θ.)
"массив смещений из 4 элементов(вправо, вверх, влево, вниз)" — это для каждой клеточки поля такой массив, или как-то иначе?
"которые отвечают соседям данной вершины" — в каком смысле "соседям"? По-обычному "соседям", или считаем соседями всю линию?
"непарные" = "нечётные". Не с целью обидеть, а с целью сделать смысл понятным для не знающих украинского.
Чёрт побери, при одной из разумных трактовок понятия "на повороте стоят" сложность решения получается O(N * M) (где N и M — в смысле входных данных), и оно и должно заходить!!!
При других разумных трактовках понятия "на повороте стоят" сложность решения получается всё же O(N * M * max(N, M)), и если зашло именно оно — значит, тесты всё же слабоваты, размер и TL маловаты...
Ну так почему все кругом пресекают мои попытки выяснить, какая из этих кардинально различных ситуаций имела место???
А где-то можно будет дорешать задачи?
команды в таблице, которые называются team*** и команды, у которых звёздочка(*) в конце названия, это команды вне конкурса?
В G существует решение не декартовым деревом?
Да, например в этой статье описаны другие подходы.
Где можно посмотреть условия задач?
Будет ли тренировка по задачам контеста?
Ну или хотя бы дорешивание на e-judge..
http://www.e-olimp.com.ua/ua/competitions — завтра (Сб 14.09.2013), 10:00--15:00 по Киеву (11:00--16:00 по Москве). Знаю, что не всем нравятся особенности e-olimp'а, но, по крайней мере, там соревнование будет.
Насчёт ограничений времени — предварительно планируется прикинуть соотношение времени работы некоторых решений нескольких отдельных задач на одном (e-olimp) и другом (где проводился этап ACM ICPC & AUCPC) серверах, определить некий коэффициент, и домножить TL всех задач на этот одинаковый коэффициент.
Никаких других подробностей не знаю, мне это всё написал AWPRIS, а дальнейшей телепатической связи с ним не предвидится.
Хочется проанализировать прошедший 11-го контест.
Вот и я чувстсвую, что с моими двумя решенными задачами мне в полуфинале делать нечего. Мой вуз не профильный для ACM, на меня тут вообще смотрят, как на отшельника, но когда я полтора года назад занялся спортивным программированием, я думал, что на одном энтузиазме смогу вырасти. Нет, не смог, без тренера трудно решать трудные задачи, и то, что мы — единственная команда от нашего вуза, действует на нас пагубно ввиду отсутствия постоянного давления от конкурентов и банального отсутствия возможности расспросить, как решается та или иная задача. Надеюсь поступить в КНУ в следующем году, может хоть так расти начну.
Нет, ну слушай, а разборы и скайп для кого делаются? Для того, что бы с кем-нибудь общаться не обязательно сидеть с ним за одной партой. Съезди на зимнюю школу в Харькове. Там познакомишься с людьми твоего уровня или немного выше, начнёте общаться вам будет интересно, будете расти и с вами станет интересно людям уровня повыше. Да и вообще красные — они не такие уж и бяки. Если что-нибудь у них спросить — наверняка расскажут. Когда я был сине-зелёным мне весьма прилично помог Кордубан с которым мы жили едва ли не в противоположных концах Украины. Так что давай, можешь смело начинать мучить KADR прямо сейчас, а не ждать у моря погоды :)
Отвечу в стиле mihnevsev :)
Разборы или видеоразборы есть далеко не для каждого контеста. Для многих официальных ICPC-контестов, которых я писал в качестве тренировок таковых не было. Для некоторых были материалы контестов, включая тесты и авторские решения, но с чтением чужого кода разбор задач идет намного медленнее. И наконец, где-то для трети моих тренировочных контестов я не мог найти ни разбора, ни материалов.
Даже если разбор есть (я говорю не о разборах на КФ), в большинстве случаев он отражает только авторскую идею решения в общих чертах. Он не отражает деталей, и в результате появляется типичная для меня ситуация, когда моя идея совпадает с авторской(или идеей какого-то красного, у кого я попросил помощи), однако я ловлю WA на каком-нибудь 37-ом тесте и ввиду отсутствия тестов мне так и не удается добить задачу, а это очень сильно демотивирует. Поначалу я думал, что это пройдет с опытом, но годы идут, а мелкие баги все сложнее вылавливать.
Разбор не отражает того, КАК АВТОР ДОШЕЛ ДО РЕШЕНИЯ. Если в задачах на структуры данных это не проблема: там просто прочитал условие, понял, какие операции надо уметь выполнять и выбрал из имеющихся в голове нужную структуру — вот и объяснение первой строке разбора: "Применим дерево отрезков"; то в случае того же ДП это становится проблемой. Когда разбор начинается со слов "Применим динамику dp[n][k][r] = t, где n,k,r и t — то-то и то-то", я немного не понимаю, откуда взялись эти параметры и почему именно они. И на такие вопросы автор разбора не обязан отвечать, как и любой красный, ведь получится целый роман. Научить так "правильно" думать, чтобы не ошибаться в выборе динамики, как по мне, может только тренер. Ну или большой опыт, которого у меня нет и нет времени его получать, ибо участвовать в ICPC я буду еще в лучшем случае год (гр****ые правила).
К красным-то можно обращаться, но если задалбывать того же Ярика после каждой моей нерешенной задачи, то есть каждые два дня, это даже ему не понравится.
Когда вы тут были сине-зеленым, ваш рейтинг очень быстро увеличивался :) Поэтому я уверен, что с того момента, когда ваш уровень действительно был на уровне 2-го дива и до того, как вы доросли до красного, прошло гораздо больше, чем полтора года (именно столько я занимаюсь спортивным программированием).
Команда у меня еще слабее, чем я сам. Я тренирую своих ребят, как могу, наставляя их советами из моего скудного опыта, но проблема в том, что меня самого никто не наставит, а значит нет гарантии, что и я учу свою команду правильно.
Не удивительно, если я вам показался нытиком и плаксой, но когда столько усилий не дают должного результата, об этом стоит написать.
Ну и наконец еще раз выскажу свое "фе" моим преподавателям, которые на спортивное программирование смотрят, как на нечто не достойное существования в 21-м веке.
(4). Можно попеременно обращаться к разным красным и не очень.
(5). Боюсь, что Сашины "сине-зелёные" времена по графику КФ отследить не удастся. В 2011 году он уже был весьма крутым товарищем и вскоре прошёл с командой на Финал ACM ICPC.
И прокачаться без крутого тренера реально можно. Если бы на 3-м курсе мне сказали, что я когда-то расстроюсь от того, что не пройду на Финал, заняв пограничное место, я бы страшно удивился. И уверен, что подобных примеров ещё много.
Одно дело — не пройти в финал, заняв пограничное место. Но совсем другое — уже в четвертьфинале оказаться размазанным по стенке средними задачами.
Насчет прокачки без тренера — можно, не отрицаю, но требуется очень много времени. И vitar тому доказательство.
Ну, у меня был тренер. Я бы даже сказал, что лучший на Украине. Разве что только Кордубан был лучшим тренером чем Александр Иванович. И при этом мне действительно понадобилось года 3 что бы хоть чему-нибудь научиться. Но тренер не отменяет необходимость общения. Если твой тренер не таргет — ты не продвинешься далеко занимаясь только с ним.
Жаль, что на Украине вообще нет тренеров уровня Лопатина или Станкевича.
Пользуясь случаем, хочу спросить, как же решать задачи В и Н?
В Н расписать арифметическую прогрессию, получится формула:
S = (A + B) * N / 2, где N — количество членов прогрессии, в нашем случаеN = В - А + 1. Преобразуем немного:S = (A + A + N-1) * N / 2 = A * N + N * (N - 1) / 2. Итого мы получили уравнениеA * N + N * (N - 1) / 2 = S. В нем нам известно S, а N мы можем перебрать, так как из уравнения видно, чтоN^2 < S. Зафиксировав значение N, подставим его в наше уравнение и вычислим единственную неизвестную А. Если это число получится целым положительным, то добавляем в массив ответов пару (A, A + N — 1). В конце сортируем эти пары и выводим.Не думаю, что мое решение В лучшее, но расскажу. Сначала сделаем факторизацию числа n(разложим на простые множители). Если среди множителей будут числа 11, 13, 17 и так далее, то выводим в ответ 0 и завершаем программу, так как цифры могут быть только до девяти. В противном случае у нас остается какое-то количество цифр 2, 3, 5 и 7. Обозначим сумму этих количеств через sum. Если б числа могли состоять только из этих цифр, ответ был бы
sum! / (k[2]! * k[3]! * k[5]! * k[7]!). Это формула перестановок с повторениями, так как цифры из факторизации мы обязаны взять все, а вот переставлять их между собой можем, как хотим. Однако о цифрах 4,6,8 и 9 мы забыли, а ведь числа могут и из них состоять. Каждая из этих цифр является произведением простых цифр, поэтому включая эти цифры в число, мы просто будем убирать из факторизации сразу несколько простых цифр вместо одной. Дальше моя идея была таковой: перебрать все возможные комбинации количеств "составных" цифр, вычесть из факторизации все их простые составляющие, и к ответу прибавить значение sum! / (k[2]! * k[3]! * ... * k[8]! * k[9]!). Если непонятно, напишу на псевдокоде:Ну и еще я делил по модулю 101, находя обратное число в кольце по этому модулю. Почитать об этом можно тут, я предпочитаю способ с бинарным возведением в степень. Ну вот и все, если у кого-то были решения получше, чем этот п*****, буду очень рад их услышать :)
Я делал точно так же. Вплоть до поиска обратного остатка бинарным возведением в степень =) Все, кого я спрашивал, писали эту задачу динамикой, но мне "теоретико-числовое" решение нравится гораздо больше. Оно и работать должно на порядок быстрее.
А какое там решение динамикой?
В задаче B нужно просто найти кол-во разложений числа на множители < 10. Это можно просто реализовать рекурсией с запоминанием.
Если тебя плюсуют, значит реально все плохо.
http://www.e-olimp.com.ua/ua/competitions — завтра (Сб 14.09.2013), 10:00--15:00 по Киеву (11:00--16:00 по Москве). Знаю, что не всем нравятся особенности e-olimp'а, но, по крайней мере, там соревнование будет.
Насчёт ограничений времени — предварительно планируется прикинуть соотношение времени работы некоторых решений нескольких отдельных задач на одном (e-olimp) и другом (где проводился этап ACM ICPC & AUCPC) серверах, определить некий коэффициент, и домножить TL всех задач на этот одинаковый коэффициент.
Никаких других подробностей не знаю, мне это всё написал AWPRIS, а дальнейшей телепатической связи с ним не предвидится.
Так будет ли где нибудь организована в итоге нормальная дорешка: здесь на КФ в тренировках или на каком нибудь ejudge?
http://www.e-olimp.com/competitions/2903 ?
olimp.com.ua/ua/problems#ajax:/problems/page:468 рассматривается как изначально ненормальная?
Не очень. На сколько я помню, там можно схлопотать ВА даже если просто вывести лишний пробел в конце строки.
Кроме того, как вы сами же упоминали выше, там даже тайм лимиты надо было изменять, а хотелось бы, что бы дорешка больше смахивала на условие боевых действий, тем более, что у меня в планах дорешать D, а про нее я слышала истории, когда асимптотически правильные решения, похожие на те, что проходили, в ТЛ не заходили.
На e-olimp вообще все пучком, недокументированные возможности: если решение получает ТЛ, надо его просто послать еще раз 5 в надежде на то, что ему повезет в следующий раз попасть на тестирование на более мощный компьютер. Так как тестирование производят на машинах, которые физически находятся в разных местах, и по мощности отличаются едва ли не в два раза.
Кроме того, если решение получает ВА, то тоже всегда есть надежда на то, что можно просто послать его еще раз 5-6, и оно попадет на другой компьютер, и все будет гладко — так как бывают и случаи, когда на разных компьютерах разные наборы тестов, и в зависимости от того, на какой компьютер попадет решение, оно или проходит, или не проходит.
Как по мне, это очень сильно смахивает на условия боевых действий, весьма серьезных боевых действий.
Как по мне, один из самых безнадежных сайтов...
У них, кстати, очень творческий подход к делу.
"Почему в этой задаче не оригинальные тесты? — Мы добавили свои, чтобы отсекать неправильные решения, которые проходили на оригинальном контесте. — Ладно, а вон в той задаче у вас тесты кривые. — Ничего не знаем, взяли оригинальные авторские тесты."
А что, оставить тот TL, при котором решение на e-olimp-овском сервере в принципе не имеет шансов зайти — лучше?
На e-olimp машины заметно медленнее, по крайней мере та, время работы на которой я видел в Пт 13.09.2013. На нашем (полу/четверть)финале была довольно быстрая машина. Сравнимая с теми, для которых codeforces нынче умножает время на 2. Кстати, почему все, кто сплошным потоком ругают меня и наши технический комитет и жюри, не_ругают codeforces? Тут тоже на раунде 200 у кучи задач настоящий TL 0,5 сек. Предпочитаете, чтоб вас обманывали и говорили 1 сек, только поделённая на 2?
Жду конструктивной критики.
Итак: что должны были делать на e-olimp'е вместо того, чтобы умножать TL, если их сервера значительно слабее?
Не будем именно тут и сейчас о прочих недостатках e-olimp'а. Вот предположим есть у (тебя/Вас/вас) online-judge, вот дали условия, тесты и т.д., кроме неправильного e-olimp'а, ещё и правильн(ому/ой/ым) лично (тебе/Вам/вам). Что (ты/Вы/вы) буд(ешь/ете) делать, зная, что TL под значительно более мощный сервер?
Что вы злитесь? На более слабых серверах мы делаем так: субмитим на наши сервера решения участников и жюри и выбираем ТЛ так, чтобы то, что было должно проходить — проходило, а то, что не должно проходить — не проходило. Ничего делить/умножать не надо, выставляйте ТЛ по настоящему живому серверу.
Дык тут ровно это было указано как один из серьёзнейших недостатков проведения дорешивания именно на e-olimp'е!
Или я настолько тупой, что мне недоступен истинный, совершенно иной, смысл второго абзаца того сообщения? (Правки 4, которая как раз была активна к моменту написания моих комментариев и их массового минусования.)
Как подметил выше I_love_Tanya_Romanova, сервера e-olimp достаточно нестабильны, в результате чего одинаковое решение может как получать ТЛ , так и не получать его.
Во втором абзаце лишь говорится о том, что для добивания важны стабильные сервера, дающие адекватную оценку времени, так как в задаче многое зависит именно от ТЛ, а по сему e-olimp для добивания — это не дело.
И еще в тему e-olimp. Спасибо Programist за наблюдательность, — сравните английскую версию задачи с русской, которой уже несколько лет. Один из авторов проблемсета на 1/4 постарался на славу. Старательно подготовил задачу к контесту, даже творчески перевел условие на английский. Ну а что, все равно никто не решает e-olimp, так зачем составлять что-то новое?
Мда.
У нас такое наблюдалось на областной олимпиаде школьников в 2012/2013 учебном году. Более того, представители одной "топовой" школы зарегистрировались на еолимпе за день до контеста и посдавали задачи, которые были на следующий день на контесте. Какое совпадение!
Тоже сразу вспомнил про эту задачу с еолимпа. Сейчас посмотрел свое решение, которое написано 2 года назад — там проходит такой треш с хешами на short: code
В чём конкретно тут вина e-olimp ?
И это не только одна задача такая: вот еще задача Н и я уверен что где-то видел задачу В на e-olimp.
По поводу ТЛ хотелось бы добавить что в задаче Н у нас 10^6 операций деления на 2 и взятия остатка по модулю 2 не проходило по времени, только когда деление на 2 заменили на битовые сдвиги, а проверку четности делали с помощью битового and, то получили АС.
Да уж, с баянами не хорошо конечно, но на 1/4 не столь критично, но вот на финале Украины aka SEERC подобвная ситуация уже недопустима. А насчет делений на 2, вы уверены, что это единсвтенные изменения в коде? Оптимизатор отлично заменяет это за вас, и я не слышал раньше, чтоб такое помогало.
Возможно, я очень невезучий в этом плане — но когда я что-то решаю, то у меня компилятор это оптимизировать вечно отказывается, и я получаю ТЛ из-за различных dp[i%2][j]=...
Ради интереса глянул дезассемблированный код в студии, даже в дебаге — деление на 2 заменяется арфиметичсеким сдвигом, а взятие по модулю — побитовым и с 100...012. Единственное, что заметил, он вставляет одну проверку — если исходное число отрицательное, то парой битовых шаманств делаем результат тоже отрицательным. Но если индексы всегда положительные, то бранч предиктор, по идее, такую проверку должен угадывать... Вряд ли у gnu оптимизатор слабее, но вот ниже тоже пишут, что другой оптимизации не делали, так в чем же разница?
Да, изменили только это.
Залейте тренировку на КФ, жалко что ли?
Можно хотя бы будет виртуально написать контест и посмотреть, где бы был в реальной таблице.
Я готовил только некоторые из задач, и ничем не могу помочь с остальными. Насколько понимаю, будет больше толку от кого-нибудь, кто одновременно и лично знает Шамиля Ягияева и Сергея Петрова, и имеет право создавать тренировки на codeforces.
Обсуждение четвертьфиналов плавно перетекает к Полуфиналу. Итак.
Господа, вот здесь наблюдаю странную картину. Зарегистрировались уже, вроде, все, кто могли, а University of Bucharest не наблюдается (не путать с политехом). Ни одной команды. Никто не знает, что это значит? Если что, в регионалке они выступали.
Вопрос на счет полуфинала: какие IDE там будут для любителей С++?
Ну или где такую информацию можно добыть вообще?
Давно хотел об этом написать, но никогда руки не доходили. Почему, в КНУ, только 3 команды проходит на полуфинал? Почему нету понятия квота, как в школьных олимпиадах? Получается так, что прошли некоторые команды с 2-3 задачи, а команда которая в общем 8-я, не проходит... Какой смысл им давать место на полуфинале? Или организаторы надеяться на то, что эти команды наберут форму за месяц и попадут на финал? Что они будут делать на полуфинале? Там же уровень задач намного выше.
Ну логика наверно приблизительно такая же как и с ограничением на количество участий в финале. Я так понимаю вся суть в глобализации и попытке предотвратить превращение чемпионата мира в чемпионат вуза)
Квота? В школьных олимпиадах? Ну так а почему на IOI от Китая только четыре участника едет? :)
Видимо, подразумевались квоты на школьных олимпиадах более низкого уровня. UOI — предыдущий перед IOI этап, вполне аналогично тому как винницкая площадка SEERC — предыдущий перед чемпионатом мира этап. Так что сравнение кажется более-менее справедливым (правда, если забыть о том, что отбор между UOI и IOI действительно является отбором, а на ACM ICPC такого нет).
Например, на UOI-2012 от Львовской области было 8 участников, а от Одесской — только 3. Именно по результатам выступлений областей на UOI-2010 и UOI-2011.
Насколько понимаю, нынешняя система ROI заметно отличается.
Давайте внимательно проанализируем таблицу http://olimp.vntu.edu.ua/all2.php, что мы видим(я ужасно доволен 6-ю турецкими командами, но от т.Мисюры нечего другого я и не ожидал):
На финал допущены 2 команды(Les Bonapartes и Writers), которые порешали только по две задачи, это вряд ли правильно, а если цель стимулирования будущих выступлений, то тогда стоит пригласить все команды, которые порешали от трех задач — их не так много и они не слабее этих двух.
Я не нашел в числе финалистов http://icpc.baylor.edu/regionals/finder/southeastern-europe-2013/reservations команду, которая заняла восьмое место в Восточном регионе TheBigBangTheory с четырьмя задачами. Что за дискриминация, ведь в среднем от каждого региона прошли по 8 команд, я не беру Южный так как там девятая команда тоже решила 5 задач. Я бы на месте восточного региона под предводительством Парамонова выделился бы и присоединился бы к ниирку, а т.Мисюра пусть и дальше турок приглашает за министерский счет.
И самое интересное, посмотрите внимательно на таблицу Центрального региона http://olimp.vntu.edu.ua/standings-center2.php команда DrPepper не попала в финал, заняв 6 место, а команда VNTU [Noobs v3.0] которая практически последняя в общем списке тех команд, которые решили по 2 задачи, а именно 56 место, спокойно попадает в финал!!! Я Вас спрашиваю — это справедливо???? А теперь угадайте с одного раза, чья это команда??)), конечно т.Мисюры, по-моему уже за это ему стоит устроить публичную обструкцию и выгнать, сместить с его должности!
3 команды от ВУЗа это нормальная практика, так же как и одна команда на финал. 2Furko -Вы не правильно выбрали универ для участия в АСМ, в КНУ слишком большая конкуренция, Вам надо пережить юниконов и флагов и еще быть сильнее новичков которые поступят в следующем году. Прикольнее еще и то, что на проход на финал с КНУ еще тот головняк перемешанный с рандомом(посмотрите результаты прошлого года). Вывод какой, если чел хочет выступать на асм, то нужно поступить в любой нормальный ВУЗ(где есть асмщики), кроме КНУ и спокойно и направленно тренироваться. Мало того, если Вам так нравится КНУ, то туда можно перевестись или пойти в магистратуру исчерпав все попытки асм выступлений.
И все таки, я предлагаю либо исключить команды с двумя задачами(желательно вместе с т. Мисюрой) или пригласить всех кто решил больше 3(естественно с учетом ограничений) — я думаю это будет справедливо!
DrPepper это команда школьников которые участвовали вне конкурса.
Рискну ответить. Согласно положению о Всеукраинской олимпиаде по программированию количество участников III этапа олимпиады (финала Украины) от каждого региона задается квотой. Так было всегда. И все участники Южного региона, особенно от тех университетов, которые имеют шанс попасть на финал Украины, об этом знают. Эта квота каждый год немного меняется. Тем не менее, на финал от каждого региона приглашаются команды в соответствии с квотой, независимо от количества решенных этими команднами задач. В этом году получилось так, что в квоту в некоторых регионах попали команды, решившие мало задач, тем не менее, регион будет представлен на финале Украины, и это правильно, я считаю. Это соответствует духу и принципам ACM ICPC, о которых не устает говорить Билл Поучер. Таким образом на финал Украины попали, в первую очередь, команды, вошедшие в квоту сoответствующего региона. Команда DrPepper выступала вне конкурса, она не зарегистрирована на сайте ICPC и поэтому не может участвовать в SEERC. Команда VNTU [Noobs v3.0] попадает в квоту региона. Все четко. Кроме того, оргкомитет (он есть, как ни странно, и даже принимает коллективные решения) принял решение пригласить на финал Украины (SEЕRC) на имеющиеся места команды, которые решили 5 задач, но не попали в квоту своего региона, причем, конечно же, в первую очередь приглашены те команды, которые стоят выше в таблице результатов.
А с каких соображений квота Южного региона 8, а например Восточного 7, Юг в прошлом году не был представлен на финале, а Восток был(я о команде TheBigBangTheory)?
Да, правильно приглашать команды из разных регионов для того, чтобы регионы развивались и были представлены равномерно, но так же логично приглашать команды которые находятся выше в таблице, чем команда занявшая 56 место, это не будет отбивать стимул у участников и также будет способствовать развитию регионов именно по-этому я предлагаю пригласить все команды с тремя задачами.
Согласно оргкомитета и положения, где кем и когда они были приняты, когда проводились коллективное голосование, выдвигались кандидатуры? Согласно какому документы и регламенту они функционируют? Потому что согласно положению многое можно списать на пункт который гласит, "на усмотрение оргкомитета". Мы что-то не помним не коллективного обсуждения положения, не его утверждения!
Я имел ввиду не украинский финал, а финал ЧМ.
Это всего + 5 команд, если Вы посчитаете по квоте не больше 3 команд от вуза. В прошлом году в Виннице было около 45 команд, так что все могут поместиться.
А почему именно он, всё у Вас не прозрачно!!!
Он сам вызвался
Вы сказали, что пригласили все команды, у которых не меньше пяти задач. у нас 6, но нас там нет :)
Так и есть, но я забыл упомянуть, что по положению проходит не более 3 команд от одного университета. Виноват. Кстати, mihnevsev об этом в своем посте не забыл.
Справедливости ради, делюсь новостью: сегодня от Месюры пришло письмо командам MSUSB2 и BigBangTheory: "удалось решить все организационные и финансовые проблемы относительно обеспечения участия двух дополнительных команд в мировом полуфинале. К сожалению. на это понадобилось слишком много времени..."
В общем, они могут участвовать, хотя для этого и требуется в очень срочном порядке оформить документы...
И еще:
Хотел было обрадоваться, что компактно составлено расписание http://vntu.edu.ua/index.php?option=com_content&view=article&id=360&Itemid=99&lang=uk, но беда в том, что т.Мисюра опять подстроился по румын, у них в это время теплее, чем у нас, поэтому время выбрано крайне неудачно. Мало того, что можно было бы проводить позже, даже лучше в ноябре, так опять в общагах будет сыро и холодно, ведь это как раз перед началом отопительного сезона, что неужели нельзя было сдвинуть все хотя бы на неделю позже???? Что для этого нужно иметь семь пядей во лбу??? Т. Мисюре, то хорошо, он себе дома в теплой постельке будет ночевать, а участники мерзнуть и заболевать, а ему плевать!!!! Зато турки будут жить в приличной гостинице за министерский счет, КРУТО!!!!
Нет нормального сайта олимпиады, где были бы выложены архивы задач с разных этапов, разборы, таблицы результатов, правила, положение, рейтинги и т.п., что т.Мисюра не мог это сделать за столько лет???
т. Мисюра абсолютно далек от тренировок, от решения задач, от тестирующей системы. Участники не будут знать до самого приезда о средах разработки, конфигурации машин, компиляторах — это правильно??? Стыд и позор, что нельзя выложить задачи в виде тренировки для добивания ни с какого тура, просто ему это не нужно, чем он занимается, а ничем, почему его до сих пор не выгнали, а потому что менталитет у нас такой- "моя хата с краю", всем ПЛЕВАТЬ, на то что творится в Украине!!!
Как же ты уже достал. Просто оставлю это здесь осторожно, юмор с imageboards
По поводу тепла можно не переживать так как в Виннице и еще нескольких городах Украины уже с понедельника начинается отопительный сезон, потому что стало холодно очень рано. Так что надеемся участники не замерзнут)