Только у меня веб-интерфейс не грузится?
(Обсуждение задач - после конца контеста)
UPD:
Извините, но это просто нет слов!
В 3:30 у нас было 5 сданных задач и подходила 6я. Внезано сначала ретестят Н, затем включают полный ретест и просят не сабмитить до сообщения от жюри. Ретест длится почти полтора часа, и никакого сообщения нету. Наконец в 4:40 жюри отвечает на чей-то вопрос, что оказывается, сабмитить уже можно. Впрочем, некоторые участники сабмитили во время реджаджа, но это их дело.
В теперь о совсем фееричном: задача Е, которая проходила до реджаджа, после дает ТЛ 3.. Задача Н, которая проходила до реджаджа, да ВА/ТЛ 19. При этом ограничения подкручены так, что на ней у нас не проходил достаточно оптимальный квадрат, та же ситуация в Д. В общем, не понравилось!
Хотел уточнить, как решали Е и Д и Н те, у кого она прошла? С какой асимптотикой? У нас был N^2logN и N^2 и N^2 соответственно.
А то 5 без неё сделали, единственные такие, видимо как-то просто :/
Т.е. ответом будет минимум по величинам:
i = 0..n
a[i], если оно идет влево
L - a[i], если оно идет вправо
во во, это про меня...
В целом чемпионат не понравился (несмотря на то, что мы заняли весьма неплохое для нас 5-е место среди участников самого ЧУ) - слишком много геморроя с такими мелочами, как длинные неосмысленные выходные данные, не обговоренные четко в условии критически важные моменты (например, в F вы за сколько догадались, что пара может состоять из двух одинаковых людей?). Из сданных нашей командой 6 задач мне больше всего понравилась E - довольно сложная, интересная задача. Мы решили ее при помощи DP, Z-функции и подсчета разностей значений функции ответа.
например, в F вы за сколько догадались, что пара может состоять из двух одинаковых людей?
Мы на это потратили не очень много времени, переключившись на другие задачи.
Какие у вас были хаки?
(H засылали за n^2*logn - ТЛ9, а F почему-то ловила ВА2)
>>Если такое k нашлось, то dp[i][j] = dp[i][j + 1] + dp[i + 1][k], иначе dp[i][j] = dp[i][j + 1].
Мне кажется, ты хотел написать dp[i][j] = dp[i][j + 1] + dp[>>j<<][k]. Или я не прав?
И кстати, как находить такое k быстрее чем бинарным поиском со сравнениями за O(logN)? Иначе итоговая ассимптотика должна равняться O(N^2 log^2N).
Этот пост уже можно считать "некро", но если ты еще помнишь суть описанного - ответь плз, интересно :)
значит будет писать динамику по a[i][j] - количество способов сложить наш словарь так до j символа что все корректно и последнее слово a[i][j]. теперь у нас есть слово a[i][j] и мы хотим найти все слова в которые он может перейти. Понятно что если нам будет подходить слово a[j+1][x], то нам и будет подходить слово a[j+1][y] где x<y<=n, т.к. если к последнему слову дописывать символу хуже не станет. Поэтому нам надо найти ближайшее такое слово. И так, просчитаем f[i][j] - максимальный общий пефикс i-ого и j-ого суффикса (допустим l = f[i][j]). Тогда если l < j - i + 1 и s[i + l] > s[j + l + 1], то следующего слова не существует (потому что следующее слово начинается на l букв нашего слова и дальше символа меньше нашего). Иначе замечаем если l > j - i + 1 (то есть дальше идет наше слово и ещё что-то), то ближайшее слово будет a[j+1][j+1+j-i+1], и оставшиеся случай когда l <= j - i + 1, тогда ближайшее a[j+1][j+1+l] (можно написать проще, совместить два последних варинта в a[j+1][j+1+min(l,j-i+1)]), но это ближайшее слово, поэтому из каждого a[i][j] я могу перейти в a[i][j+1] - то есть как бы взять последнее слово в своем списке и расширишь.
вкратце:
инициализация a[1][1]=1 (индеск с 1), для каждого a[i][j] делаем переход в a[i][j+1] и в a[j+1][j+1+min(f[i][j], j-i+1)] если не выполняется условие (f[i][j]<j-i+1 и s[i+f[i][j]] > s[j+1+f[i][j]]).
P.S. Прошу прощения за много букв.
На скоко я знаю по правилам АСМ это недопускается - был прециндент на полуфинале, и в итоге оставили ОК.
0 0 1 1 0
1 0 30 239 1000000
0 0 0 2 1
2
0 0 2 5 1
1 1 5 2 1
0
Case #1: Intersection contains 2 integer(s).
Case #2: Intersection contains 0 integer(s).
Если писать в unsigned int то ВА 19. Если хранить в long long а пересчитывать используя тип unsigned int - то ТЛ 10!!! (не понимаю вообще как!) В итоге засабмител 5 или 6 решения используя в различных моментах типы int, unsiged int, long long... Мы так и не поняли почему - все решения ТЛ 10, кроме 1 - оно зашло как то на шару)) Кароче полное извращение а не задача, похоже на угодай какое решение писали авторы (нахера такой ТЛ впритык тоже не ясно)
За задачу F надо руки сломать автору, потому что половину условия пришлось придумывать!
Но формат вывода это пзц, и нам еще повезло - там +1 или +2 - догадалить про 11th))
Бесят меня авторы))
Ну понятно a, b и m тоже unsigned int (когда было ВА)
Кстати, в Pascal точно можно было прописать директиву компилятору, чтобы операнды вычислялись слева направо. В C++ тоже логично было бы чему-то такому же быть. Но я его не знаю :)
А вообще здесь же огромный тир с ногами. Можно ведь ещё писать так, что операнд слева будет зависеть от результата вычисления операнда справа...
Извращение не задача а весь контест)
Плюс ко всему, насколько я мог судить из обсуждений на форуме TC и различных блогах, на финале TL обычно выставляется относительно приятный. По крайней мере, непонятно, как наличие или отсутствие модуля/long long в H могло бы при этом привести к TL (если уж это попытка устроить раунд в духе финала)
Думал над динамикой по дереву. Да так и не придумал.
Присоединяюсь к всеобщему негодованию =)
Кроме всего вышеперечисленного порадовал также СЕ по причине "Compilation timed out", несмотря на то, что на нашей машине код компилировался мгновенно. На клары в духе "Что за дела?" отвечать никто не желал, и лишь спустя эн десятков минут выяснилось, что это ML на самом деле (ошиблись кол-вом нулей) 0_о
Просто нет слов.
Посчитаем максимальный ответ для прямоугольников со сторонами не более 20 клеток = Answer за О (300^2 * 20^2).
Далее на каждом шаге проверяем, существует ли ответ Answer+EPS. Если он существует, то увеличиваем Answer на 1. Утверждается, что таких шагов будет немного и все это влезет в ТЛ. Таким образом мы сократили границы ответа для бинпоиска.
Такое решение объяснял Сергей Копелиович.
Решение до которого все додумались – это для каждой полоски за O(N log *) посчитать бинарным поиском ответ. Это решение базируется на том факте, что мы можем для полоски за O(N) проверить больше ли ответ на ней чем какое-то значение. Добавим в тупое решение такую штуку, перед тем как запускать бинарный поиск, просто проверим за O(N) можем ли мы улучшить наш текущий ответ, если можем, то только тогда запускаем бинарный поиск.
Утверждаю, что если все полоски случайно перемешать, то ожидается log_2 N улучшений ответа, а следовательно и запусков бинарного поиска. Так происходит потому, что случайный элемент последовательности будет примерно медианой, а все меньшие элементы отбрасываем, как результат размер последовательности на каждой такой итерации сокращается вдвое.
Сейчас додумал просто N*N*N*log N, не поверите, использовать выпуклую оболочку. Доказывать умею :)
а еще меня каждый раз очень радовала строка в условии:
Следуйте формату вывода, указанному в примере, как можно точнее.
Во время проведения Гран-При СПб для первого дивизиона произошло несколько существенных сбоев, повлиявших на результат раунда. В частности, Гран-При не стартовал автоматически, после ручного старта Гран-При в результате неполного перезапуска систем были установлены значения Time Limit, равные 20 секунд для всех задач. Также произошло расхождение в тестах для задач J и I (оказавшиеся в системе тесты соответствовали прошлой версии задачи с другим текстовым выводом), приведшее к пересуживанию задач, причём в случае задачи I пересуживание произошло достаточно поздно. Однако на проведение турнира для второго дивизиона эти сбои влияния не оказали.
В связи с этим жюри Открытого Кубка приняло решение считать Гран-При СПб для команд первого дивизиона внезачётным.
Наконец-то удалось написать опенкап (из 4 предыдущих в двух зачли результат в ПЗ, в двух результат на зимней школе) и очень хорошо написали (3-е место). Могли бы в 10-ку уже попасть в общем зачете и на тебе.
Во-первых, прошу прощения за технические проблемы во время соревнования: ошибку в условии B, пересуживание по I и J из-за текстовых правок в тестах, общее пересуживание из-за неправильно выставленных TimeLimit-ов. Мне видятся в них две основные причины: доделывание контеста в последний момент и недостаток общий координации. Конечно, есть и чисто технические моменты, но без этих причин большинства проблем, скорее всего, удалось бы избежать. Допущенные ошибки обязательно будут учтены при подготовке следующего чемпионата СПбГУ, который ориентировочно состоится в октябре.
По поводу претензий по задачам выскажу своё мнение.
1. В задаче F, действительно, условие хорошо было бы изначально сделать чётче. Тем не менее, ответы на стандартные вопросы прямо или косвенно следовали из условия. В каком порядке записаны биты — объяснено подробно. Является ли граф ориентированным — нет, иначе как он может быть задан половиной матрицы смежности. Может ли человек быть “другом” самому себе — да, ведь бит для этого есть, и в условии подчёркивается, что отношение “дружбы” — формальное понятие. Можно ли считать, что два одинаковых человека образуют пару — да, потому что не сказано, что они должны быть различны. Примерно этим руководствовалось жюри в своих ответах “без комментариев”.
Я считаю, что, с одной стороны, два последних момента действительно лучше бы пояснить в условии заранее, а с другой стороны, при таком условии делать по ним объявление не нужно, поскольку это нечестно по отношению к командам, решившим эти вопросы самостоятельно. Считаете иначе — объясните.
2. Общая претензия по тому, что решения с правильной асимптотикой не проходят из-за Time Limit. Одна из причин — то, что авторы чемпионата СПбГУ обычно пишут решения довольно оптимально. Считаю, что это не то чтобы хорошо или плохо — так есть, это специфика чемпионата, почему бы и нет.
Вообще, ограничения по времени выставляются исходя из того, чтобы решения жюри укладывались в них с двухкратным запасом. Это было неверно локально (не в Кубке, а в чемпионате СПбГУ) в задаче H, где решение жюри работало 1.5 секунды из 2. К моменту, когда мы это заметили, случилось уже много попыток по этой задаче, успешные среди них тоже были, и, опять же, менять ограничения было бы нечестно по отношению к тем, кто уже потратил время на оптимизацию и сдал задачу только после этого.
3. Окончания числительных в задаче J. Тут, во-первых, замечу, что английский — основной язык соревнований ACM ICPC, начиная с четвертьфиналов. Поскольку чемпионат СПбГУ (как и этап Кубка) — это соревнование в формате ACM ICPC, считается, что этот язык достаточно важен. Во-вторых, английский в качестве иностранного изучает подавляющее большинство школьников и студентов. Словом, если в команде из трёх человек нет ни одного, кто бы считал, что с числительными “elevenst”, “twelvend” и “[one hundred] thirteenrd” что-то не так — это достаточное основание для того, чтобы получить по задаче минус и задуматься об этом. Программирование тут, действительно, ни при чём. Но с таким знанием английского в англоязычном условии команда вполне может понять какое-нибудь слово неверно (реальный пример: что такое unidirectional edges?) и из-за этого решать не ту задачу. И программирование тоже будет ни при чём.
Замечу, что некоторые из тех, кто искал проблему в написании числительных, на самом деле выдавали неправильный ответ на тест n = 4.
4. Вообще вывод текста, не несущего информации. Действительно, это сделано с задумкой “как на финале”, там в некоторых задачах приходится выводить не только ответ, но и несколько слов, пробелов и переводов строки, не являющихся необходимыми. Действительно, реализация этой идеи не всегда соответствует задумке (предложения получаются не на английском). На финале также бывает, что форма слова не изменяется из-за стоящего рядом числительного. Не считаю, что такой формат вывода особенно хорош или плох. Он просто бывает, также как и формат, состоящий только из чисел.
Тем не менее, мне кажется, что у условия F, если его внимательно прочитать — только одно правильное понимание. Поэтому, если сделать объявление с пояснениями — это нечестно по отношению к командам, которые уже потратили время и отнеслись к условию внимательно.
Тут вопрос, что ценить больше — удобство контеста или внимание участников. В этом случае я пока склоняюсь ко второму.
А насчёт легенды — поскольку некоторые члены жюри действительно работают ВКонтакте, возможно, они знают, о чём говорят.
В чемпионатах СПбГУ традиционно есть задачи на оптимизацию, в которых нужно не только придумать решение с правильной асимптотикой, но и реализовать его достаточно оптимально. Да и в других контестах это бывает часто. Считаю, что такие задачи имеют право на существование.
Если команда A умеет придумывать максимальный тест и мерить на нём время работы, она не получит лишний минус, а сразу поймёт, что нужно оптимизировать. Если команда B что-то из этого не умеет, она получает лишнее штрафное время, послав неоптимальное решение. Логично, ведь B по этому показателю хуже A.
Далее, если команда C умеет находить наиболее трудоёмкие места в своём решении и оптимизировать программу именно в них, она сделает это и сдаст задачу достаточно быстро. Если команда D этого не умеет, она может сдать задачу “пропихиванием” — например, перебирая замены одних типов данных на другие, меняя eps, переставляя местами условия в ифах и циклы. Но обычно команда D тратит на это гораздо больше реального времени и штрафных попыток, чем команда C. Ну и опять же логично, ведь C по этому показателю хуже, чем D.
То есть чем лучше команда понимает, что происходит, тем больше метод тыка (“пропихивание”?) превращается в методичную оптимизацию, и тем лучше у команды результат по задаче (реальное время, количество попыток). Я считаю, что это нормально.
Конечно, это всё работает “в среднем”: какой-то команде может повезти, и она, не понимая этого, сразу напишет правильное решение, а другая соптимизирует лучше, чем нужно, а потом окажется, что на самом деле программа просто виснет на неучтённом крайнем случае. Ну так и при придумывании асимптотически правильного решения, реализации и отладке такие случайности тоже бывают.
Представляю, как на пробном туре команда решает 3 задачи:
Задача A) Определить размер кэша процессора.
Задача B) Определить тактовую частоту процессора.
Задача C) Определить, какая именно модель процессора используется на тестирующем сервере.
Потом на основании этих данных рассчитывает магические константы, которые надо будет использовать в решениях задач основного тура :)
Причем задача специально давалась, чтобы участники могли примерно понять насколько их локальный компьютер быстрее или медленнее проверяющего.
Когда я ещё участвовал в ACM ICPC, мы на пробном туре посылали Флойда, чтобы узнать, на скольки вершинах он ещё укладывается в две секунды. Как примерная оценка того, насколько проверяющий компьютер быстрее или медленнее локального — вполне работает.
С кэшом не заморачивались, всё равно не умели пользоваться.
Даже тот факт, что ни одна команда (из ~50 решивших) не сдала задачу F ни с первой, ни со второй попытки, говорит о проблемах с условием.
Мы, например, только после конца контеста узнали, что от матрицы смежности на самом деле дана нижняя половина, это легко было не заметить. А какая логика в дружбе человека с самим собой – до сих пор не понимаем, хотя задачу на контесте сдали :)
А вот скажи, пожалуйста, как координатор CodeForces по задачам:
1. Ты бы объявил по F и про то, что человек может быть другом самому себе, и про то, что люди в паре могут совпадать, так?
2. Считаешь ли ты, что из условия эти два пункта не следуют ни прямо, ни косвенно?
3. Как быть с тем, что команды, сдавшие задачу до объявления, потратили на неё больше ресурсов? Это неважно по сравнению с тем, насколько непонятно было условие?
Если считать, что условие неоднозначно (или однозначно, но не соответствует тестам жюри) — конечно, я согласен, что нужно объявлять и снимать попытки (самим или по апелляциям), это минимизирует неравенство условий для команд.
Если же считать, что условие сложно понять, но при этом оно однозначное — объявление помогает всем, кроме тех команд, которые уже сдали задачу. Считаешь ли ты это достаточным основанием, чтобы не делать объявление, и почему?
Даже любопытно, как жюри удалось отладить свои решения. Неужели путем визуализации тороидальной трехмерной шахматной доски? =)
Некрасиво, по-моему...
Ночь прошла, эмоции, вроде, должны были поулечься.
Мы теперь добиваемся, чтобы авторы окончательно раскаялись, публично посыпали голову пеплом, повторно обещали учесть все ошибки, поклялись, что "никогда больше" и т.п. ? Вопрос риторический.
Так этого термина и не было в условии)Могу рассказать ужастик в тему: если бы в своё время хотя бы один из троих человек в моей команде прочитал первое предложение в условии одной задачи, мы бы сейчас, скорее всего, готовились ехать на финал. Но, в самом деле, кто же читает первое предложение?..
В математике пара, состоящая из двух одинаковых объектов — вполне разумное понятие. Это же не множество. Точно так же, как “несколько” в олимпиадных задачах не значит “хотя бы два”.
Я и сам бы хотел увидеть эту “развитую систему умолчаний” где-нибудь записанной. Действительно, когда у жюри она n лет одна, а у участников k лет другая, возникают такие проблемы.
К формулировке задачи F это не имеет отношения.
Согласен, претензия к условию J и последующим “no comments” — по делу.
условие на русском
english problems
Если ссылка не работает (мало ли, у меня из кэша подобралось) могу куда-нибудь залить.
По-моему, приведенный в условии задачи H (и в русской, и в английской версиях условий) факт, просто прекрасен своей неоспоримой очевидностью.
К счастью, необычность задания этого ограничения большинством участников просто игнорируется, все курят^Wвидят то, что и предполагали авторы :)
Есть ли какая-то возможность скачать сабмиты, отправиленные на туре? Разумеется, нашей команды, хотя если можно посмотреть других - было бы вообще замечательно. Я склоняюсь к ответу "нет", т.к. не могу найти ссылку на вход именно в контест (который давно over, но есть вкладка "отправки"). Может, у кого-то в кэше?
Вообще наличие такой возможности было бы очень полезно, т.к. в идеале на месте написания должен отсутствовать интернет (блокироваться трафик на иные адреса) и возможность считывать флеш. Хотя на практике, на мой взгляд, выполняется это редко. Я, например, просто забыл переписать :(
http://158.250.33.215/~ejudge/team.cgi?contest_id=???? - и последние четыре циферки надо угадать.
четырепять циферок - искомые.Да, действительно все работает. И решения скачиваются. Спасибо. Еще интересно, навсегда ли так "зависают" прошедшие контесты, или через какое-то время они становятся недоступны. Например, доступны ли сейчас так контесты прошлых лет?
Они не зависают, а просто остаются в системе.
Некоторые из них потом делают виртуальными.
А уж считая только те, к которым подходит пароль от Кубка...
В прошедшие этапы можно войти, используя на opencup.ru в левой панели внизу меню “Выбрать этап”.
В прошедшие сезоны — пока только в предыдущий (в левой панели вверху — “Выбрать сезон”).
в данном случаенаоборот "запилил" = "открыл".Видимо, совсем не владею диалектом.
Раньше нельзя было зайти в старые контесты. Теперь можно. Вопрос был в том, кто и по чьей просьбе сделал так, что можно.
Вопрос: чем тогда доказывается правильность ответа на тест из условия? Авторским решением? А правильность авторского решения?
Не то, чтобы я ставил под сомнение авторское решение, но обычно так не бывает.
Конечно, не надо засвечивать идею по нерешенной задаче, но действительно есть какое-то доказательство правильности авторского решения?
Там же можно просто граф игры построить и по нему всё посчитать.
Тогда всё доказательство правильности заключается в том, что возможные ходы, описанные в условии, совпадают с теми ходами, которые делаются в решении.
Разве не так?
Накосячил, так накосячил. Смущает только, что правильность любого решения по этой задаче можно показать только на элементарных тестах, где ответ = 1. А для всех остальных тестов только поверить, что ответ - верный.
Хотя, может быть, с этим утверждением я ошибаюсь.
Хмм. Я написал для интереса решение задачи B.
Оно у меня тоже выдаёт 4 хода на сэмпл..
Как нюанс, надо рассматривать раздельно позицию при ходе белых и черных.
Интересно, я прав?
Честно говоря, я не знаю.
Насколько можно понять из каталога с задачей, ответы могли быть проверены при помощи brute force solution. Действительно, если чёрные выигрывают за три хода, то, вероятно, перебор с тривиальными отсечениями работает не очень долго. И написать его не очень сложно.