Dimka_ptz 12 ноя 2009 в 21:10

Полуфинал ACM ICPC 2009-2010

1 мин

1.4K

Спортивное программирование*

+10

Комментарии 27

Assargin 12 ноя 2009 в 21:22

Ну особых сенсаций с ПетрГУ не вижу, они всегда блистали на этих соревнованиях. Один мой знакомый приехал в Тольятти оттуда как раз, отучившись в их матшколе, во всем нашем потоке не было кого-либо, равного или превосходящего его в программировании.

Dimka_ptz 12 ноя 2009 в 21:25

Его случайно не Глеб зовут?

Assargin 13 ноя 2009 в 10:19

Именно ))

Danov 12 ноя 2009 в 21:49

Поддерживаю. Сам команду выводил в 2004/05 в полуфинал. Петрозаводск и тогда очень высоко в рейтинге поднимался.

Dimka_ptz 12 ноя 2009 в 21:54

Ну они не были фаворитами. В том что они попадут в 10ку были уверены практически все, а вот то, что ПетрГУ обойдёт МГУ и ИТМО мало кто предполагал, даже сама команда.

Danov 12 ноя 2009 в 21:57

Ну чтож, я рад за ПетрГУ. Поздравляю с заслуженным успехом!!!

barabashka 12 ноя 2009 в 23:21

Я бы прочитал разбор задач, а то интересно как некоторые решаются)

Dimka_ptz 13 ноя 2009 в 08:19

Если будет интересно, то могу написать краткий разбор 5 самых простых задач полуфинала (B,D,F,J,H).

barabashka 13 ноя 2009 в 11:16

С удовольствием бы прочитал F и J. Мы F вот чуть чуть не добили — словили TL, который кажется убирался одним ифом, а J даже не пытались решать. Писать контест вдвоем оказалось сложно, дурацкий грипп)
Еще интересно как в A центр масс искать, какое нибудь разбиение на тетраэдры?

Dimka_ptz 13 ноя 2009 в 11:25

A — разбиение на тетраэды и нахождение расстояний до граней.
в F надо было использовать очередь с приоритетами, тогда точно никакого TL бы не было
J — динамика с бинарным поиском.

А вообще, будет сободное время — напишу разбор, мб даже и тех задач, которые я не знаю как решать (надо будет покурить решения жюри)

barabashka 13 ноя 2009 в 11:50

Спасибо (сорри, карму не могу добавить)

да, с A так и думал.
в F у нас видимо было дело не в очереди с приоритетами — она у нас была) Там перебираются все варианты наборов букв попадающих в данные слова. И они упорядовачиваются по количеству слов в которые попали. Ну не все наборы надо строить, а вначале в очередь положить пустой набор, и на каждом шаге выбирать из очереди максимальный и из него строить новые. Как то так, да?
J — а динамика по чему?

Dimka_ptz 13 ноя 2009 в 12:18

по F — да, похоже на правду :-)
по J: параметры динамики — номер текущей группы вопросов, количество уже набранных правильных вопросов, количество уже набранных ответов. А само значение динамики — максимальный размер группы (количество вопросов в ней). Правда я, немного, наврал, там не будет бинарного посика, а будет перебор по минимальному количеству вопросов в группе.

barabashka 13 ноя 2009 в 18:10

интересно) осталось мне подумать и понять почему так)

НЛО прилетело и опубликовало эту надпись здесь

scorzh 13 ноя 2009 в 14:17

Ну они не то, чтобы слили. Скорее IFMO 2 хорошо сыграли.

Dimka_ptz 13 ноя 2009 в 14:28

Скорее они слили. Они должны были выиграть. Если судить по последним контестам, именно IFMO 1 самая сильная команда в России, ну и IFMO 2 тоже молодцы :-)