Недавно делал маленький контест в полигоне. Почти все понравилось - после выкачивания package мне было достаточно разархивировать данные в тестирующую систему и поменять xml-файл с настройками.
А не понравилось вот что: файлы с тестами, генерируемые на полигоне, имеют вид 01 и 01.a, ..., 99 и 99.a, а затем 100 и 100.a и т.д.
Если тестов больше 100, то я не могу задать в xml-ке с настройками маски входных и выходных файлов, т.к. у некоторых тестов имя состоит из двух символов, а у некоторых - из трех. Приходится писать скрипт для переименования, что не очень удобно.
В связи с этим есть предложение: добавить в полигон настройку имен файлов с тестами. Думаю, это очень несложно.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3649 |
| 2 | Benq | 3581 |
| 3 | orzdevinwang | 3570 |
| 4 | Geothermal | 3569 |
| 4 | cnnfls_csy | 3569 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3531 |
| 8 | Radewoosh | 3521 |
| 9 | Um_nik | 3482 |
| 10 | jiangly | 3468 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 164 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 159 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Раз уж тут всплыла тема шахмат, хочу предложить две забавные задачки.
В обоих позициях ход белых, задание самое банальное - мат в один ход.
Если вы считаете, что мат в один ход найдет абсолютно любой человек - эти позиции для вас!
Пожалуйста, пишите свои ответы под спойлерами!
Обновление. Вроде народ не против, так что вот еще две боянистые задачки. Правда, теперь их сложность - VERY HARD.
3). Партия из начальной позиции закончилась 5 ходом черных, когда конь съел ладью и поставил мат. update: Известно, что первый ход белых был 1. e4. Восстановите партию.
4). Из начальной позиции партия продлилась 4 хода и закончилась матом белым. Белые ходили 1. f3, 2. Крf2, 3. Крg3, 4. Крh4. А как ходили черные?
Сначала в общих чертах о раунде.
Моими задачами в этом раунде были задачи A-div2, B-div2, C-div2/A-div1, E-div2/C-div1, D-div1. Сначала я хотел провести на них контест исключительно для второго дивизиона. Однако затем мы решили провести общий раунд. MikeMirzayanov подготовил задачу про молоко, anonymous предоставил задачу E-div1. Кроме того, по напутствию RAD были усложнены Аземблер и Флаги.
По-моему, получилось неплохо для первого раза (кроме небольшого фейла с рамочками). Во всяком случае, мне понравилось. Правда, я не ожидал, что Аземблер и Флаги решит так мало народу.
А теперь разбор.
Задача A (div.2) - Восстановление пароля
Текст задачки был актуален чуть более года назад, когда свирепствовал вирус piggy.exe :) Но в то время у меня не было возможности где-либо опубликовать эту задачу.
Вот пример решения: http://pastebin.com/hMV0NcjN
Задача B (div.2) - Друзья
Возможно, некоторых смутила формулировка утверждения. Однако именно так оно звучит в книжке, из которой я его нагло скопировал :)
Т.к. вершин в графе всего 5, достаточно написать 3 вложенных цикла for (каждый цикл соответствует одной вершине графа) и проверить, что ребра между этими вершинами имеют одинаковый цвет.
Пример решения: http://pastebin.com/gswaxGmM
На самом деле ответ FAIL будет лишь в одном случае - когда в графе ровно 5 ребер и они образуют цикл длины 5 (как в тесте 2). Вот шуточное решение на эту тему: http://pastebin.com/09T0ixrJ
Задача A (div.1) / C (div.2) - Рамочки
Итак, давайте разберемся в задаче. Во-первых, заметим, что ответ всегда не превосходит 3, т.к. любое множество подряд идущих папок можно разбить на 3 прямоугольника (возможно, пустых). В первый прямоугольник мы поместим конец первой строки, во второй - все, кроме конца первой строки и начала последней (это будет прямоугольник с шириной m), а в третий - начало последней строки.
Самый простой способ решить задачу --- проверить, что ответ 1 или 2, а иначе вывести 3. Давайте рассмотрим, в каких случаях ответ меньше 3.
Итак, пусть ответ - единица. Значит, все требуемые папки можно выделить за одно движение мышкой. Вот эти случаи (в скобках показан тест для этого случая):
- первая и последняя папки находятся в одной и той же строчке (21 5 7 9);
- первая папка находится в самом левом столбце, а последняя - в самом правом (21 5 1 15), этот случай покрывает случай m = 1;
- первая папка находится в самом левом столбце, а последняя имеет номер n (21 5 6 21). Сюда же относится тот случай, когда надо выделить вообще все папки.
Теперь рассмотрим все случаи, когда ответ равен 2:
- первая и последняя папки находятся в соседних строчках (21 5 8 14);
- первая папка находится в самом левом столбце (21 5 6 13);
- последняя папка находится в самом правом столбце (21 5 4 15);
- последняя папка имеет номер n (21 5 4 21);
- столбец, в котором расположена первая папка, находится непосредственно справа от столбца, в котором расположена последняя папка (21 5 3 12). Мне кажется, это самый хитрый случай в задаче.
Если ни одно из этих условий не выполняется, то ответ равен 3.
Пример решения: http://pastebin.com/8QRytzzF
Еще эту задачу можно было писать сжатием координат и перебором, но психов среди нас нет :)
Задача B (div.1) / D (div.2) - Окончание сессии
Задача решается жадным алгоритмом. Нужно последовательно пробовать переливать из каждой бутылки молоко в любую кружку, которая для этого подойдет и в максимально возможном количестве.
В ходе процесса надо помнить, сколько молока находится в каждой кружке и каждой бутылке, а также из каких бутылок наливали в каждую кружку и куда переливали из каждой бутылки. Эта информация нужна, чтобы определять, а можно ли перелить из конкретной бутылки в конкретную кружку или нет.
Остается это просто написать - ничего сложного, как мне кажется. Единственный момент - сравнивать вещественные числа надо, используя EPS. Без этого можно получить WA на тесте 12 (50 1000 49), где из-за неправильного сравнения программы некоторых участников выдавали NO, тогда как решение существует.
В обсуждении ниже показано, что ответ можно считать в целых числах, если взять объем бутылки, равный mn. А при выводе будем делить на mn и умножать на w. Ни одно из трех решений жюри до этого не додумались :)
Пример решения: http://pastebin.com/HG5Nrxne (оно уже не такое красивое, как предыдущие, но понять, как мне кажется, можно)
Задача C (div.1) / E (div.2) - Аземблер
Меня удивило маленькое количество сабмитов по этой задаче. Достаточно маленькие ограничения на n и большое ограничение по времени явно намекали на перебор. Кроме того, интуитивно понятно, что максимальный ответ находится в районе 5.
Для получения решения необходимо хранить (например, в векторе) текущие значения регистров и перебирать всевозможные новые значения, получаемые из текущих, а затем рекурсивно запускаться с новым набором чисел в регистрах. Попутно можно сохранять и саму программу.
Чтобы при этом не возникло TLE, надо хранить максимальную глубину рекурсии (собственно, это первое число в ответе), в которой мы достигли ответа, и не ходить глубже. Также не следует ходить в те состояния, где мы получаем число, большее n. Если же мы получили ровно число n, и наша глубина рекурсии меньше минимальной, запомним ответ и скопируем его в безопасное место, чтобы потом вывести.
Еще есть улучшение, которое состоит в том, чтобы перебирать числа по убыванию (так работает быстрее), но ограничения в 5 секунд хватало, чтоб перебирать числа как угодно.
Были и другие подходы к решению этой задачи: поиск в ширину и перебор для конкретного ответа.
Вот два решения: обычный перебор (http://pastebin.com/Z6ZF36st) и перебор для конкретного ответа (http://pastebin.com/viiYF9CB).
Задача D (div.1) - Флаги
Сначала я расскажу, как считать ответ для одного числа (т.е. L = R), а потом переделаю решение для общего случая. Дело в том, что изначально задумывалась как раз формулировка с конкретным числом полос N, и только потом мы было принято решение усложнить задачу. Мое решение не сильно оптимально (задачи все-таки не "фиолетовые", как оказалось, а некоторые решения - "фиолетовые" :) ). Я видел коды других участников, и у них все попроще.
Итак, задача для фиксированного N.
Обозначим за 
число флагов с N полосами, считая симметричные флаги разными. Посмотрим, как, имея эту информацию, получить ответ на задачу.
На первый взгляд, достаточно поделить на 2. Но, посмотрев повнимательнее, можно обнаружить, что это верно только для флагов, не являющихся палиндромами. Например, флаги-непалиндромы WBWB и BWBW симметричны, и надо учитывать только один из них --- здесь деление на 2 законно. А вот флаги-палиндромы, такие, как WBW, симметричны сами себе, поэтому деление на 2 для них приведет к ошибке.
Посмотрим, что можно сделать. Во-первых, заметим, что при четном N корректных флагов-палиндромов вообще не существует, т.к. иначе в центре встретились бы 2 полосы одного цвета, что невозможно, поэтому для четных N формула 
верна.
, где 
--- количество флагов-палиндромов длины N. Но каждый флаг-палиндром нечетной длины N однозначно определяется своими первыми 
полосами, и количество таких флагов-палиндромов равно 
(здесь, разумеется, симметрию учитывать не надо).Итак, мы свели нашу задачу к нахождению числа флагов с N полосами, причем симметричные флаги считаются различными. Заметим, что для того, чтобы пририсовать очередную полосу к флагу так, чтобы он остался корректным, нам необходимо знать лишь последнюю и предпоследнюю его полосы.
Применим динамическое программирование. В качестве состояния возьмем вектор
из 8 чисел, каждая компонента которого будет содержать количество флагов c общим количеством полос N и определенными корректными последней и предпоследней полосами (как раз 8 вариантов). Сумма всех компонент этого вектора даст нам общее количество флагов с N полосами, т.е. 
.База динамики --- вектор
, содержащий ровно 8 единиц (они соответствуют всем разрешенным парам цветов). Давайте подумаем, как можно найти вектор , зная вектор 
.Оказывается, существует такая матрица A, что
. Элементы этой матрицы можно посчитать даже вручную, из следующих соображений. Например, пусть мы имеем комбинацию последних двух полос WB. Тогда можно справа дописать белую или желтую полосу, что будет соответствовать BW и BY. Поэтому в столбце матрицы, соответствующему WB, мы поставим единички в строках, соответствующих BW и BY. Все это займет не более минуты.И последний шаг. Очевидно, что
. А возведение в степень можно проводить быстро, за логарифмическое время. Принцип в том, что, если N четное, то нам достаточно вычислить 
и возвести эту матрицу в квадрат. А если N --- нечетное, то N - 1 - четное, и для степени N - 1 можно снова применить этот прием.Осталось не забыть, что при N = 1 все это неприменимо, зато можно сразу сказать, что ответ равен 4.
А теперь проапгрейдим это решение для случая отрезка
.У меня есть два способа это сделать. Первый способ состоит в том, что в векторе состояний добавляется одна координата, а в матрице - новая строка и столбец. Эта новая координата в векторе состояний будет хранить сумму на отрезке
(с L = 1 разберемся if-ом). Останется подогнать матрицу A, что делается довольно несложно. Попробуйте сами (подсказка: я умножал ее слева еще на одну, почти единичную матрицу).Второй способ мне понравился больше. Так же, как и ранее, разделим задачу на две: на палиндромы и непалиндромы. Научимся находить ответ для флагов без учета симметрии на отрезке
. В вышеприведенных обозначениях ответ равен 
. Покажем, как можно быстро и просто находить сумму E + A + ... + AN.Пусть b --- такая максимальная степень двойки, что 2b - 1 ≤ N. Разобьем нашу сумму следующим образом:
.Оказывается, первая часть этого выражения легко считается:
. Вы можете сами убедиться в справедливости этого равенства. А сумма в скобках второй части выражения из предыдущего абзаца что-то напоминает... Разберетесь сами :)Ответ для палиндромов считается таким же способом. Будем полагать для удобства, что L и R - нечетные (если это не так, то к L можно прибавить единицу, а от R - отнять). Тогда
.Вот и все. Остается не ошибиться, после каждой операции брать модуль и внимательно рассматривать крайние случаи.
Вот решение вторым способом: http://pastebin.com/wHu1tPgd
Наверное, можно все сделать куда проще. Пишите свои разборы, чем их больше - тем лучше!
Задача E (div.1) - Лостборн
Эта задача решается формулой включений и исключений. Только многие получили TLE, т.к. они почему-то не прогнали максимальный тест на своем компьютере (да, прогоняйте макс. тесты на своем компьютере!).
А остальные почувствовали, что что-то тут не так, и запоминали ответы для небольших N и конкретного ai в массив, чтобы в дальнейшем их не считать. Например, можно посмотреть решение победителя турнира rng_58, там все очень четко и понятно написано. Вот еще один пример такого решения: http://pastebin.com/4kcfJdAi
Более подробно об этой задаче написал ее автор anonymous вот в этом посте: http://codeforces.com/blog/entry/2216. У него есть решение, укладывающееся в ограничение по времени при N ≤ 1015, что, скорее всего, не сделало бы ни одно из решений, отправленных во время контеста. Это решение можно посмотреть в дорешивании.
Разбор задач Codeforces Beta Round 76 (Div. 2 Only)
Всем привет!
Меня зовут Алексей Дергунов, и я рад представить первый "фиолетовый" раунд в истории Codeforces. Надеюсь, что задачи покажутся вам не слишком "фиолетовыми" :)
Благодарю за большую помощь в подготовке контеста следующих людей:
- MikeMirzayanov (Михаил Мирзаянов)
- RAD (Артем Рахов)
- Connector (Макар Красноперов)
- anonymous (Анонимус)
- Delinur (Мария Белова)
UPD. Стали известны имена победителей.
1 дивизион:
2 дивизион:
- 1 место - pmnox
- 2 место - muliguishou
- 3 место - craus
UPD 2. Ссылка на разбор: http://codeforces.com/blog/entry/2208
В последнее время было много непониманий и недовольств текущей системой подсчета очков в соревнованиях и рейтинга, и я постараюсь предложить варианты решения этой проблемы.
Вначале о рейтинге. Сейчас на Codeforces видна инфляция, во всяком случае, мне видна. Это происходит из-за большого количества участников, сыгравших один-два контеста и больше не появлявшихся.
Рассмотрим подробнее: сейчас у нас новый участник неявно получает рейтинг 1500. Как правило, новичков регистрируется гораздо больше, чем опытных программистов, поэтому на первом же своем контесте этот рейтинг сливается. А так как средний рейтинг неизменен, эти очки достаются верхней половине. Если так будет продолжаться, то через пару лет все, кому не лень, станут красными.
Есть такое предложение:
1) Рейтинг у участника появляется только после написания им 5 контестов.
2) Начальный рейтинг участника при этом не полагается 1500. Вместо этого для каждого из первых пяти контестов будем считать для него такой рейтинг, что, обладая им, он не изменил бы его по результатам соревнования.
3) Как только пять контестов пройдет, рейтинг участника становится равным среднему арифметическому пяти чисел, полученных в п.2.
4) При этом при подсчете рейтинга для участников, уже имеющих рейтинг, новички учитываться не должны.
Какие особенности у этой системы: средний рейтинг не будет постоянным. Зато каждый участник получит в результате рейтинг, почти идеально соответствующий его уровню.
Далее, странно, что, скажем, в турнире Manthan последние места слили всего около 50 очков рейтинга. Вот мои мысли об этом.
Рейтинг Эло вроде как из шахмат украден, поэтому почему бы не представить таблицу контеста как таблицу кругового турнира по шахматам? Примем, что участник A обыграл участника B, если он набрал больше очков, и посчитаем рейтинг по всем таким "партиям". При этом коэффициент изменения должен быть очень небольшим, ведь в контестах участвуют более 1000 участников.
Есть ощущение, что текущий расчет ведется как-то по-иному, потому что при описанной выше "шахматной" системе слив рейтинга последним местом должен быть довольно существенным - ведь он проиграл всем, вообще всем, в то время как в соперниках было около 200 участников, равных ему по силам!
Теперь о самом наболевшем: конечно же, о взломах.
Конечно же, если претесты делать покрывающими все мыслимые случаи, то от взломов ничего не останется, и контесты превратятся в ACM. Так что, как и претесты нужны почти полные (это пожелание авторам), нужна и возможность взломов. Но, если посмотреть на результаты последних раундов, то можно увидеть участников, заработавших более 3000 очков на взломах (при этом в последнем контесте задача A, на мой взгляд, была достаточно хорошей). Напомню, что суммарная стоимость задач - 7500. Не кажутся ли вам эти цифры немного несопоставимы? Решаешь на первых минутах A и B, делаешь 30 взломов = почти 4500 очков и ты примерно в топ-20! А если решать все задачи, то, скорее всего, получишь даже меньше, ведь стоимость то убывает.
Я сам на Manthan-е отправил задачу A на 8 минуте, заблокировал, т.к. мои первоначальные тесты она проходила. Потом, минут через 10, я неожиданно понял, что отправил фигню! Открыл комнату и набрал 1000 очков. А стоимость задачки - 500. Ошибся, не сдал задачу, а в итоге набрал на этом в 2 раза больше очков. Не слишком это честно, что-ли.
Все-таки надо что-то менять. Почему-то лучшим выходом мне видится изменение очков за взломы. Тут есть сразу несколько предложений, которые вполне можно и объединить. Они были высказаны уже давно, а я их тут просто объединю.
1) Изменить очки в зависимости от стоимости задачи (сам я проголосую за этот пункт). Например, за удачные взломы по задачам A,B,C,D,Е давать 40, 60, 80, 100, 120 баллов. По-моему, такой подсчет достаточно корректен: 1200 очков за 30 взломов по задаче A вроде бы нормальный результат (30 взломов набирает 1-2 человека за контест), в отличие от 3000 очков. Хочешь получать по 100 баллов - а реши-ка ты сначала задачу D!
2) Уменьшать очки по мере увеличения числа взломов. Например, за первый взлом давать 100% от номинала, за второй - 90%, ......, за десятый и последующие - 10%. Здесь первые взломы будут неплохо поднимать вас вверх в таблице, а последующие - не очень сильно. Получится "поломал сам - дай поломать другим". Или "не дай поломать другим, но получи от этого мало очков". И выбираем, что выгоднее.
3) Изменять количество очков в зависимости от цвета/разности рейтинга. Скажем, за взлом своего цвета давать 100% очков, соседних сверху и снизу - 120% и 80% и т.д.
Или в зависимости от рейтинга: очки = номинал * (1 + (чужой_рейтинг - твой_рейтинг) / 1000).
Что будет: 1500 ломает 2000, получает 150% очков, 1900 ломает 1400 - получает 50% очков. Надо будет еще как-то правильно отнормировать эту формулу, но вообще это смотрится неплохо.
Вначале о рейтинге. Сейчас на Codeforces видна инфляция, во всяком случае, мне видна. Это происходит из-за большого количества участников, сыгравших один-два контеста и больше не появлявшихся.
Рассмотрим подробнее: сейчас у нас новый участник неявно получает рейтинг 1500. Как правило, новичков регистрируется гораздо больше, чем опытных программистов, поэтому на первом же своем контесте этот рейтинг сливается. А так как средний рейтинг неизменен, эти очки достаются верхней половине. Если так будет продолжаться, то через пару лет все, кому не лень, станут красными.
Есть такое предложение:
1) Рейтинг у участника появляется только после написания им 5 контестов.
2) Начальный рейтинг участника при этом не полагается 1500. Вместо этого для каждого из первых пяти контестов будем считать для него такой рейтинг, что, обладая им, он не изменил бы его по результатам соревнования.
3) Как только пять контестов пройдет, рейтинг участника становится равным среднему арифметическому пяти чисел, полученных в п.2.
4) При этом при подсчете рейтинга для участников, уже имеющих рейтинг, новички учитываться не должны.
Какие особенности у этой системы: средний рейтинг не будет постоянным. Зато каждый участник получит в результате рейтинг, почти идеально соответствующий его уровню.
Далее, странно, что, скажем, в турнире Manthan последние места слили всего около 50 очков рейтинга. Вот мои мысли об этом.
Рейтинг Эло вроде как из шахмат украден, поэтому почему бы не представить таблицу контеста как таблицу кругового турнира по шахматам? Примем, что участник A обыграл участника B, если он набрал больше очков, и посчитаем рейтинг по всем таким "партиям". При этом коэффициент изменения должен быть очень небольшим, ведь в контестах участвуют более 1000 участников.
Есть ощущение, что текущий расчет ведется как-то по-иному, потому что при описанной выше "шахматной" системе слив рейтинга последним местом должен быть довольно существенным - ведь он проиграл всем, вообще всем, в то время как в соперниках было около 200 участников, равных ему по силам!
Теперь о самом наболевшем: конечно же, о взломах.
Конечно же, если претесты делать покрывающими все мыслимые случаи, то от взломов ничего не останется, и контесты превратятся в ACM. Так что, как и претесты нужны почти полные (это пожелание авторам), нужна и возможность взломов. Но, если посмотреть на результаты последних раундов, то можно увидеть участников, заработавших более 3000 очков на взломах (при этом в последнем контесте задача A, на мой взгляд, была достаточно хорошей). Напомню, что суммарная стоимость задач - 7500. Не кажутся ли вам эти цифры немного несопоставимы? Решаешь на первых минутах A и B, делаешь 30 взломов = почти 4500 очков и ты примерно в топ-20! А если решать все задачи, то, скорее всего, получишь даже меньше, ведь стоимость то убывает.
Я сам на Manthan-е отправил задачу A на 8 минуте, заблокировал, т.к. мои первоначальные тесты она проходила. Потом, минут через 10, я неожиданно понял, что отправил фигню! Открыл комнату и набрал 1000 очков. А стоимость задачки - 500. Ошибся, не сдал задачу, а в итоге набрал на этом в 2 раза больше очков. Не слишком это честно, что-ли.
Все-таки надо что-то менять. Почему-то лучшим выходом мне видится изменение очков за взломы. Тут есть сразу несколько предложений, которые вполне можно и объединить. Они были высказаны уже давно, а я их тут просто объединю.
1) Изменить очки в зависимости от стоимости задачи (сам я проголосую за этот пункт). Например, за удачные взломы по задачам A,B,C,D,Е давать 40, 60, 80, 100, 120 баллов. По-моему, такой подсчет достаточно корректен: 1200 очков за 30 взломов по задаче A вроде бы нормальный результат (30 взломов набирает 1-2 человека за контест), в отличие от 3000 очков. Хочешь получать по 100 баллов - а реши-ка ты сначала задачу D!
2) Уменьшать очки по мере увеличения числа взломов. Например, за первый взлом давать 100% от номинала, за второй - 90%, ......, за десятый и последующие - 10%. Здесь первые взломы будут неплохо поднимать вас вверх в таблице, а последующие - не очень сильно. Получится "поломал сам - дай поломать другим". Или "не дай поломать другим, но получи от этого мало очков". И выбираем, что выгоднее.
3) Изменять количество очков в зависимости от цвета/разности рейтинга. Скажем, за взлом своего цвета давать 100% очков, соседних сверху и снизу - 120% и 80% и т.д.
Или в зависимости от рейтинга: очки = номинал * (1 + (чужой_рейтинг - твой_рейтинг) / 1000).
Что будет: 1500 ломает 2000, получает 150% очков, 1900 ломает 1400 - получает 50% очков. Надо будет еще как-то правильно отнормировать эту формулу, но вообще это смотрится неплохо.
1. Открываем главную страницу любого контеста.
2. Щелкаем "Положение".
3. В новой вкладке браузера открывается это самое положение.
4. В первой вкладке открываем главную страницу другого контеста.
5. Щелкаем "Положение".
6. Положение нового контеста открывается в вкладке, открытой на шаге 3.
P.S. Потыкал еще немного - результат даже неоднозначен. В одном из случаев положение открылось в предыдущей просмотренной вкладке.
Браузер = Firefox 3.0.19, если что.
2. Щелкаем "Положение".
3. В новой вкладке браузера открывается это самое положение.
4. В первой вкладке открываем главную страницу другого контеста.
5. Щелкаем "Положение".
6. Положение нового контеста открывается в вкладке, открытой на шаге 3.
P.S. Потыкал еще немного - результат даже неоднозначен. В одном из случаев положение открылось в предыдущей просмотренной вкладке.
Браузер = Firefox 3.0.19, если что.
Собственно, здравствуйте, уважаемые читатели. Это мой первый пост на этом сайте, и связан он, разумеется, с четвертьфиналом 18-23 октября в Саратове, который на самом деле называется первенством Южного подрегиона NEERC.
Вероятно, все уже видели монитор соревнований - там команда Samara SAU #2 заметно опередила мою команду Samara SAU #1. Это не случайность, просто при регистрации человек, ответственный за нее, решил пошутить и поменять нас местами, потому что он хотел отсортировать команды по возрасту. Так что реально сильнейшей была вторая команда, а наши шансы на проход я оценивал примерно 50 на 50.
В качестве вступления хочу отметить чистоту и красоту территории университета. Это не наш раздолбанный Самарский аэрокосмический университет с убогими зданиями, свалкой самолетов, домиками каких-то мужиков, вроде бы связанных с запчастями для машин и прочим мусором.
Рассказ, пожалуй, надо начать с 20 октября, когда прошел пробный тур и раздали условия Code Game Challenge. О пробном туре у меня одно замечание: меня и мою команду очень порадовала тестирующая система. При написании java-класса, реализующего Runnable и дальнейшем создании нового потока тестирующая система давала верный вердикт RE при выбрасывании исключения. А вот на Тимусе, например, дают WA вместо RE.
Посмотрев задания Code Game Challenge, мы очень обрадовались: это снова танки, а не унылые гонки. Точнее, это были танки двухлетней давности без баз и трения.
На самом Code Game Challenge мы сначала написали стрельбу, на это ушло примерно час. Мы просто сделали все то же самое, что и 2 года назад, когда наш танк занял 7 место. Этот алгоритм себя оправдал: стрелял наш IDDQD идеально. А вот хорошее движение написать не получилось: наверняка все видели, как наш танк тупил.
Было обидно, что нам не везло с случайными бонусами. За 10 минут до конца соревнования мы тестили свой ховеркрафт на рандомах в Global Test, и он примерно в 80% случаев набирал более 100 очков и занимал 1 место. За 6 раундов настоящего Code Game это удалось лишь в самой первой игре. Возможно, при большем везении мы попали бы в призы.
Зато отлично выступила наша вторая и сильнейшая команда. Их ховеркрафт рвал нашего IDDQD один на один примерно в 70% случаев. Мы предполагали, что это серьезная заявка на победу - так и вышло. Ховеркрафт с загадочным названием Natasha Fan Club, названный в честь местной богини программирования, не только идеально стрелял, но и превосходно ездил и собирал бонусы, и в итоге победил, выиграв 8 поединков из 9 и уступив еще в одном лишь одно очко.
А наша третья команда с креативным названием 123456789 заняла шестое место, обогнав наш невезучий ховеркрафт, который закончил турнир на 16 месте.
Я снимал на сотовый второй и третий раунды (т.е. когда осталось 32 ховеркрафта и финал соответственно), и они уже доступны для просмотра (пока на Rutube). Хотя было бы круто, если бы организаторы выложили оригинальное видео, я не вижу причин, почему этого не делать.
Сам контест для нашей команды прошел в режиме злостного отупения. Вначале мы написали задачу F (про лифт), но получили TLE. Конечно, это было зацикливание. Мой просчет... Потом набрали задачу B (про кубики), сдали таки F и J (про буйки, где один из моих партнеров вовремя сообразил, что надо оставлять на месте ровно два буйка). Затем я целый час решал E (про мужика, которого везут с закрытыми глазами), вовремя не заметив нормальное решение в 3 цикла for. Первый неверный сабмит по E получил TLE, хотя работать должен был вроде бы недолго. А второй неверный сабмит произошел из-за глупейшего бага, недописанной строчки. Потом мы зачем-то написали эвристику для C, cловившую WA #19, и сдали D (про Николая и Владимира) с второй попытки (ага, естественно, ребро надо добавлять только в одну сторону).
Итак, за 3 часа мы сдали 5 задач, а наша первая (на мониторе - вторая) команда сдала шесть. В дальнейшем мы так ничего и не сдали, а за час до конца соревнований были на 13 месте, если исключить стоящие выше нас лишние саратовские команды. Непосредственно после контеста мы узнали, что сидевшие напротив нас волгоградцы решили две задачи за последний час и обогнали нас - мы стали четырнадцатыми, последним выходящим местом.
На выходе нас немножко успокоили, сказав, что мы были последними из тех, кто решил пять задач, и что команды, решившие четыре задачи, отставали от нас по времени - им надо было делать две. Этого не произошло, и мы проскочили в Питер, не решив ни одной трудной задачи. А вообще непонятно, почему мы не начали писать G и K.
Результат был отпразднован, разбор задач прослушан, и пора было уезжать. Мы решили посидеть на лавочках на территории университета и уйти, как только до отправления поезда останется час. Там было весело: на нас целый час набигали две пьяные девочки, Алиса и Оля. Они никак не могли поверить, что мы ждем поезда, и все время пытались унести с собой рули, выигранные в Code Game Challenge. В итоге они порвали ручку у коробки руля и зохавали два бейджика. Впрочем, это нас не огорчило, и мы уехали домой, в Самару. А я еще и написал этот пост.
UPD: Видео Code Game Challenge залито на Rutube: http://rutube.ru/tracks/3703952.html?v=74c4d34409fa2e52a8c439a3039b7f03 и Вконтакте: http://vkontakte.ru/video7104349_154275450, не ругайте меня за возможные неадекватные комментарии...
Вероятно, все уже видели монитор соревнований - там команда Samara SAU #2 заметно опередила мою команду Samara SAU #1. Это не случайность, просто при регистрации человек, ответственный за нее, решил пошутить и поменять нас местами, потому что он хотел отсортировать команды по возрасту. Так что реально сильнейшей была вторая команда, а наши шансы на проход я оценивал примерно 50 на 50.
В качестве вступления хочу отметить чистоту и красоту территории университета. Это не наш раздолбанный Самарский аэрокосмический университет с убогими зданиями, свалкой самолетов, домиками каких-то мужиков, вроде бы связанных с запчастями для машин и прочим мусором.
Рассказ, пожалуй, надо начать с 20 октября, когда прошел пробный тур и раздали условия Code Game Challenge. О пробном туре у меня одно замечание: меня и мою команду очень порадовала тестирующая система. При написании java-класса, реализующего Runnable и дальнейшем создании нового потока тестирующая система давала верный вердикт RE при выбрасывании исключения. А вот на Тимусе, например, дают WA вместо RE.
Посмотрев задания Code Game Challenge, мы очень обрадовались: это снова танки, а не унылые гонки. Точнее, это были танки двухлетней давности без баз и трения.
На самом Code Game Challenge мы сначала написали стрельбу, на это ушло примерно час. Мы просто сделали все то же самое, что и 2 года назад, когда наш танк занял 7 место. Этот алгоритм себя оправдал: стрелял наш IDDQD идеально. А вот хорошее движение написать не получилось: наверняка все видели, как наш танк тупил.
Было обидно, что нам не везло с случайными бонусами. За 10 минут до конца соревнования мы тестили свой ховеркрафт на рандомах в Global Test, и он примерно в 80% случаев набирал более 100 очков и занимал 1 место. За 6 раундов настоящего Code Game это удалось лишь в самой первой игре. Возможно, при большем везении мы попали бы в призы.
Зато отлично выступила наша вторая и сильнейшая команда. Их ховеркрафт рвал нашего IDDQD один на один примерно в 70% случаев. Мы предполагали, что это серьезная заявка на победу - так и вышло. Ховеркрафт с загадочным названием Natasha Fan Club, названный в честь местной богини программирования, не только идеально стрелял, но и превосходно ездил и собирал бонусы, и в итоге победил, выиграв 8 поединков из 9 и уступив еще в одном лишь одно очко.
А наша третья команда с креативным названием 123456789 заняла шестое место, обогнав наш невезучий ховеркрафт, который закончил турнир на 16 месте.
Я снимал на сотовый второй и третий раунды (т.е. когда осталось 32 ховеркрафта и финал соответственно), и они уже доступны для просмотра (пока на Rutube). Хотя было бы круто, если бы организаторы выложили оригинальное видео, я не вижу причин, почему этого не делать.
Сам контест для нашей команды прошел в режиме злостного отупения. Вначале мы написали задачу F (про лифт), но получили TLE. Конечно, это было зацикливание. Мой просчет... Потом набрали задачу B (про кубики), сдали таки F и J (про буйки, где один из моих партнеров вовремя сообразил, что надо оставлять на месте ровно два буйка). Затем я целый час решал E (про мужика, которого везут с закрытыми глазами), вовремя не заметив нормальное решение в 3 цикла for. Первый неверный сабмит по E получил TLE, хотя работать должен был вроде бы недолго. А второй неверный сабмит произошел из-за глупейшего бага, недописанной строчки. Потом мы зачем-то написали эвристику для C, cловившую WA #19, и сдали D (про Николая и Владимира) с второй попытки (ага, естественно, ребро надо добавлять только в одну сторону).
Итак, за 3 часа мы сдали 5 задач, а наша первая (на мониторе - вторая) команда сдала шесть. В дальнейшем мы так ничего и не сдали, а за час до конца соревнований были на 13 месте, если исключить стоящие выше нас лишние саратовские команды. Непосредственно после контеста мы узнали, что сидевшие напротив нас волгоградцы решили две задачи за последний час и обогнали нас - мы стали четырнадцатыми, последним выходящим местом.
На выходе нас немножко успокоили, сказав, что мы были последними из тех, кто решил пять задач, и что команды, решившие четыре задачи, отставали от нас по времени - им надо было делать две. Этого не произошло, и мы проскочили в Питер, не решив ни одной трудной задачи. А вообще непонятно, почему мы не начали писать G и K.
Результат был отпразднован, разбор задач прослушан, и пора было уезжать. Мы решили посидеть на лавочках на территории университета и уйти, как только до отправления поезда останется час. Там было весело: на нас целый час набигали две пьяные девочки, Алиса и Оля. Они никак не могли поверить, что мы ждем поезда, и все время пытались унести с собой рули, выигранные в Code Game Challenge. В итоге они порвали ручку у коробки руля и зохавали два бейджика. Впрочем, это нас не огорчило, и мы уехали домой, в Самару. А я еще и написал этот пост.
UPD: Видео Code Game Challenge залито на Rutube: http://rutube.ru/tracks/3703952.html?v=74c4d34409fa2e52a8c439a3039b7f03 и Вконтакте: http://vkontakte.ru/video7104349_154275450, не ругайте меня за возможные неадекватные комментарии...
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 27.04.2024 02:04:46 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
