Комментарии 45
В мое время на школьных олимпиадах (начало 90-х) все было куда проще. Ни ограничений (кроме системных), ни тестов, входные и выходные данные в общих чертах описывались, просто ручками проверяли (лишь бы не падала) и код читали.
А я помню ещё некоторые олимпиады, где код ручками писали без компьютера.
А он хоть исполнялся? :)
Ой, не спрашивайте меня. Его так же проверяли, читая, потом перебивали в ГИВИ-Бейсик и проверяли на «компилябельность». Ну и оттуда со всеми вытекающими результатами, кому последнее место, кому предпоследнее и так далее.
Трудные времена были… смута :)
Трудные времена были… смута :)
В мою бытность в старших классах c БК-0010… Насчет исполнения кода школьников на бейсике из домашнего задания в тетрадке на настоящем компьютере в 98% случаях вопрос даже не стоял — препод просто впол-оборота проглядывал тетрадные листы «исходников» и зачеркивал косяк
(по-современному — throw Exception красной ручкой).
Нет, он был не злой человек, он делал и «свободные уроки», когда можно было делать с компом что угодно, хочешь играй, хочешь бейсик мучай. Но педагогическая методика необычная.
(по-современному — throw Exception красной ручкой).
Нет, он был не злой человек, он делал и «свободные уроки», когда можно было делать с компом что угодно, хочешь играй, хочешь бейсик мучай. Но педагогическая методика необычная.
Исполнял в уме? :)
Да там ума много и не надо было… Я за препода проверял. Компы примитивные, бейсик тоже примитивный, я на Роботроне учился задолго до этого по методике «думай как компьютер шаг за шагом строка за строкой исполняй команды в уме».
Тогда не было понтов TPL, кучи процессоров, ядер, винды даже не было. Все было просто.
Тогда не было понтов TPL, кучи процессоров, ядер, винды даже не было. Все было просто.
В некоторых регионах России школьный и муниципальный этап Всероссийской олимпиады по информатике до сих пор ручками (тур состоит чисто из теоретических задач, или 50/50) пишут. Ужас, если честно. Я занимаюсь программированием дистанционно с некоторыми школьниками из Астраханской и Архангельской области. Они мне рассказывают, как проходят у них первые два этапа олимпиады. Жаль, что в некоторых регионах так относятся к программированию…
Если у задачи нет решения на одном из языков программирования — это плохая олимпиадная задача. Обычную олимипиадную задачу можно решить на любом языке из данного набора и уложиться в ограничения. Это работа авторов.
Это меня и расстраивает, что нет поправки на язык, далеко не всегда на python можно соревноваться с C в плане скорости выполнения, а на codeforce от этого зависит итоговый бал да и вообще выполнение задачи.
С такими поправками не все просто. Появляется много вопросов.
Какой именно коэффициент между решением на Python и C++? 5 раз? 20 раз? Дело в том, что это совсем не константа и каким бы его не поставили, одна из сторон окажется в преимущественном (возможно, значительно) положении. Как результат, цель достигнута не будет.
Наличие таких поправок фактически значительно увеличит ограничения по времени во многих задачах, что приведет к увеличению времени тестирования. При большом количестве участников некоторые интересные задачи авторам придется откладывать из-за того, что они будут очень долго тестироваться. Короче, класс используемых задач уменьшится.
Я легко могу представить в реальной практике требование вида «Ваш компонент должен обрабатывать миллион запросов не более чем за секунду», но поправка к нему вида «Ну ладно, если пишите на Python, то достаточно уложиться в 10 секунд» выглядит смешной.
Отсутствие поправок обосновывается, что для каждой задачи в программировании важно подбирать правильный инструмент. Глупо реализовывать на языке с динамической типизацией высокоэффективный алгоритм с жесткими требованиями на производительность. Ну не подходят эти языки для таких задач. С другой стороны часто бывают задачи без жестких требований ко времени работы. Самые короткие и элегантные решения часто получаются на Python и Ruby.
Здесь работает принцип, что выбирая инструмент, ты выбираешь его плюсы и минусы. Например, уровень поддержки сред языка Java значительно выше, чем языка C++. Статический анализ в Java встроенный в IDE позволит избежать некоторых ошибок, а так как код управляемый — любой выход за границу массива породит исключение и вы быстрее найдете ошибку. С другой стороны да, решения на Java обычно работают чуток медленнее.
На Codeforces обычно ограничения по времени очень лояльны — неасимптотические оптимизации редко нужны, без проблем проходят эффективные решения на С/C++, С#, Java и других языках со схожей производительностью.
Какой именно коэффициент между решением на Python и C++? 5 раз? 20 раз? Дело в том, что это совсем не константа и каким бы его не поставили, одна из сторон окажется в преимущественном (возможно, значительно) положении. Как результат, цель достигнута не будет.
Наличие таких поправок фактически значительно увеличит ограничения по времени во многих задачах, что приведет к увеличению времени тестирования. При большом количестве участников некоторые интересные задачи авторам придется откладывать из-за того, что они будут очень долго тестироваться. Короче, класс используемых задач уменьшится.
Я легко могу представить в реальной практике требование вида «Ваш компонент должен обрабатывать миллион запросов не более чем за секунду», но поправка к нему вида «Ну ладно, если пишите на Python, то достаточно уложиться в 10 секунд» выглядит смешной.
Отсутствие поправок обосновывается, что для каждой задачи в программировании важно подбирать правильный инструмент. Глупо реализовывать на языке с динамической типизацией высокоэффективный алгоритм с жесткими требованиями на производительность. Ну не подходят эти языки для таких задач. С другой стороны часто бывают задачи без жестких требований ко времени работы. Самые короткие и элегантные решения часто получаются на Python и Ruby.
Здесь работает принцип, что выбирая инструмент, ты выбираешь его плюсы и минусы. Например, уровень поддержки сред языка Java значительно выше, чем языка C++. Статический анализ в Java встроенный в IDE позволит избежать некоторых ошибок, а так как код управляемый — любой выход за границу массива породит исключение и вы быстрее найдете ошибку. С другой стороны да, решения на Java обычно работают чуток медленнее.
На Codeforces обычно ограничения по времени очень лояльны — неасимптотические оптимизации редко нужны, без проблем проходят эффективные решения на С/C++, С#, Java и других языках со схожей производительностью.
Да это все верно, но все же если в конкурсе предполагается возможность участия на многих языках то хорошо бы иметь возможность пройти задания на каждом из них.
Пример:
Вчера я решал задачу в одном из ваших соревнований на python, алгоритм проходил тесты хорошо, но когда количество элементов массива выросло со 100 до 15000 и операций по ним с тех же 100 до 4000 моя программа ни как не могла уложиться в 2 сек, а считала около 20 — 30 сек хотя алгоритм работы был правильным, и различные оптимизации приводили лишь к небольшим изменениями времени работы и потребления памяти. Такую пропасть мне преодолеть не удалось. Я не C/C++ разработчик, но мне тоже интересны конкурсы подобные вашим, хорошая разминка для мозгов, но в таких условиях не вижу смысла в них принимать участие.
Пример:
Вчера я решал задачу в одном из ваших соревнований на python, алгоритм проходил тесты хорошо, но когда количество элементов массива выросло со 100 до 15000 и операций по ним с тех же 100 до 4000 моя программа ни как не могла уложиться в 2 сек, а считала около 20 — 30 сек хотя алгоритм работы был правильным, и различные оптимизации приводили лишь к небольшим изменениями времени работы и потребления памяти. Такую пропасть мне преодолеть не удалось. Я не C/C++ разработчик, но мне тоже интересны конкурсы подобные вашим, хорошая разминка для мозгов, но в таких условиях не вижу смысла в них принимать участие.
Мне понравилось как сделали результаты тестирования в одном из курсов coursera. Там после прогона по всем тестам отдельно идет замер потребления памяти и времени выполнения при различном количестве входных параметров. Несколько прогонов с разным количеством и последующая интерполяция дают приблизительную оценку вашему алгоритму например O(N) или O(log N) и тд.
Хорошо бы и в спортивном программировании оценивать не абсолютные показатели время/память а «относительные» через сложность алгоритма. Это немного сгладит разницу между ЯП
Хорошо бы и в спортивном программировании оценивать не абсолютные показатели время/память а «относительные» через сложность алгоритма. Это немного сгладит разницу между ЯП
да было бы неплохо )
Ну например в курсе по алгоритмам на той-же коурсере, для все заданий требуется уложиться в некоторое время выполнение. И в размер памяти. Таким образом проверяется правильность алгоритма.
То есть, если я распределю массив на максимальные возможные ограничения, то оценка будет O(1)?
Не совсем понял что вы собираетесь делать с массивом.
Не бывает О(1) есть O( C ) — если время работы не зависит от количества входных параметров. (соответственно и для памяти).
Не бывает О(1) есть O( C ) — если время работы не зависит от количества входных параметров. (соответственно и для памяти).
Если вы посмотрите на определение «О большого», то поймете, что О( С ) и О(1) по смыслу одно и то же. Запись О(С) при этом избыточна, а О(1) намного более широкоупотребима.
Я практически уверен, что если требование в 2 секунды, а программа работает 20-30с, то алгоритм не правильный. В смысле, он правильно считает и проходит все функциональный тесты, но не оптимальный (не проходит тесты на производительность). Скорее всего у тебя там O(N*N) ассимптотика, а не O(N) или O(N*LogN).От языка программирования на данных в пределах описанных выше не может быть разница в 10-15 раз.
Быть может Вы и правы, буду пробовать дооптимизировать алгоритм уже вне codeforce, правда с данными я чуть чуть ошибся, сейчас пересмотрел 15000 эелементов массива 30000 операций 4000 запросов которые могут применить от 1 до 30000 операций над массивом, каждая операций может увеличить на n от 1 до 15000 элементов массива
В данном случае вы можете просто опубликовать ссылку на свое решение, а мы все вместе на него посмотрим и поймем в чем дело. Но повторюсь, эквивалентная реализация на Python вполне может отставать от С++ в 5-20 раз.
вот мое решение pastebin.com/FNByrpPU
Дайте ссылку вида codeforces.ru/contest/71/submission/3516879 (нажмите в решеточку на попапе с исходником) А сейчас еще надо догадаться, что за задача, и на каком тесте возникают проблемы.
Я могу ошибаться, задачу я не решал. Но твое решение в лоб применяет запросы и для каждого запроса выполняет все отдельные операции над каждым елементом оригинального массива. Очевидно ассимптотика O(K*M*N).
Так как задача олимпиадная, надо сделать что-нибудь другое :) Например просчитать массив сумм операций (Msum[0:m][0:n]. То есть для применения операций с m[i]->m[k] (как раз один запрос) надо прибавить к оригинальному массиву елементы массива Msum[k] и вычесть елементы массива Msum[i-1].
Получается что-то типа O(M*N+2*K*N)
C индексами и ассимтотикой я мог напутать, но что-то в этом виде наверно требовалось.
Так как задача олимпиадная, надо сделать что-нибудь другое :) Например просчитать массив сумм операций (Msum[0:m][0:n]. То есть для применения операций с m[i]->m[k] (как раз один запрос) надо прибавить к оригинальному массиву елементы массива Msum[k] и вычесть елементы массива Msum[i-1].
Получается что-то типа O(M*N+2*K*N)
C индексами и ассимтотикой я мог напутать, но что-то в этом виде наверно требовалось.
Даже если перепишите на C++ — все-равно решение не пройдет временные ограничения.
Составители задач не могут решать её на 20 языках. А лучше большой выбор языков, чем 100% гарантия наличия решения. Есть вроде стандартный набор языков, на которых проверяют решаемость — паскаль (самый популярный), c++ (классика), java (jvm иногда может выдать сюрпризы в плане производительности — как приятные, так и не очень) и python (очень тормозной)
ну. пример задачи решается вроде-бы просто
раскрасить вершины графа тремя цветами синий, красный и нейтральный, чтобы нейтрального было поменьше, а синий и красный не встречались на одном ребре
вырожденное решение (все вершины одного цвета) запрещено
значит берем один лист (или как там называется вершина с одним ребром из нее) дерева, красим в синий цвет
ее партнера оставляем «нейтральным»
все остальное дерево делаем красным. итак, а+b=n-1, а количество перекрестков в городе без ресторана (нейтральный цвет) равно одному
так как в дереве любая «нелистовая» вершина делит граф на две половинки, то решением будет количество нелистовых вершин
ну найти такие «внутренние вершины» в заданном графе
раскрасить вершины графа тремя цветами синий, красный и нейтральный, чтобы нейтрального было поменьше, а синий и красный не встречались на одном ребре
вырожденное решение (все вершины одного цвета) запрещено
значит берем один лист (или как там называется вершина с одним ребром из нее) дерева, красим в синий цвет
ее партнера оставляем «нейтральным»
все остальное дерево делаем красным. итак, а+b=n-1, а количество перекрестков в городе без ресторана (нейтральный цвет) равно одному
так как в дереве любая «нелистовая» вершина делит граф на две половинки, то решением будет количество нелистовых вершин
ну найти такие «внутренние вершины» в заданном графе
простите, все оказалось сложнее (выдергивание одной вершины делит дерево на несколько частей по кратности этой вершины — это не меняет ничего, но может усложнить), да и самая суть олимпиадной задачи — эффективно посчитать за 4 секунды.
Да, конечно. Наличие внутренних вершин степени более 2 делает задачу значительно содержательнее. Полагаю, без динамического программирования здесь не обойтись.
Для каждой внутренней вершины степени (или кратности? — я не помню теорию графов) N надо быстро посчитать {X1, X2… Xn} — количества вершин в графах, которые получатся после ее удаления. Потом cкомбинировать все возможные варианты Xi в две суммы — неоправданный геморрой.
Например, у нас в городе 5000 перекрестков. Один должен остаться без ресторана. В самом предельном случае решением будет
{1, 4998}; {2, 4997};… {4998,1} — это в том редком случае, когда город расположен вдоль Пан-Американского шоссе. С другой стороны, если город представляет из себя 4999-конечную снежинку — то ответ тоже такой же.
Например, у нас в городе 5000 перекрестков. Один должен остаться без ресторана. В самом предельном случае решением будет
{1, 4998}; {2, 4997};… {4998,1} — это в том редком случае, когда город расположен вдоль Пан-Американского шоссе. С другой стороны, если город представляет из себя 4999-конечную снежинку — то ответ тоже такой же.
Ссылка на ACM-соревнования никуда не ведёт.
Ага, а потом засудят за что-нибудь. Мы помним все, адоб.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий
Олимпиадные задачи по программированию: что за зверь?