Форум DL

Мой профиль

Текущее состояние в Летнем Кубке - 2010

------------------------------------------------------------

Окончательное состояние в Весеннем Кубке - 2010
(последнее изменение - 28 мая, 16.27)

1. Кулик Сергей - 3 разбора
2. Малышев Егор - 2

------------------------------------------------------------

Окончательное состояние в Зимнем Кубке 2009-2010
(последнее изменение - 26 января, 18.12)
1. Малышев Егор - 12 разборов 2. Грицкевич Евгений - 7 3. Колесов Алексей - 5 4. Короткевич Геннадий - 4 5. Бардашевич Адам - 2 6. Кулик Сергей - 1
Открыт курс "Подготовка к IOI 2010", куда перенесены все нерешенные задачи из "Подготовки к IOI 2009" и куда по традиции собираются все задачи, из решаемых нами по воскресеньям, которые НИКТО не смог решить.

Курс тематически реструктурирован (по сравнению с "Подготовкой к IOI 2009), надеюсь, так будет удобнее и интереснее. После решения задачи в этом курсе ОБЯЗАТЕЛЬНО нужно написать разбор своего решения и выложить сообщение в этой теме и ссылку на свой разбор в виде

link: Название задачи URL(на форуме)

В конкурсе "Летний кубок 2009" (и последующих Осеннем, Зимнем и Весеннем кубках) побеждает не тот, кто больше всех решил задач, а тот кто больше всех ОПИСАЛ РЕШЕНИЙ задач, которые решил. Допускается делать повторные описания ОТЛИЧАЮЩИХСЯ решений (описаний).

Добавление от 13 декабря 2009 года

Для того, чтобы претендовать на добавление балла за альтернативное описание в Зимнем Кубке
В дополнение к описанию (в конце его) ЯВНО указывать РАЗЛИЧИЯ
- то есть
1) Что нового и полезного может почерпнуть читатель из второго разбора в дополнение к первому
(новый прием решения, новую реализацию и т.д.)
2) Сравнение обоих решений по производительности, памяти, сложности кодирования и отладки.

Объявляется дополнительно вторая номинация в Зимнем Кубке "Подготовка к IOI 2010"
кто больше всех решит задач.

Мой профиль

А если на задачу уже есть разбор , но она расположена в ИЛИ 2010 ? ) то +0

Мой профиль

Поясни подробней и сделай ссылку - о какой задаче речь.

Мой профиль

Неудача в первый день Игоря Брюкова, связанная с тем, что он
смог придумать, но не смог реализовать на 100 баллов решение задачи
с использованием сложной структуры данных (сбалансированное дерево,
в его случае) подтолкнула меня к мысли сформулировать более строго,
в каких направлениях нужно готовиться к IOI, почему и как.

Мои соображения основываются как на личном опыте из анализа тематики
задач, которые мы решаем в последние годы, когда сборная Беларуси
целенаправленно готовится к IOI на базе Гомель+DL, а также на беседах
с тренерами других команд (России, Грузии, Армении и др.) и статье
Тома Верхоефа, посвященной анализу направлений развития тематики
и сложности задач IOI от первой до последней (20-ой) IOI.

20 Years of IOI Competition Tasks (149-166)
Tom VERHOEFF

Я бы выделил следующие акценты:

Исследования и теоретическая подготовка
Динамическое программирование
Сложные структуры данных
Графы и деревья
Решение композиционных задач (гробов)
Перебор и автоматизация тестирования
STL и переход на C++
Альтернативные подходы

Чтобы мой текст далее не изобиловал фразами "по-моему, как мне
кажется, с моей точки зрения" и другими подобными, сразу оговорюсь,
что везде далее излагается моя точка зрения и я с удовольствием
выслушаю и обдумаю точки зрения других людей на поднятые вопросы.

Исследования и теоретическая подготовка

Глобальное стремление ребят, которые сейчас верховодят в Scientific
Commettiiee, где собственно и разрабатываются задачи - давать такие
задачи, для решения которых нельзя просто, прочитав задание, сразу знать
решение, если ты изучил соответствующую теорию. Они стараются придумать
такие задачи, чтобы для придумывания решения было необходимо ИССЛЕДОВАТЬ
задачу как проблему, часто даже написать вспомогательные программы,
которые облегчат это исследование. На основании этого исследования
требуется выдвинуть ГИПОТЕЗУ и проверить ее руками или переборным
решением, и только потом писать полное решение задачи. Понятно, что
чем больше теории знаешь, тем быстрее может закончиться исследование,
поскольку богаче арсенал решающего. Кроме того сам процесс изучения
теории, будучи грамотно организованным, должен развивать навыки
исследования решаемой задачи.

Динамическое программирование

Одним из главных для IOI-подобных олимпиад методом решения задач
с предварительным исследованием или без него, является динамическое
программирование (рекуррентные соотношения). Вводится пространство
состояний (от двух, трех и более параметров) и рекуррентная формула
перехода к последующим состояниям от предыдущих (при заданных начальных),
обычно задействующая несколько арфиметических операций и max/min.
Часто возникают проблемы с оперативной памятью и приходится прибегать
к "послойному просчету и хранению" или/и битовому кодированию и обработке
одного или нескольких параметров состояния.

Сложные структуры данных

Как правило, простейшие решения задач довольно очевидны, однако полные
баллы за задачу часто можно получить, только изменив порядок сложности
вычислений решений - к примеру перейти от сложности O(n^2) к O(n*logn).
Универсальное средство решения подобных проблем - использовать
(предварительно изучив теорию и многократно применив на практике)
сложные структуры данных, которых даже нам уже известно превеликое
множество (см. специальный раздел курса "Методы алгоритмизации").
Еще круче научиться МОДИФИЦИРОВАТЬ известные структуры данных под
нужды конкретной задачи или даже РАЗРАБАТЫВАТЬ новые сложные структуры
данных и/или новые способы их реализации.

