Сегодня в Новосибирске начинается Всесибирская олимпиада по программированию.
Завтра состоится соревнование первой номинации (Game Challenge) была марафонская задача : http://olimpic.nsu.ru/wso/archive (надеюсь, что не сделаю много плохого, если выложу пароль: Tentura), в воскресенье - ACM тур.
Предлагаю здесь обсуждать впечатления и задачи.
То ни солнца закат - то
грусть одолела.
На всесибе я не был.
Well... Всесиб для нашей команды начался с небольшой экскурсии по городу. Мы пропустили в нужный момент банкомат одного известного банка. Нам выделили волонтершу, которая сопроводила нас до ближайшего. Что в целом было приятно :)
Жеребьевка. Это конечно мой личный взгляд, но процесс мне показался лишним. Я верю, что организаторы могли написать программу, которая рассадила бы всех участников. И кроме того, я верю в честность организаторов. Они же хотят поддерживать престиж своего турнира. Могли сэкономить минут 40 от всего процесса.
Пробный тур. Пробный тур прошел вполне спокойно. Eclipse, Far, Visual Studio, gcc запускались без каких-либо проблем. Большой монитор, стабильные и адекватные вердикты. Печать мы не пробовали, но у ИТМО 1 она не заработала. Думаю отключили на пробный тур, на основном не использовали. Вызвала некоторую оторопь клавиатура: очень уж тяжко было перестроиться, т.к. блок Insert/Home/PgUp был повернут на 90 градусов. Длился по факту пробный тур около полутора часов; проверить можно было почти все.
Ненавязчиво волонтеры выгнали нас на открытие, а сами стали чистить компы. Как я понял, делали они это вручную. Что мне кажется не очень верным.
Открытие. Особо информативным открытие не было. Рассказали о перспективах, пожелали удачи, в конце были освещены какие-то организационные моменты.
Дальше было окно. В окно мы могли пообедать и около полутора часов безучастно бродить в стенах главного здания НГУ. Я услышал несколько новых баек и покидался тарелочкой. Но ожидание, как вы догадываетесь, все же утомительно.
Столовая порадовала своей эффективностью: особых заторов я не заметил. Либо мне повезло, либо местный персонал работает довольно резво.
Основной тур. Читатель наверное уже знаком с условиями. Я думаю о звездах еще могут сказать другие романтики :) В целом я бы оценил создание хорошего решения по ней месяца в три работы бодрой исследовательской группы. Скоро узнаем, насколько превосходят мои ожидания лидеры.
Да, немного смущающим для нас были вердикты во время основного тура. Между временем работы и баллами была у нас строчка вида AAAM. И к великому нашему сожалению узнали мы, что означала она "Accepted, Accepted, Accepted, Memory Limit" только после контеста. Этот момент мы упустили. Жаль, но и не очень очевидно было. Как оказалось, мы были не одиноки.
В итоге вместо наших потуг с разумным решением в отослали заглушку.
Ужин.
P.S. Спасибо организаторам за сок и шоколадку во время тура! Это было кстати :)
Пишем программу
int main()
{
ifstream cin("teams.txt");
vector<string> v;
while(getline(cin,s))
if (s != "")
v.push_back(s);
int currentTime = time(0);
cout<<"Current time = " << currentTime << endl;
srand(currentTime);
random_shuffle(v.begin(),v.end());
for (int i=0;i<(int)v.size();i++)
cout<<i+1<<' '<<v[i]<<endl;
return 0;
}
Которая торжественно запускается на большом экране во время жеребьевки. В случае паранойи показанный рандсид полностью гарантирует честность жеребьевки (всегда можно перепроверить), а правильность времени с точностью до пары секунд проконтролировать по часам. Подтасовка вида "подогнали" выглядит нереальной.
Можно заиспользовать один из сервисов random.org, например этот.
Подскажите, пожалуйста, как решать задачу 7 (Ролевая игра 2). Там пересечение полуплоскостей или можно как-то проще?
Пересечь полуплоскости - получим выпуклый многоугольник (нужно отсортить плоскости по углу нормали, а дальше за линейное амортизированное время все пересекается). Ну и потом надо за logn определять принадлежность точек этому многоульнику (делается бинпоиском).
6 - Дейкстра на графе, где цена ребра — длина отрезка - длина объединения отрезков, покрывающихся какой-нибудь из окружностей. Длина объединения — стандартная задача на эвенты.
игнор
Ans = sum (i = n - 1 .. 0) (C(n - 1, i) * (-1) ^ (n - 1 - i) * a[i])
Биномиальные коэффициенты за O(n ^ 2) считать нельзя, поэтому будем вычислять их через определение как отношение факториалов.
Для этого будем хранить два массива f[] и pow[], где pow[i] - максимальная степень p, являющаяся делителем i!, f[i] = i! / p ^ pow[i];
Теперь для подсчета ответа достаточно проверить: если степень факториала в числителе больше суммы степеней факториалов в знаменателе, то это слагаемое даст в ответе 0 по модулю p.
Иначе умножим факториал числителя на числа, обратные по модулю p к факториалам знаменателя. (обратные можно считать, например, Евклидом).
Вот код: http://pastebin.com/LGKwz4KW
Оригинальный разбор задачи "Пьяный матрос" от автора (Димы Бутюгина). Там только небольшая ботва с собственными векторами в примечании...
Над преобразованием Фурье Дима тоже думал, но не придумал, как его там использовать.
Petr-a и tourist-a, наверное, интересует вопрос - как на опенкаповском туре команда Вятки сдала задачу 14 на битмаски за две минуты? ;)
Я не из Вятки, но отвечу:
Анонимус никогда, после сдачи одной задачи, не исправлял в другой, написанной задаче тупую опечатку, найденную сокомандником?
Такая супер-тактика позволила нам на четвертьфинале сдать задачу H за рекордное время 1 минута 2 секунды...
Да ладно, со сдачи 13-й прошло 40 минут. По пути сдалась 3-я, но её кодить 2 минуты. Да и команда опытная.
Кстати, передавать комп совсем не обязятельно. Когда сидишь и кодишь что-то объемное, отвлечься на пару минут на задач на формулу вполне реально.
Мне вот интересней, как сдать F с ГП Екатерингбурга за всего 10 минут...
Да, к наше решение например не работало на таком тесте:
11011011
10000001
11011011
К нему правильный ответ вроде 3, а у нас больше выдавало.
В общем, если вы паросочетание ищете потоком, то нужно следить, чтобы ребра были только из левой доли в правую, а из правой в левую только обратные, не обыкновенные.
А потом уже, после того как нашли паросочетание, перенаправить ребра как того требует нахождение контролирующего множества.
я пишу Куна, проблем с 10 тестом нету, 13 WA.
Прошла.
fixed
Динамика по подмножествам. Параметры: карты первого игрока, карты второго игрока, кто ходит. Первый стремится максимизировать ответ, второй - минимизировать.
Пересчет делается так: перебираем по карте у 1 и 2 игрока. Если такой ход возможный - пытаемся обновить ответ. Если первым ходит первый игрок, он выбирает максимальное значение из всех минимальных значений, которые ему может предложить второй игрок. Аналогично, если ходит второй - он выбирает минимальное значение из всех максимальных, которые ему может предложить первый.
кто-нибудь может рассказать, как решать 13 нормально, а то мы помучавшись с математическим решением, сдали потоками
ну просто я подумал, что это
ебанутость и извращениестранно: писать на такую задачу макспоток... в итоге, мы все таки решили это сделатьТо, что происходило, меня просто убило.
В середине контеста читаем задачу, думаем халява. Сажусь пишу, получаю WA2, отдаю код однокомандникам, пишу другую задачу. В 3:53 исправляю найденное, посылаю, получаю Check failed N/A. Сразу же пишу клару, бегло читаю код-вроде правильно переключаюсь на другую задачу.
Через полчаса не вижу никакой реакции, в 4:26 отправляю еще одну клару. В 4:40 приходит ответ, что check failed - это WA. Без номера теста или каких либо еще пояснений. На вопрос о номере теста до сих пор нет ответа и check failed так и висит в summary.
Я считаю, что подобная реакция жюри недопустима (особенно в конце контеста). И, что обидно, не на что апелляцию подавать - после контеста в том коде нашли пару опечаток (но код на дорешивании всё равно получает check failed :( )
Если так смотреть, то можно и acm icpc world finals списать в тренировки.
Даже, если считать opencup тренировкой, а Снарка тренером, то почти час в конце не реагировать на check failed - это train failed.
Я негодую не столько по поводу, что с чекером что-то не так, а скорее по поводу того, что жюри не реагирует ни на вердикт, ни на клары в разумное время из-за чего совсем непонятно, что происходит с задачей.
Что меня больше всего удивляет, что никто не пишет, что столкнулся с похожей проблей в задаче 6.
Влад не смог смириться с поражением по задаче первого дня "Планетарий".
Он переписал решение с использованием информации об алгоритме генератора. Сегодняшнее "решение жюри" набирает очень много баллов=) Вроде бы 155K из возможных 159K (как-то даже не верится=) ). Желающие могут почитать код тут: http://pastebin.com/EFQpiuYM
Просто это задача далеко не на 5 часов, а как минимум часов на 12. С пятью часами времени контест превратился в "кто сможет написать и отдебажить чего-нибудь умнее рандома".
Почти час надо было потратить на понимание условия и генерации хотя бы какой-нибудь идеи. Дальше шёл процесс реализации в целом тривиальной стереометрии попеременно с попытками понять, что делает "вот та строчка в генераторе".
Несмотря на то, что в целом генератор был написан неплохо, его основная существенная часть состояла из огроменной функции "generate_map", причём понимание работы этой функции действительно давало почти единственную загвоздку для решения, а в условии задачи алгоритм её работы явно указан не был.
Также вся интрига была в максимальном значении параметра "от скольких ярчайших звёзд пытаемся плясать". Кажется, это стоило упомянуть в условии, т.к. это существенно влияет на задачу. По дефолту оно равнялось 60. В решении жюри явно фигурирует число "100".
P. S. Кажется, сейчас решение жюри можно ещё улучшить. Например, можно заметить, что в похожих созвездиях отношения расстояний от звёзд до центра - примерно одинаковые. Тогда можно сразу отсечь кучу непохожих созвездий и сравнивать их более тщательно, учитывая, что самая далёкая от центра звезда не обязательно осталась самой далёкой.
Код генератора можно было даже и не читать. Нам вот единственное, что ещё понадобилось и чего не хватало в условии, так это осознание того факта, что галактика имеет равномерно кубическую форму (посмотрели в визуализаторе). Кстати, для людей, знакомых с астрономией, это должно было быть ВНЕЗАПНО :)