Ну что, делимся впечатлениями, признаемся, кто участвовал, в какой команде и что нарешал? Ужасно не хватает более детальной информации по контесту — стран участников и общего балла явно недостаточно :-)
Список команд:
| Место | Команда | Состав |
|---|---|---|
| 1 | Havka-papstvo | Egor, Petr, pashka |
| 4 | Charles_University_Legion | fhlasek, Mimino, k21 |
| 5 | Progopedia | maksay, kit1980, Nickolas |
| 8 | Unpretired | Michael, ilyakor, Василий Астахов |
| 9 | DrinkLess | arseny30, valich, levlam |
| 13 | _NiN_ | ashmelev, mmatrosov, Антон Демидов |
| 14 | Saratov.SU2.Retired | ralekseenkov, ivanromanov, Igor Kulkin |
| 16 | petrsu_ginger | Eledven, zurg, Jughead |
| 18 | despise_oimaster | sevenkplus, wuzhengkai, Zekun Ni |
| 20 | any_random | Zhukov_Dmitry, zeliboba, ifsmirnov |
| 22 | PigsAndHedgehogs | Joshik, andrewzta, dgozman |
| 27 | Accept_iterator | asaveljevs, ulzha, visockas |
| 33 | PMP_Forever | poopi, Mohammad_JRS, piloop |
| 34 | KNURE_Team | SkorKNURE, DryukAlex, Daiver19 |
| 36 | LT_United | Leonid, KrK, Lomir |
И немного впечатлений от Progopedia в моем лице. Самое яркое впечатление, конечно, оставила задача A Triangles; у меня ушло 5 неправильных сабмитов и гораздо больше эмоциональных высказываний на то, чтобы выяснить, насколько вырожденными могут быть треугольники по этому определению; вот такие
1
11
x.x
x..x
нашлись достаточно быстро, над вот такими
2
22
2.x
x..x
пришлось поломать голову, но вот такие
x
33
3.x
x..x
меня просто убили — совершенно контр-интуитивно. Нет, сама мысль интересная, но мне кажется, что с относительным скорингом (и без пенальти!) эта задача была бы гораздо симпатичнее. После прояснения вопроса с вырожденными треугольниками я отдала эту задачу maksay.
В задаче F Currency Hack меня впечатлило, как ее решил kit1980 — программа на Python читала условия и генерировала программу на Prolog, которая делала все остальное. Вот уж поистине, правильный инструмент для конкретной задачи!
Наконец, задача D If мне понравилась очень, но в нашем интерпретаторе где-то была ошибка — например, в первом тесте он утверждал, что программа всегда выводит 5 независимо от вводов, что оказалось неправильным. Поэтому все оптимизации кодов по этой задаче сделаны вручную лично мной :-) Ну и немного огорчил штраф за неправильные посылки — у меня таких набралось несколько штук, в основном из-за того, что я не сразу разобралась с синтаксисом вывода, и еще пара странных рандомных ошибок.
К решению B и C (а нерешенной у нас осталась только E Beacons) я была совершенно непричастна (обе они на счету maksay), поэтому осмысленно прокомментировать затрудняюсь. В целом контест мне понравился, следующий пункт — втиснуть в плотное расписание на весну поездку в Будапешт :-)
Мы, команда PigsAndHedgehogs в составе Joshik, andrewzta и dgozman заняли 22 место и собираемся поехать в Будапешт :)
На контесте мы довольно быстро начали писать A и B. Когда программа выдала по A1 ответ 40, начали все-таки вглядываться в рисунок и нашли все 3 хитрых случая (благо сама программа их нарисовала). А вот с задачей B случилась большая неприятность. Достаточно быстро к ней написал решение andrewzta и послал B1, получив WA при этом. Тест руками проверить было невозможно, поэтому начали проверять программу, что и продолжалось в итоге в течении почти всего контеста, пока в начале последнего часа я не написал совсем тупое решение, которое выдало такой же ответ. Тогда мы подумали, что возможно какую-то фигню отправили в первый раз и я переслал свой ответ, который прошел! Но, тут, начав отправлять ответы с компьютера andrewzta, мы все равно получали WA, а с моего — OK. Как оказалось, у них была проблема с виндовыми переводами строк, а я, к счастью, с утра достаточно случайно взял линуксовый ноут вместо виндового:) В итоге из-за этого мы потеряли 200+ баллов и не успели получить ответ на B10.
Ну, а помимо этого, dgozman достаточно быстро сдал C и погенерил ответов для некоторых тестов из D, что, видимо, стало ключевым.
В задаче E достаточно легко получили Дб, на которых было слышно каждую частоту, с помощью Audacity, но вот точно восстановить точку из этих данных не получалось — не хватало точности — в итоге только E1 сдали. К F не прикасались — не хватило времени.
В общем, если бы не проблемы с B, над которыми мучались весь контест, решили бы значительно лучше и получили бы больше удовольствия!
P.S. предлагаю в основном посте собирать составы команд.
О нет, пропустил, почему никто не предупредил заранее :(
Насколько заранее? Я писала об этом контесте за месяц, как только регистрацию открыли: http://codeforces.com/blog/entry/3700
Странно, что я не видел тот пост. По-моему, было бы хорошей практикой бампать пост комментарием за пару дней до соревнования. В любом случае, мой комментарий выше задумывался как пустое нытье, не обращайте внимания :)
Кто же пишет заранее о контестах, где надо войти в топ 30? ;)
Расскажу с нашей точки зрения (Havka-papstvo, Egor Petr pashka) Начали мы писать контест вдвоем, так как pashka в это время ехал из Давоса в Цюрих. Первыми довольно быстро мы написали А и С — я А, а Petr С, они были сданы на ~40 минуте с разницей меньше минуты. Затем я занялся F, а Петя — B. Где-то в начале второго часа присоединился pashka. Петя сдал по В все тесты, кроме последнего — у него оказалась хитрая бага, при которой возникала бесконечная рекурсия и он очень удивлялся, что это не проявилась на остальных тестах. Я тем временем прошел семпл и первый тест, но мое решение оказалось негодно для всех остальных. pashka занялся D и в итоге почти все время провел оптимизируя решения по умолчанию (которые послать, конечно, было просто обязательно — они набирали довольно много очков), но за час до конца дал ключевую идею по F — симплекс метод. В итоге я свою программу по F переписал в генератор инпутов lpsolver, Петя написал E, но расстояние на семпле было чуть более 2 метров. В итоге пройти сначала 5 тестов, а потом еще 2 помогла моя идея о том, что мощность каждого динамика от теста к тесту не меняется. Вот, собственно, и все — отмечу еще тот факт, что мы писали контест из 3 разных стран
Решил пробить, в гугле, что за название... После этого видео все стало понятно)) http://www.youtube.com/watch?v=hxHKGV4LY34 :)
Ну, вряд ли так уж все ;) Я, когда вбивал это название, ролика совершенно не помнил, конечно
Есть еще http://community.topcoder.com/stat?c=problem_statement&pm=9943 (см. сэмпл тесты)
А по какому принципу посты на главную помещаются?
1) Пост должен быть интересным 2) Пост должен быть не на отвлеченную тему 3) Пост должен быть и на русском, и на английском языках
Все верно. Кроме того пост должен быть содержательным, грамотно написан и аккуратно размечен.
Возможно, это мое субъективное мнение, но неужели этот разы содержательней и грамотней десятков других интересных постов?
На этот раз писал в составе команды NiN вместе с mmatrosov и Антоном Демидовым (финалист ACM ICPC 2003 и 2004 годов в составе команды ННГУ). Заняли 13 место. Понравилась задача C, но и D очень забавная, жаль, что только в самом конце за нее взялись.
Мы — Unpretired (8 место), состав Michael, ilyakor и Вася Астахов.
По поводу впечатлений (расскажу свою личную точку зрения) — весьма своеобразный контест, не очень похож на ACM. Стратегические решения тут возможно даже важнее, чем умение решать задачи. Например, для меня было неожиданностью узнать после контеста, что по задаче B можно было сделать 8 тестов из 10 тупо квадратом, и не надо было писать всякие kd-деревья. Ну или задача про оптимизацию программы — кто ж знал, что они дают кучу баллов за сабмит input'а :) Ну а в целом — прикольный контест, особенно порадовали "4" треугольника в 1 тесте задачи A и комментарии Michael по поводу py-glpk в процессе решения задачи про обмен валюты :)
10 из 10 ;) Достаточно при построении графа посортировать все точки по Х-у и для каждой проходить только интервал [x-R,x+R] в попытках строить ребра. Это и так самая затратная часть решения, дальше выделение верхних компонент двузвязности очень быстро работает. После прикрутки этого ограничения вместо просто двух циклов на последних двух тестах оно точно до минуты работало.
Мда, после 5 лет ACM совесть не даёт такое писать :) Надо мне переучиваться :)
9 и 10 тест не смог сдать изза сегфолтов на больших тестов. графы какие-то жесткие получались. Вроде 6гб на 2графа насчитали.
хотя не совсем это.
Составы еще 2 команд (надеюсь, они не против оглашения):
DrinkLess arseny30 valich levlam
petrsu_ginger Eledven zurg Jughead
Our team was PMP_Forever. We got 33th.
Team members: poopi, Mohammad_JRS and piloop
We are Charles_University_Legion and we were 4th.
Team members: fhlasek, Mimino, k21.
We are despise_oimaster, we got 18th.
Team members: sevenkplus, Zekun Ni, and wuzhengkai
Команда: any_random
Состав был такой: Zhukov_Dmitry, zeliboba, ifsmirnov
Team: KNURE_Team;
Competitors: SkorKNURE DryukAlex Daiver19;
Results: A (10 cases), B (9 cases), C (10 cases), 34-th place.
We would like to go to Budapest, but are not sure that 34-th place will be enough to get there. We would be greateful if teams advanced to finals but are not able to visit it will write about this in comments. And congratulations to all teams from Top30!
Saratov.SU2.Retired — ralekseenkov, Igor Kulkin, ivanromanov — 14е место.
Никто не знает, команда CROTEAM (29 место) — это реально из Croteam или просто назвались так же?
We are LT_United, 36th place. Leonid KrK Lomir
Accept_iterator = asaveljevs, ulzha, [user:visockas] — ranked 27.
We did A, B, C and some trivial points on D.
Inspected F and got the gist of flows that were a little unusual, but out of lack of confidence in inventing them moved on to E. Got devastated with that as well.
Полный и насыщенный обзор.
Invitations are out there out http://ch24.org/team/list. While top-50 are invited, note that only top-30 out of those who accepted will be confirmed for the finals.
Our team was Sparrows24 (26th place). The other two members of my team have no codeforces account, but their Topcoder handles are edx and saraedum2.