В статье говориться, что для оценки времени работы стоит считать, что в секунду выполняется 10^6 операций. На современнях компьютерах, по крайней мере по моему опыту олимпиадного программирования, это скорее 5*10^7-10^8 операций в секунду. Конкретное число зааисит от сложности операций. Например, целочисленное деление — это относительно долгая операция, а побитовый xor — быстрая.
Вообще как-то так, все пытаются предугадать куда побежит Нео и выстрелить с упреждением, а Нео может оценивать ситуацию и думать куда лучше побежать, чтобы не поймать пулю. И плюс через 15-20 секунд стояния на месте время возобновляется, чтобы нельзя было заморозить игру через AFK,
Время у всех движется одинаково. А игрок, от движения которого, зависит время, выбирается по-очереди или случайно. Или им становится тот, кто убил текущего игрока.
Если мы случайным образом перемешаем массив, то мы как раз сделаем перестановки равновероятными, а значит вероятность того, что алгоритм отработает за n^2, а не за n log n, становится крайне мала.
Но согласитесь, это же не решение, а грубый хак, который в нормальной программе недопустим
Не соглашусь. Так можно сказать, например, про любой эвристический алгоритм. И если алгоритм в 95% дает правильный ответ, а на практике вероятность того, что запрос пользователя попадет в эти 5% крайне мала, то алгоритм можно смело применять, как мне кажется.
Пример про quicksort некорректен, так как перемешать массив — это не грязный хак, а абсолютно нормальное доказанное решение. Worst case превращается в average case, а, как известно, быстрая сортировка в среднем работает за O(n log n).
Однако, вы правы, сделать такой контест, чтобы все решения участников, которые прошли тесты были правильными, не просто. В этом состоит большая доля работы жюри.
Для того, чтобы понять значение всех чисел в таблице, советую ознакомится с правилами. На мой взгляд они лучше всего объяснены в этом видео http://www.youtube.com/watch?v=jKHYE3CWloU. Оно снято для Чемпионата Урала, а не для ACM ICPC, но правила там такие же.
Во-первых, ИТМО побеждает далеко не в первый раз. В пятый, по-моему. Это абсолютный рекорд по количесту побед среди ВУЗов. Это с учетом того, что один человек по правилам может принять участие в финале максимум два раза.
Во-вторых, университет предоставляет только площадку. Задачи и тестирующая система делаются организацией ACM.
Вы никогда не участвовали в соревнованиях вида Russian AI Cup? По-моему, это довольно зрелищно. Особенно на большом экране, когда в зале сидят участники соревнований и яростно болеют за свою программу.
http://e-maxx.ru/algo
Сборник сделан Ивановым Максимом — выпускником мех-мата Саратовского ГУ, серебрянным призером чемпионата мира по программированию ACM-ICPC 2011.
> Balanced Search Trees (сбалансированные поисковые деревья, снова извиняюсь за прямой перевод, возможно правильно не поисковые, а бинарные деревья).
Насколько я знаю, в русском языке используется термин: «Сбалансированное дерево поиска». Так что перевод вполне правильный. Но не любое бинарное дерево — дерево поиска.
Бои с чемпионом: http://russianaicup.ru/profile/slash/contest4
Умножить два целых быстрее, чем взять корень в вещественных числах.
Не соглашусь. Так можно сказать, например, про любой эвристический алгоритм. И если алгоритм в 95% дает правильный ответ, а на практике вероятность того, что запрос пользователя попадет в эти 5% крайне мала, то алгоритм можно смело применять, как мне кажется.
Пример про quicksort некорректен, так как перемешать массив — это не грязный хак, а абсолютно нормальное доказанное решение. Worst case превращается в average case, а, как известно, быстрая сортировка в среднем работает за O(n log n).
Однако, вы правы, сделать такой контест, чтобы все решения участников, которые прошли тесты были правильными, не просто. В этом состоит большая доля работы жюри.
Во-вторых, университет предоставляет только площадку. Задачи и тестирующая система делаются организацией ACM.
Сборник сделан Ивановым Максимом — выпускником мех-мата Саратовского ГУ, серебрянным призером чемпионата мира по программированию ACM-ICPC 2011.
Насколько я знаю, в русском языке используется термин: «Сбалансированное дерево поиска». Так что перевод вполне правильный. Но не любое бинарное дерево — дерево поиска.