Хотел поделиться своими впечатлениями еще давно, но никак не мог найти время. И вот по истечении двух месяцев, оно все-таки нашлось. На борту самолета из Сан-Франциско в Париж. Лучше поздно, чем никогда :)
Так, вот! Мы, команда Saratov SU2 (уже Retired), решили после пятилетнего перерыва вспомнить молодость и поучаствовать в соревновании под названием Challenge 24. Это ежегодное командное соревнование проводимое на базе BME university, отличается своими нестандартными задачами (гибрид ipsc, токподеровского марафона, acm icpc с открытыми тестами, и codegame challenge) и достаточно хардкорным онсайт финалом, который проходит 24 часа нон-стоп! Причем команде выдают лишь две розетки - эзернет и сеть 220V, а все остальное должно быть с собой (ноутбуки, хабы/раутеры, провода, спальники, и т.д.) Ах да, чуть не забыл, если вы вышли в онсайт, то проезд и проживание за ваш счет :)
Она из прелестей соревнования заключается в том, что на пути к 24-часовому финалу есть всего лишь одна преграда - отборочный тур по интернету, который идет 5 часов. В онсайт финал приглашаются лучшие 27 команд, плюс топ 3 прошлого года. Мы подумали что это хороший повод поучаствовать и написать отборочный тур. Собственно, о нем и рассказ.
На момент интернет тура Иван с Игорем были в Швейцарии, а я в Калифорнии. Поэтому связь было решено держать по скайпу. У меня шел первый час ночи, у ребят утро. За пол часа до начала пришлось усердно попотеть и заняться установкой явы, идеи, а так же написанием шаблона. Все это мы успешно преодолели, и даже спустя 10 минут после того как соревнование началось, нам удалось невероятными телепатическими усилиями найти пароли к задачам в IRC канале, распаковать два вложенных запароленных архива и приступить к прочтению условий :)
После прочтениях всех 6-ти задач, стало понятно что ничего не понятно. Недолго подумав, мы все же вспомнили как проверять изоморфизм деревьев, и было решено писать задачу "B" вдвоем. Я же начал заниматься "D", где нужно было уметь проматывать вперед линейный конгруэнтный генератор. В итоге спустя где-то час-полтора после начала, ребята сдали "B", а я сдал лишь несколько первых тестов от "D" потому как долго возился даже с тривиальным решением (получались другие ответы), а ничего умнее так и не придумал.
По причине тотального отсутствия идей по "D", было принято решение переключить меня на задачу "A", где предлагалось разделить 100 чисел от 0 до 100 на 3 кучки с одинаковой суммой (которую нужно было максимизировать), возможно использовав не все элементы. А ребята стали решать "C", где по изображению пластинки данной в виде .png файла, нужно было понять в каком формате на ней записан звук, воспроизвести его, послушать, и в качестве ответа послать набор цифр которые там проговаривают голосом.
С задачей "A" я мучался достаточно долго, пытаясь придумать динамику. Но мозг никак не хотел включаться в 3 часа ночи, поэтому я сдал опять же тривиальным решением несколько первых тестов, чтобы не терять баллы из-за удешевления задачи, и стал думать дальше. Иван с Игорем усиленно писали "C", попутно изучая API явы для работы со звуком и картинками. Тут мне в голову пришла идея - попробовать в "A" поаппроксимировать ответ рандомом (перебираем сумму/ответ сверху вниз, пытаемся 10^5 раз взять случайную перестановку, и попробовать жадно набрать данную сумму три раза; если получилось, то у нас есть кандидат на ответ). Рандом показывал удивительно хорошие результаты близкие к правде, но было понятно что отсылать в таком виде ответы нельзя из-за риска получить WA и штрафные баллы. Было принято решение модифицировать тривиальное решение, чтобы учитывать проаппроксимированный ответ во время перебора, таким образом уменьшив количество состояний.
Тем временем ребята начали с завидной периодичностью звонить по скайпу, ставя послушать звуки которые им удалось проиграть с пластинки. Звук шел, проигрывалось все отлично! Но было одно маленькое "но" -- все записи были похожи на соревнования скретч диджеев, а в ответ нужно было все-таки отослать набор цифр :) Короче говоря мы продолжили заниматься задачами. Я не питал больших надежд на "A", потому что упихать 4^100 не представлялось реальным. Но удивительный факт, после модификации перебора у меня супер быстро отработали все тесты (самый большой работал секунд 15, а количество состояний разрослось всего лишь до 4 * 10^8). Было понятно что ответы правильные, задача успешно сдалась! Позднее в разборе расскажут про правильную динамику, и напишут что перебор пройти ну никак не мог из-за дикого количества состояний :D
Ребята продолжали работать над пластинками, я сразу начал писать марафонную задачу "E", благо было понятно что в ней нужно делать. Минут за 40 до конца нас настиг успех - получилось правильно проиграть первую пластинку и успешно отослать правильный ответ! У меня к этому времени был готов парсинг городов и кое-какие вспомогательные методы. Минут за 15 до конца, написанное впопыхах самое первое решение задачи "E" получило около 45% возможных баллов. И у нас уже было 9 из 10 правильно проигранных пластинок! К сожалению последняя пластинка оказалось немного кривоватой, наш парсер все время сходил с дорожки, и так и не удалось ее проиграть. Но зато получилось улучшить решение "E" до 75% возможных баллов, отослав последний ответ за пол минуты до конца.
Вот так, в очень плотной борьбе, мы и заняли почетное 4-е место, пробившись в онсайт :) Сегодня вечером рейсы из Парижа и Цюриха соберут нас втроем в Будапеште, а завтра и послезавтра (30 апреля и 1 мая) можно будет поболеть за нас, и не только! Надеюсь монитор будет доступен.
P.S.
Ссылка на задачи отборочного раунда: http://ch24.org/ec/html/
Итоговое положение после отборочного раунда: http://ch24.org/team/list
Отчет с прошлогоднего финала: http://codeforces.me/blog/entry/360
Так, вот! Мы, команда Saratov SU2 (уже Retired), решили после пятилетнего перерыва вспомнить молодость и поучаствовать в соревновании под названием Challenge 24. Это ежегодное командное соревнование проводимое на базе BME university, отличается своими нестандартными задачами (гибрид ipsc, токподеровского марафона, acm icpc с открытыми тестами, и codegame challenge) и достаточно хардкорным онсайт финалом, который проходит 24 часа нон-стоп! Причем команде выдают лишь две розетки - эзернет и сеть 220V, а все остальное должно быть с собой (ноутбуки, хабы/раутеры, провода, спальники, и т.д.) Ах да, чуть не забыл, если вы вышли в онсайт, то проезд и проживание за ваш счет :)
Она из прелестей соревнования заключается в том, что на пути к 24-часовому финалу есть всего лишь одна преграда - отборочный тур по интернету, который идет 5 часов. В онсайт финал приглашаются лучшие 27 команд, плюс топ 3 прошлого года. Мы подумали что это хороший повод поучаствовать и написать отборочный тур. Собственно, о нем и рассказ.
На момент интернет тура Иван с Игорем были в Швейцарии, а я в Калифорнии. Поэтому связь было решено держать по скайпу. У меня шел первый час ночи, у ребят утро. За пол часа до начала пришлось усердно попотеть и заняться установкой явы, идеи, а так же написанием шаблона. Все это мы успешно преодолели, и даже спустя 10 минут после того как соревнование началось, нам удалось невероятными телепатическими усилиями найти пароли к задачам в IRC канале, распаковать два вложенных запароленных архива и приступить к прочтению условий :)
После прочтениях всех 6-ти задач, стало понятно что ничего не понятно. Недолго подумав, мы все же вспомнили как проверять изоморфизм деревьев, и было решено писать задачу "B" вдвоем. Я же начал заниматься "D", где нужно было уметь проматывать вперед линейный конгруэнтный генератор. В итоге спустя где-то час-полтора после начала, ребята сдали "B", а я сдал лишь несколько первых тестов от "D" потому как долго возился даже с тривиальным решением (получались другие ответы), а ничего умнее так и не придумал.
По причине тотального отсутствия идей по "D", было принято решение переключить меня на задачу "A", где предлагалось разделить 100 чисел от 0 до 100 на 3 кучки с одинаковой суммой (которую нужно было максимизировать), возможно использовав не все элементы. А ребята стали решать "C", где по изображению пластинки данной в виде .png файла, нужно было понять в каком формате на ней записан звук, воспроизвести его, послушать, и в качестве ответа послать набор цифр которые там проговаривают голосом.
С задачей "A" я мучался достаточно долго, пытаясь придумать динамику. Но мозг никак не хотел включаться в 3 часа ночи, поэтому я сдал опять же тривиальным решением несколько первых тестов, чтобы не терять баллы из-за удешевления задачи, и стал думать дальше. Иван с Игорем усиленно писали "C", попутно изучая API явы для работы со звуком и картинками. Тут мне в голову пришла идея - попробовать в "A" поаппроксимировать ответ рандомом (перебираем сумму/ответ сверху вниз, пытаемся 10^5 раз взять случайную перестановку, и попробовать жадно набрать данную сумму три раза; если получилось, то у нас есть кандидат на ответ). Рандом показывал удивительно хорошие результаты близкие к правде, но было понятно что отсылать в таком виде ответы нельзя из-за риска получить WA и штрафные баллы. Было принято решение модифицировать тривиальное решение, чтобы учитывать проаппроксимированный ответ во время перебора, таким образом уменьшив количество состояний.
Тем временем ребята начали с завидной периодичностью звонить по скайпу, ставя послушать звуки которые им удалось проиграть с пластинки. Звук шел, проигрывалось все отлично! Но было одно маленькое "но" -- все записи были похожи на соревнования скретч диджеев, а в ответ нужно было все-таки отослать набор цифр :) Короче говоря мы продолжили заниматься задачами. Я не питал больших надежд на "A", потому что упихать 4^100 не представлялось реальным. Но удивительный факт, после модификации перебора у меня супер быстро отработали все тесты (самый большой работал секунд 15, а количество состояний разрослось всего лишь до 4 * 10^8). Было понятно что ответы правильные, задача успешно сдалась! Позднее в разборе расскажут про правильную динамику, и напишут что перебор пройти ну никак не мог из-за дикого количества состояний :D
Ребята продолжали работать над пластинками, я сразу начал писать марафонную задачу "E", благо было понятно что в ней нужно делать. Минут за 40 до конца нас настиг успех - получилось правильно проиграть первую пластинку и успешно отослать правильный ответ! У меня к этому времени был готов парсинг городов и кое-какие вспомогательные методы. Минут за 15 до конца, написанное впопыхах самое первое решение задачи "E" получило около 45% возможных баллов. И у нас уже было 9 из 10 правильно проигранных пластинок! К сожалению последняя пластинка оказалось немного кривоватой, наш парсер все время сходил с дорожки, и так и не удалось ее проиграть. Но зато получилось улучшить решение "E" до 75% возможных баллов, отослав последний ответ за пол минуты до конца.
Вот так, в очень плотной борьбе, мы и заняли почетное 4-е место, пробившись в онсайт :) Сегодня вечером рейсы из Парижа и Цюриха соберут нас втроем в Будапеште, а завтра и послезавтра (30 апреля и 1 мая) можно будет поболеть за нас, и не только! Надеюсь монитор будет доступен.
P.S.
Ссылка на задачи отборочного раунда: http://ch24.org/ec/html/
Итоговое положение после отборочного раунда: http://ch24.org/team/list
Отчет с прошлогоднего финала: http://codeforces.me/blog/entry/360
Comments (0)
