Архив форума

Ну вот. Все кончилось ;) Все для нашей команды сложилось удачно. Наконец-то нашел в себе силы рассказать, как это было во второй день.

Общие впечатления. Начали мы классно. Все шло как по нотам. Задачки решались, писались и заходили. Где-то после второго часа что-то перекосячилось, и все начало валиться из рук. Но к чести моей молодой команды, мы проявили волю к победе, вытянули все, что надо было вытянуть, и не дали победе ускользнуть из рук.

Заметки по задачам.
A Hail. Геометрия. Nothing special. Косячили мы знатно. Зашла после того, как мы прочитали clarification жюри. Самое удивительное в том, что мы и сами понимали, что условие можно трактовать неоднозначно. Почему не задали вопрос? Вопрос ;)
B Logarithm. Жесточайшая задача. Оптимизация до оператора. Что называется, били-били и наконец добили. Написал с самого начала бинарный поиск. Сначала ловил WA Test#3. Написал тупое решение с делением на 10. На случайном тесте нашел ошибку в бинарном поиске (стыдно, товарищи, стыдно :oops: ). Поправил. TL Test#10. Оптимизация бинарного поиска (предподсчет левых и правых границ по старшим битам числа). TL Test#10. Вызов "аппаратного" log10 для чисел с тремя нулевыми старшими int'ами - AC. Уффф ;)
C The Hotel. Тривиальная задача.
D Graph decomposition. Нарисовал. Придумал эвристику. Сам себя убедил в ее правильности. Submit. AC ;)
E Floor indicator. Уффф.... Ну и задача. Задача на "предподсчет" на бумажке. Но какой. Голову сломаешь ;) Замечательна история AC на эту задачу. Мы получили WA #11. Долго не могли найти ошибку. От безнадеги я начал "силой" её пробивать. Делал это так. Мутировал куски алгоритма, надеясь понять, на какую ветку Test#11. Итак. Вставил где-то return 0;. Test #10. WA. Так. Следующая строчка кода выглядела printf("2"); Я (решал, писал и хоть что-то в задаче понимал Саша, я лишь ее "сдавал" :wink: ) меняю ее на printf("1"); AC!!!!!!!!!! Видели бы эйфорию моей команды после этого. Вот это фарт :D ;) Потом мы поняли, что это правильно, но это было совсем для нас не очевидно. Саше респект. На каждом из туров он решил по задачке, которую больше никто не сдал :D
F Spy. Блин. Обратный Burrows-Wheeler. Я воздерживаюсь от комментариев. Кто "в теме", те поняли, почему я ничего не комментирую 8)
G Classmates. Не решали. И не жалею ;)
H Extra spaces. Блин. Я сначала не так прочитал условие. Меня перемкнуло, сказалась усталость, и мы эту, в общем-то простую задачу, так и не решили, а значит и не сдали.
I Dirt. Волна. Прикольно мы её на 13-ой минуте сдали? :lol: Мне потом рассказали, что то решение, которое мы сдали, жюри изначально предполагало "резать" ;) Зашла она за 18.5 секунд при TL=20 секунд, и при наличии решения за 0.5 сек. Но я не унываю. Получил бы TL - придумал бы что-нибудь. Представляю, что по поводу этого думает команда Яковлева, убившая на эту задачу часа 2 в совокупности ;)
J Bottle taps. Перебор. С тонкостями. Прочитав ее в первый раз, я не понял, что она простая. Но увидев на мониторе, что ее сдает вся лидирующая группа, я ее решил. Психология, чтоб её :lol:

Да... Выигрывали у Назарова 4:2, потом проигрывали 8:5. Потом сравняли до 8:8. Команда Уфы ничего не сдала в последние 2 часа. Что надо сказать? Спасибо, наверное ;)

Сейчас в моих планах сдача сессии :lol: А потом? Тренировки. В Питере надо "выстрелить". А иначе зачем туда ездить? :twisted:

На разборе, награждении, банкете и после было классно ;) Мне понравилось :)

Кубок Чемпионов Урала рулит! :P

Пожалуй тоже расскажу как это было.

По задачам (в том же стиле :) )

A Hail. Не читали где-то до 3:30 от начала пока не сдали Назаров и компания (точно знаю, что геометрию пишет не он сам). Простейшая задача - почти на одну формулу. Submit. WA. Printer. Исправил 2 символа. AC. Clarif, кажется, как раз между сабмитами пришел, но на мое понимание задачи он никак не повлиял.

B Logarithm. У нас было только лобовое решение с длинной арифметикой. Никаких шансов! А ведь можно было прекалк сделать, додавили бы потом. Хорошо хоть времени много не потратили.

C The Hotel. Мы ее вторыми сдали :)

D Graph decomposition. Появилась эвристика, обсудили, контр-примера не нашли, убедили друг друга, что она правильная. Sumbit. AC.

