История

Нам откровенно проперло с задачами ;) Решали ровно то что нужно ;))))

Не взялись за гробовые тарелки (хотя Дима по его словам прописал решение на бумажке к концу контеста) ;) К архиватору последним приступили. ;)

До этого контеста руками мне приходилось писать только сжатие по Хаффмену. Самое главное, что я вынес их того опыта, что это для сжатия текстовых данных - полное фуфло. И сжатия только с Хаффменом не получишь. Также я когда-то пролистывал одну книжку по сжатию данных (привезли ее из Питера в этом году, есть почти у всех, кто ездил ;)) и в памяти отложился алгоритм Лемпеля-Зива (очень необычный алгоритм, такой не забудешь). На эту задачу я совершенно честно потратил около 2-х часов компьютерного времени. Это было бы совершенно фатально и неправильно, если бы не было к тому моменту сдано 8 задач, или оставалось бы еще что-нибудь решенное хоть кем-то, или была бы уверенность, что пробить что-то еще удастся. В результате написано:
1. Честное кодирование по Лемпелю-Зиву (input.txt->output.txt)
2. Честное декодирование. (input.txt->output.txt)
3. Генерилка тестов (полуслучайный сжимаемый бред)
4. Генерилка тестов (полуслучайный несжимаемый бред)
5. Бинарная сравниловка файлов.
6. Генерилка искомой программы (генерится CPP-программа)

Тут оказалось, что VC испытывает необычайные проблемы с длинными строковыми константами (internal compiler error. heap overflow)

7. Декодер на Delphi.
8. Генерилка искомой программы (генерится Delphi-программа)
Главная проблема - сгенирить для бинарный данных правильную строковую константу.

Вот. Было сделано три сабмита в последние 10 минут. Но так и не срослось ;(

Некоторые мои впечатления:
1. Комплект был как по заказу под меня. Идеи все (или почти все) неоднократно появлялись на УрГУшных контестах ;) Не было задач из разряда мною нелюбимых. Неужели приберегли на второй день? ;) Все просто, красиво, аккуратно, "не мутно" ;) Спасибо за комплект ;)

A. Архиватор. Молодцы, добавили новый стандартный алгоритм в копилку ACM-ера! Мне, как я считаю, совсем немного не хватило, чтобы сдать. Писал, мучаясь, алгоритм Лемпеля-Зива ;)
B. Пирамида декана. Саша - молодец! Единственный, кто сдал ее на контесте ;) Самая, кстати, маленькая по коду задачка получилась ;)
C. Банальный prebuild. За версту пахнет ;) Сдавали очень грязно. Блин, лень было лишних пару раз прогнать переборный солюшен, нагенерить тестов!
D. Диагностика ACM. Классический ДП с длинной арифметикой. Что-то я давненько не видел ДП без длинной арифметики. "Мы с Тамарой ходим парой" ;) Первый раз получен Time Limit. Был заменнен vector<short> на short[], переписана сумма длинных чисел на вариант без явной нормализации. Результат - AC. Лишь после контеста я понял, что надо было просто уменьшить количество цифр в длинном числе.
E. Кирпичи. Нормальная задачка. Центр масс - прикольная фенечка ;)
F. Тарелки. Хорошо, что у меня в команде никто пока такую геометрию решать не умеет ;) Если бы я решал, то решал бы динамически. Тарелки бы у меня были твердами телами, которые подчиняясь некоторым законам "летали" бы по подносу, неупруго сталкиваясь и с силой трения. Появится задача на Timus'е - сдам ;)
G. К вопросу о спорте. Задача была сдана моей командой на 7-ой минуте. В чем секрет? Достаточно взглянуть на sample output, чтобы понять, что задача планируется как простая :)
H. Погоня в метро. Волна. Банально. Но красиво ;) Первый раз был получен WA. Блин, тестить надо было! Валилась на тесте, где путь состоял всего из одной вершины - тривиальщина, крайний случай.
I. ПДВАС и ПВИПАС. Хитрая нестандартная волна. Очень многие условия надо восстановить по sample'у и домыслить.
J. Классическая задачка на хитрую структуру данных. Я ее сдал, как полный cheater ;) Не зашла бы, была бы прикольная задачка ;)
Если память не изменяет, когда-то задачка на такую структуру появлялась на внутренних соревнованиях. Не путаю?

