Хотелось бы узнать, может кто принимал участие в олимпиадах АСМ, встречался с задачами с этих контестов. Пишите, делитесь опытом.

Цитата(MastEdm @ 3.1.2006, 19:44)

может кто принимал участие в олимпиадах АСМ

Ну я принимал (вместе с Ирокезом и Симаняеем).

Цитата(MastEdm @ 3.1.2006, 19:44)

встречался с задачами с этих контестов

Было дело.

Цитата(MastEdm @ 3.1.2006, 19:44)

Пишите, делитесь опытом.

Был бы опыт положительный, поделился бы

Что интересует-то? Принимал уже участие? Или только собираешься?

Я тоже принимал участие. Есть даже сайт на Тимусе посвященный АСМ.
Про задачи- нелегкие

MastEdm
Если ты об этом говоришь -- то да, учатствовал я в 2004 году в региональном туре чемпионата мира

Не очень мне это дело понравилось.
Задачи каждый год там довольно похожие, так что для команд, натренировавшихся на решении подобных заданий, весь процесс становится чисто механическим. Как ещё можно объяснить, что ИТМОвская команда решила первую задачу на 20-й минуте (примерно), а вторую уже на 30-й? Там только набирать исходник столько времени понадобится...

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

Я принимал участие в 4-финальных играх московского подрегиона. Довольно интересное мероприятие, я бы сказал. Моя команда решила 2 задачи - много это или мало, кому как - но судя по тому, что от нашего вуза раньше вообще не одной задачи не решали, то ничего. Опять же без специальной подготовки. На радостях решили готовиться к следующим соревнованиям. Дело это, на мой взгляд, довольно увлекательное.

По поводу http://acm.timus.ru/ - можно на нём тренироваться, но там, кажется, слишком простые задачи по сравнению с АСМ
Интереснее всего http://online-judge.uva.es/problemset/ - реальные задачки!

Цитата(MastEdm @ 4.1.2006, 13:19 )

Дело это, на мой взгляд, довольно увлекательное.

Кому что...

Это сравнимо со спортом. В некотором роде даже с азартными играми: ведь я прекрасно понимаю, что первые мест 15-20 займут команды из МГУ, но всё же есть азарт потягаться с другими ВУЗами столицы - мы то же что-то можем!

А есть ли у кого опыт успешного выступления на подобных олимпиадах - хоть что-то решалось ведь...

Дрон
ППКС

Ну так что, уважаемые братья-программисты? Неужели никому нечего сказать по поводу АСМ? Можно даже неудачный опыт участия - на ошибках учатся.

MastEdm
А, простите, с какой целью интересуетесь?

Эх... Рассказать как всё было, так там скорее не об олимпиаде получится, а так, о жизни

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

В итоге я пытался её решить 4 раза. Но не успешно
В основном валился по времени: первый раз на 16-м тесте, потом на 21, потом на 24. (ну и ещё разок завалилась с wrong result -- это я малёк ступил ). Интересно, сколько у них всего тестов?
В чём была проблема -- я не сомневаюсь: у меня там был далеко не самый эффективный алгоритм сортировки: я распихивал элементы в дерево, а потом обходил его -- недостатки очевидны. Хотя всё остальное было действительно идеально
Но, блин, что же я должен быструю сортировку Хоара наизусть выучить?

В общем вот. Остальные задачи как-то не запомнились -- задачи как задачи... про всякую чепуху.

После окончания я посмотрел на результаты остальных команд -- из них никто эту последнюю задачу даже решать не пробовал...

Это сообщение отредактировал(а) Дрон - 5.1.2006, 20:15

Цитата

А, простите, с какой целью интересуетесь? smile

Просто весной будет проводится олимпиада по схеме АСМ, но на русском языке. Хотелось бы достойно выступить, тобеж хоть что-то решить.

Понятно, что владение основными алгоритмами обработки данных, хоть и огромный плюс, но проблема может быть в банальной отладке. К примеру, решали мы как-то задачку с http://online-judge.uva.es/problemset/. Вроде бы решили, вроде всё работает, во время укладывается, но сдать не можем - неправильный ответ. А проблема была в обработке математических функций. Понять это можно на простом примере: как измерить толщину листа бумаги? Возьмём 100 листов, поставим на них человека, измерим высоту. Затем вытащим один лист и вновь измерим высоту. Разница и даст нам толщину листа бумаги. Этот пример меня уже достал (уже ни один препод преводил мне его!), но факт остаётся фактом.