Графы и деревья

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

Решение композиционных задач (гробов)

Часто задача на IOI - это синтез всех или нескольких из этих тем, например:
"Динамическое программирование на графах с использованием сложных
структур данных после тщательного исследования проблемы". И тут появляется
НОВОЕ ТРЕБОВАНИЕ - умение писать и отлаживать решения сложных задач -
попросту говоря ГРОБОВ.

Ну и три практических совета

Перебор и автоматизация тестирования

У профессионалов не должно быть случаев, когда решение придумано,
закодировано, протестировано (как потом оказывается ЯКОБЫ), а 100
баллов не берет.
Как с этим бороться
1) Чуть медленнее и вдумчивее писать
2) Стараться писать как можно ОДИНАКОВЕЕ (в идеале тождественно,
включая названия переменных) стандартные коды, что в некотором
смысле обеспечивает "повторное использование кода".

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

STL и переход на C++

Последний пример - с Брюковым - он не смог сделать вручную то, что на C++
с использованием STL просто обеспечивается вызовом ЧУЖОГО ОТЛАЖЕННОГО
многократно использованного кода :-(

Претендентам на IOI нужно рассмотреть альтернативы
- научиться беспроблемно писать сложные структуры данных
- перейти на С++ и получить навыки использования STL.

Поскольку не все и не всегда структуры STL работают эффективно для
конкретной задачи, важно ПОНИМАТЬ как выполнена реализация, чтобы
знать возможные проблемы и методы их обхода.

Альтернативные подходы

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

Мой профиль

University of Waterloo (Canada) to host the next IOI

Waterloo's reputation is known worldwide. In 2005, Microsoft CEO Bill Gates visited our campus and returns in February 2008. "There are many years where Waterloo is the university we hired the most people from of any university of the world", he said.

The next Olympiad will be held entirely on the university campus and the contests will take place in the lecture halls of the Department of Mathematics and Informatics.
Students and guests will be accommodated at the university hostels located within 7 minute walk.

The choice of the University of Waterloo was not accidental: it is the place of academic studies for many of IOI medalists. Upon graduation, they are hired without hesitation by eager employers. The annual salary of a novice Internet expert with a good CV is 60,000 Canadian dollars.

Canada pays great attention to education

It has the highest expenditures on educations (in terms of percents of GDP) in the world. This is why Canada has become one of the leaders in education.
At international events Canadian children show some of the best results in Mathematics, natural sciences, and Informatics. This is indicative of the high quality of service delivery at Canadian schools. Canadian academic degrees, Diplomas and Certificates are highly appreciated by the business community around the world.

Tuition fees, however, are commensurate to those in Europe, USA, and Australia which makes Canadian education attractive to international students.

Мой профиль

IOI 2010 will be held in Waterloo, Ontario, Canada, August 14-21
IOI 2011 will be held in Thailand
IOI 2012 will be held in Milan, Italy
IOI 2013 will be held in Brisbane, Australia

Мой профиль

Есть первое описание. Автор - Малышев Егор.

Coci_2008-09\6_March\6 - "SLICICE" 92335

Мой профиль

Начался "Зимний Кубок 2009-2010"

Есть еще описание. Автор - Малышев Егор

AP-CE-BT-PSC-COCI-RU\09_COCI6 - "DOSTAVA" 92334

Мой профиль

Есть еще описание. Автор - Грицкевич Евгений

AP-CE-BT-PSC-COCI-RU\09_GG - "ноФйа" (92702)

Состояние в Зимнем Кубке на 7 декабря
1. Малышев Егор - 1 разбор 2. Грицкевич Евгений - 1

Мой профиль

Есть еще описание. Автор - Грицкевич Евгений

Россия-И. Командные\05_Rup4 - "Посадка в поезд "(77728)

Состояние в Зимнем Кубке на 7 декабря 1. Грицкевич Евгений - 2 разбора 2. Малышев Егор - 1

Мой профиль

Есть еще описание. Автор - Грицкевич Евгений

Россия-И. Командные\06_Rup9 - "Шоколадки"

Состояние в Зимнем Кубке на 9 декабря 1. Грицкевич Евгений - 3 разбора 2. Малышев Егор - 1

Мой профиль

Есть еще описание. Автор - Малышев Егор

Россия-И. Командные\07_Rup5 - "Таблица" 60390(60390)

Состояние в Зимнем Кубке на 9 декабря 1. Грицкевич Евгений - 3 разбора 2. Малышев Егор - 2

Мой профиль

Есть еще описание. Автор - Грицкевич Евгений

Россия-И. Командные\08_Rup11 - "Пересекающий отрезок"

Состояние в Зимнем Кубке на 9 декабря 1. Грицкевич Евгений - 4 разбора 2. Малышев Егор - 2

Мой профиль

Есть еще описание. Автор - Малышев Егор

Россия-И. Личные\08_Rui1 - "Слияние " 77217

Состояние в Зимнем Кубке на 10 декабря 9.23 1. Грицкевич Евгений - 4 разбора 2. Малышев Егор - 3

Мой профиль

Есть еще описание. Автор - Грицкевич Евгений

Россия. Сборы\04_Rus\04_Rus - "Художник"

Состояние в Зимнем Кубке на 9 декабря 9.27 1. Грицкевич Евгений - 5 разборов 2. Малышев Егор - 3