2. Организация контеста была крайне хорошей. Накладок не было. Все было дрюжелюбно, без дурацких ограничений ;)

3. Вообще играть было безумно весело сегодня ;) Особенно первые часа 2, когда шли с пермяками ноздря в ноздрю :) Безумный драйв ;) Пришел я на контест (Паша не даст соврать) жухлый-жухлый, с ноющей головной болью ;) Меня даже ГАИшник на площади остановил, поинтересовался состоянием моего здоровья ;) Про боль я забыл ровно минуте к 7-ой ;)

4. Дома и стены помогают. Безумно классно, когда человек, который приносит тебе бумажку от жюри, отдавая ее, говорит: "Давай! Давай! Мы их сделаем!". ;) Всем спасибо за поддержку ;)

5. Чего так много смайликов? Так прикольно же сыграли :lol: Погода даже радует :D

6. Играли мы, конечно, быстро. Но безумно грязно. Точно уж есть над чем работать. :oops:

PS Может каждая команда (и УрГУшная и не УрГУшная) подобный мини-отчетик напишет? Интересно же ;) Самое ценное - впечатления и опыт ;)
PPS Маленькая деталь. Моя команда сидит за машиной, играя на которой, я дважды становился чемпионом УрГУ ;) Фартовая машинка ;)

эммм.. а можно поподробнее, что есть prebuild почему он банальный?:))))а что такое ДП и почему он классический и всегда вместе с длинной арифметикой? :))))а какая именно структура? я думал на хеш-таблицы, но реализовывать даже не собираюсь:))))

вот.
P.S. а вот судя по великолепному выступлению и ФТФ и РТФ УПИ, АСМ там придется начинать с нуля либо нагло использовать УрГУшные отборы для тренировок:)) если конечно, физика и связанные с ней спецкурсы не затянут:)))

Prebuild - это решения по следующей схеме. Довольно медленная программа сначал "что-то" посчитает на локальной машине, выплюнет "что-то". Потом это "что-то" мы вставим в программу, которая на основе этого "что-то" быстро будет давать ответ.ДП - Динамическое программирование. Что этим словом только не называют. Обычно решение по сути представляет собой реализацию некоторой реккурентной формулы. Такие задачки очень часто просто встречаются. А длинная арифметика просто обычно очень естественна (чтобы результат хоть дол сколько-нибудь значительного N вычислить) ;)Тупая. Для каждого запроса храним, сколько раз он появлялся. Также храним суммарное число запросов в группах
0...999
1000...1999
и т.д.

Добавить запрос в такую структуру - O(1)
Удалить - O(1)
Ответить на вопрос, сколько запросов, больших K - O(sqrt(N)) (если N - индекс максимального запроса)Я всеми руками за конкурентноспособность УПИ! После контеста, ко мне кто-то из них подошел, интересовался возможностью совместных тренировок. Надеюсь, что действительно получится.

А вы language identificator не забыли??? :wink:
было бы 9

Блин. Это тоже сказка о моей дури ;) У меня, как я уже писал, было два солюшена. Генерящий CPP-архив, и Delphi-архив. Бил я в последние минут 20 Delphi-версию, а сабмитил из соседнего FAR'а CPP версию. Она, как я уже говорил, получает compiler error на больших тестах.

нямс упи не дает олимпиадникам преимуществ при поступлении (Рогович как-то обещал, но когда я в деканате это попросил, мне сказали, что "он погорячился", после чего я решил в УПИ не поступать, ибо некрасиво очень получилось с подготовительными курсами).

Кстати, на Тимусе русские условия отличны от тех, что мы получили сегодня. Вроде бы по мелочам, но...

2 солюшена, которые сегодня получили AC, получили ML. Хорошо, что Саша все еще не научился измерять расход памяти ;)

Но в лучшую (уж поверьте) сторону. Просто на тимус задачи были загружены заранее, а бумажную версию вычитывали и вылизывали до самого последнего момента - доходило даже до полных замен сказок - это видно, если сравнивать с английским тимусом. Возможно поэтому кларифов практически не было.

Летающие тарелки получил, завтра вечером погоняю на другой машине (здесь cpp нет), но похоже на правду. Какое пиво ставить?