Вот хотелось бы узнать побольше таких тонкостей...

Дрон

А саму задачку не вспомнишь?

Это сообщение отредактировал(а) MastEdm - 5.1.2006, 23:02

Цитата(Дрон @ 5.1.2006, 22:13 )

Но, блин, что же я должен быструю сортировку Хоара наизусть выучить?

Пардон, а на чем писали-то? Если на C++, то std::sort еще никто не отменял
Правда, есть у меня подозрение (слегка подтвержденное собственным опытом), что C++ код на соревнованиях любят компилировать с не самыми агрессивными настройками оптимизации, что приводит к тормозам при использовании STL. А жаль, ведь цель, по идее, - не протестировать знание основных алгоритмов, а выявить способности к созданию собственных и оптимальной их реализации.

Цитата(Дрон)

Задачи каждый год там довольно похожие

А что ты собственно хотел? Алгоритмов ведь не так много, как кажется. Придумать задачу — дело тонкое, а в подобных олимпиадах надо еще так придумать, чтобы она решалась за разумное время и при том был бы тест, который при неэффективном решении не пропускал бы дальше. Разнообразие сложно физически.

Цитата

...что же я должен быструю сортировку Хоара наизусть выучить?

Не, можно на листочке заранее написать...
Добавлено @ 23:16

Цитата(Void)

..что C++ код на соревнованиях любят компилировать с не самыми агрессивными настройками оптимизации, что приводит к тормозам при использовании STL.

В тему: мы задачку там долго не могли скинуть. Скинули, когда cin заменили на scanf...

Это на 4-финальных можно со своей литературой, а вот дальше - извини...

Дрон
А по поводу сортировки, то почему бы не воспользоваться цифровой или сортировкой Шелла? Они не такие уж сложные...

Цитата(MastEdm @ 6.1.2006, 01:20 )

А по поводу сортировки, то почему бы не воспользоваться цифровой или сортировкой Шелла? Они не такие уж сложные...

Да quicksort тоже совершенно не сложная. А у Шелла все-таки быстродействие меньше.

Цитата(Pete @ 6.1.2006, 01:16 )

Придумать задачу — дело тонкое, а в подобных олимпиадах надо еще так придумать, чтобы она решалась за разумное время и при том был бы тест, который при неэффективном решении не пропускал бы дальше.

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

Цитата(MastEdm @ 5.1.2006, 22:39 )

А саму задачку не вспомнишь? smile

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

Цитата(Void @ 5.1.2006, 23:08 )

Пардон, а на чем писали-то? Если на C++, то std::sort еще никто не отменял smile

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

Цитата(Pete @ 5.1.2006, 23:16 )

Не, можно на листочке заранее написать...

Цитата(Void @ 5.1.2006, 23:30 )

Да quicksort тоже совершенно не сложная.

Не спорю, но так я ж её всё равно не помню
Если она мне по работе понадобится (в чём сомневаюсь ), то открою гугль и быстро всё найду.

Цитата(Дрон @ 6.1.2006, 12:33 )

Не спорю, но так я ж её всё равно не помню smile

Я ее тоже не мог запомнить, пока не увидел реализацию на OCaml Пять строк (по сути, сам принцип алгоритма) запомнить несложно, а развернуть в императивный код труда не составит.

Кстати, если кому интересно, у меня есть тексты задач регионального турнира ACM, проводившегося у нас этой осенью. Перепечатывал вручную, поэтому рисунков там нет. (Тем проще будет решить некоторые задачи ;) )
Куда бы их выложить?

Вот тексты задач с 2003 года: http://ankor.newmail.ru/problems.zip (~110 Kб)

А вот последняя задача (о которой я говорил) с 2004 года:
http://ankor.newmail.ru/ProblemK.zip (~5 Кб)

Только, прежде чем её читать, прочитайте последнюю задачу 2003 года. Там просто некоторый юмор присутствует

Это сообщение отредактировал(а) Дрон - 7.1.2006, 22:49