?

Log in

No account? Create an account

elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
NEERC 2014 завершился
elizarov

Очередные, 19-е, соревнования Северовосточного Европейского Региона Студенческого Командного Чемпионата Мира по Программированию (NEERC) завершились. В следующем году нас ждут юбилейные, 20-е соревнования. Таблица результатов доступна на сайте соревнования. Победителем стала команда Санкт-Петербургского Университета ИТМО (Короткевич, Минаев, Васильев). В этом году борьба было очень напряженная. Первая команда Московского Государственного Университета (Евстропов, Пядеркин, Омельяненко) дышала в спину победителям и даже обходила их в один из моментов соренования. Обе команды решили по 9 из 11 задач, оторвашись на 2 задачи от остальных команд.

В этом году 15 сильнейших вузов нашего региона получают право участвовать в Финале Чемпионата Мира по Программированию ACM ICPC — самом престижном соревновании среди программистов в мире. Финал Чемпионата пройдет 16-21 Мая 2015 года в г. Марракеш, Марокко, где соберутся более 120 команд сильнейших вузов мира, чтобы бороться за звание Чемпиона Мира. NEERC по праву считается сильшейшим региональным соревнованием планеты. Победители NEERC становились чемпионами мира 6 раз из последних 10 финалов, включая все три последине года. Очень надеюсь на продолжение этой замечательной традиции и в этом году.

Огромное спасибо всем организаторам, волонтерам и спонсорам соревнования. Особенно хочется отметить технический коммитет соревнования, уже многие многие годы возглавляемый Матвеем Казаковым, и обеспечивающий бесперебойное и слаженное проведение соревнований. Отдельное спасибо нашему члену жюри Петру Митричеву, благодаря усилиям которого, мы оживили церемонию награждения, показав анимацию стратегии команды ИТМО в задаче G. Побробности смотрите в блоге Петра.

Условия задач выложены на сайте соревнования здесь. В этом году, после 5-и доступных всем задач A, B, F, J, и K, сложность резко возрастала. Только 35 команд решили больше 5 задач, в основном за счет задачи I. Я очень разочорован тем фактом, что мало команд решили задачи C и D. Задача C, решенная только двумя командами-лидерами, была доступна абсолютно всем командам ибо не требовала каких-либо специальных знаний и уже её точно можно было спокойно написать за последний час соревнования. Более того, в отличие от задачи I, которую многие пытались решить не успешно, задачу C было очень легко отладить на приведенных примерах. Её просто было нельзя сделать неправильно. Большое разочарование вызвал и тот факт, что задача F оказалась для учатников наиболее сложной из 5 простых задач. Складывается ощущение, что сложность задачи просто пропорциональна суммарному объему условия и кода решения. Конечно есть и усключения, вроде задачи H, правильное решение которых просто очень сложно придумать, и, даже придумав, очень сложно реализовать правильно. Интересно, проводил ли кто-нибудь такой анализ?

Краткий разбор задач я выложил здесь. Медиа-центр ИТМО записал видео разбора и выложил его здесь.


  • 1
"Задача C, решенная только двумя командами-лидерами, была доступна абсолютно всем командам ибо не требовала каких-либо специальных знаний и уже её точно можно было спокойно написать за последний час соревнования. "

Лично меня 'надоело' читать условие где-то к середине второй страницы. Задача на три листа A4 имеет очень хорошие шансы быть прочитанной только в ситуации "все остальное безнадежно не решается".

И это достаточно разумная стратегия, так как налажать, не заметив какого-то требования, отраженного в тексте, но не отраженного в примерах - элементарно при такой длине условия.

"Складывается ощущение, что сложность задачи просто пропорциональна суммарному объему условия и кода решения" - сложность или нерешаемость? В нынешних ICPCшных соревнованиях фаза выбора подмножества решаемых задач стала гораздо заметнее.