E Floor indicator. Никто не читал даже полностью :oops: Хоть я и понял примерно, что сделать требуется, решать не стал (никто не сдает, что браться?)

F Spy. Блин. Блин. Блин. Я, если можно так сказать, "в теме" :) . Я читал алгоритм Burrows-Wheeler накануне контеста. Прочитал введение, посмотрел картинки, понял, что мне неохота разбираться и отложил книжку. Блин. Блин. Блин.

G Classmates. Набили наскоро простенькую эвристику (даже сказать стыдно какую :oops:), WA test#2, бросили, потом вернулись, придумали решение, которое паросочетание использует (помните на разборе Атнашев сказал, что он паросочетания в этой задаче писал?), но реализовывать это уже не было времени. Жаль. :(

H Extra spaces. На последних минутах сабмитили, получили TLE test#1, удивились, Серега поправил что-то, но было поздно. Но там все равно WA test#1 был. Не так решали :(

I Dirt. Кое-кто на 13-й минуте сдал, а мы на 298-й! Писать начали сразу. Первое решение, похоже, было правильным, но ловило TLE test#16. Подумали, решили делать все по-другому, Серега переделал свое решение (думаю довольно сильно, если не полностью). Submit. WA test#22. Еще несколько попыток, бросили задачу. Примерно через час от нечего делать (во как бывает!) я взялся писать эту задачу с нуля. 20 минут, WA test#22. Как так? 2 независимых решения получают одинаковый вердикт! Сейчас понятно, алгоритм-то один и тот же. Бросаем задачу еще раз. На этот раз совсем хороним. За 20 минут до конца опять же от нечего делать я решил переделать алгоритм. Сел, написал. Не работает. Я пустил Серегу добивать H. Минут через 10 напечатали. (Тут ошибка, надо было сразу печатать.) Нашел ошибку, исправил, послал, AC (за 2 минуты до конца!). Ладно хоть так кончилось. :)

J Bottle taps. Обычный бэктрекинг, сдали с первого раза. Как я выяснил, мое решение работало в 4 раза быстрее, чем у жюри. :)

Жутко на монитор было смотреть, сначала проигрывали 1:4, потом 2:6, потом 3:8, мы сдаем одну, а все остальные - две! Было время - имели 1 плюс и 3 минуса на разные задачи. Грустно.

Сдали только те задачи, которые просто не могли не сдать, и больше ничего не смогли :(
Неудачно сыграли :(

А кубок Чемпионов Урала действительно рулит! :D

УрГУ-2 МОЛОДЦЫ!!!

на тимусе - режут. хады...

вопрос по задаче о графе: почему граф 1-2, 2-3, 1-3 нельзя "представить списком смежных ребер"? :shock: только не надо отвечать "потому что число ребер в компоненте связности нечетное" - это проблему не проясняет... пронумеруем ребра соотв. 1==(1-2), 2==(2-3). 3==(1-3), тогда список смежных ребер будет таким же - 1-2, 2-3, 1-3. какое тайное знание требуется, чтобы понять, что это представление не удовлеворяет условиям задачи?

Я не понимаю обозначения 1-2, 2-3, 1-3.
А тайное знание здесь простое - надо стирать в графе ребра ПАРАМИ, причем в каждой паре должна быть общая вершина. Если таким образом можно стереть все ребра - ответ "Да", иначе "Нет".

условия просты: откуда следовало сделать вывод, что все ребра в представлении должны быть различными? видимо, это "и так все знают", как было с input.txt на отборе... ;)

В общем, их надо стирать. Сказку про стирание просто не успели перевести, и в комплект попало то, что там есть сейчас. По-русски, кстати, это называлось "Разложение графа" - что подразумевает разбиение на пары.

Господа, внесите ясность - эту задачу жюри все-таки решало динамикой? И просто не смогло обрезать переборы?

PS Ввообще все так же хочется увидеть текст разбора.

Только что спросил Дена, мол как ты догадался, о чем там речь. Дык он только с третьего раза начал понимать, что же собсна мне не нравится в формулировке... Видимо, дяденька Шеврин таки искалечил мой моск, и теперь извилины не в ту сторону завернуты, что у всех осталньых :lol: А ВЫ ЗНАЕТЕ, ЧТО БЫВАЕТ, КОГДА В АУДИТОРИЮ ЗАХОДИТ ПЕДАНТ?:twisted: :twisted: :twisted:

По поводу задачи G (Classmates). Не найдя описания решения, проясню.
Самый обячный тупой перебор в лоб. Не требуется даже паросочетания (ограничения то N<=6 или 8 не помню).
Единственное только надо запоминать варианты, которые уже проходили. Все. Сдал в online со 2 раза (первый раз забыл варианты запоминать), написал за 30 минут.