Решаемость задачи это все-таки P(задача решена|задача получена).
Нерешаемость - P(задача не решена|задача получена).
А сложность задачи - это P(задача не решена|было принято решение решать задачу)
===
Собственно, все это сообщение о том, что P(было принято решение решать задачу|задача получена) - существенно не константа. И монотонно убывает по длине условия задачи. Неужели это для тебя новость? :)

Edited at 2014-12-08 10:20 am (UTC)

Всё так. Задача C специально была специальна сделана такой. Концептуально простой, но с большим условием (и кодом). Именно для того, чтобы продемонстрировать командам ошибочность их стратегии по оценке вероятности сдачи задачи. Не умение внимательно читать и вникать в условия задач это чуть ли не самый большой пробел у многих команд.

Естественно, если у команды решившей 5 задач менее чем за 4 часа соревнования (а таких было очень много) было придумано решение задачи I, то надо было его реализовывать (это быстро) и сдавать. Там как раз в задаче I такие ограничения на n, что, не придумав правильного решения, бессмысленно её даже начинать писать (точно не пройдет).

Тем не менее, мы видим по таблице результатов, что огромное число команд в качестве 6-ой задачи безуспешно пытались сдать задачу I и, похоже, на это и потратили всё время. Я не понимаю, зачем было пытаться сдать задачу I не имея к ней решения? Разве не очевидно что задача требует точного и эффективного алгоритма и не придумав его это пустая трата времени? За это время можно было спокойно написать задачу C и точно сдать её с первой попытки. В ней почти невозможно было набагать.



Edited at 2014-12-08 12:37 pm (UTC)

Ой, ржу еще сильнее.

Рома, вот как ты думаешь, в заочном кружке для 0-4 классов дать задачу (в параллель четвертого класса), которая формулируется в терминах математики начальной школы, но решается с помощью дифференциального исчисления - это здравая мысль?

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

Видать назрела у вас ротация. Составители тура напрочь забыли, что есть студень. И им пора перейти в раздел улыбающихся и жмущих руки, организующих призы etc. А тур пусть народ лет на 5-10 младше составляет.
ННЛ, есличо.

Re: Ой, ржу еще сильнее.

Не могу не прокомментировать

1) Это полуфинальные соревнования, поэтому цель - отобрать лучших студентов, а не сделать их жизнь легче. И, судя по результатам представителей нашего региона на финале, Роман и его команда отлично справляются с этой задачей. К тому же выбрать лучших из 1000 команд в нашем регионе это непростая задача. Уровень начальной подготовки растет и растет конкуренция. Поэтому и задачи должны становиться более непрямолинейными.

2) Когда я слышу про ротацию я тоже улыбаюсь, но как-то грустно. У меня за 15 лет организации этого мероприятия была целая армия теоретиков, говорящих про усовершенствования и нововведения в мероприятие. Но факт остается фактом - большинство членов оргкомитета работают там от 10 лет и больше. Почему? Потому что теоретики не готовы работать во благо мероприятия, а готовы только давать советы "как лучше". Так что, если хочется ротации - вперед! - приготовьте свою задачу и предложите на следующий полуфинал. А лучше две. И пусть они будут более "правильными", чем те, что есть сейчас.

С наилучшими пожеланиями,
Матвей

Re: Ой, ржу еще сильнее.

Мы постоянно экспериментируем. Задача с 3-мя страницами условия (задача C) была у нас в первый раз. И, кстати, оказалась таки не самой сложной. Несмотря на мое разочарование, её все-таки решили 2 сильнейшие команды, в то время как задачи G и H -- нет. И решение задачи C от ИТМО очень компактное и ушло у них на неё по их оценкам около 20 минут.

При этом ИТМО 1 было очень близко к тому, чтобы решить G (будь у них больше времени), а БГУ были близки к решению H. Совсем нерешаемых гробов в этом году не было. Были шансы распечатать все задачи.

  • 1