Логин: Пароль:

Спортивное программирование
в Красноярском крае


k_mihey
kormyshov


 


Перейти к профилю
Вернуться к ленте

Random на службе олимпиадника

Я не буду рассказывать здесь о том что быстрая сортировка имеет худший случай и надо применять random. Также не буду рассказывать про декартово дерево по случайному ключу. А хочется рассказать о некоторых задачах, в решении которых применение случайных чисел упрощает его.

Впервые применение случайных чисел именно в таком контесте увидел после студенческого полуфинала 2008 года. В том году впервые была интерактивная задача (В).

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

Когда приехали домой и начали разбирать решения жюри, то решение Петра Митричева заставило раскрыть рот:

#include <cstdlib>
#include <cstdio>

using namespace std;

int main() {
  srand(43154731);
  char ans[10];
  char* moves[] = {"NORTH", "SOUTH", "EAST", "WEST"};
  for (int i = 0; i < 100000; ++i) {
    printf("%s\n", moves[rand() & 3]);
    fflush(stdout);
    gets(ans);
  }
  printf("DONE\n");
}

То есть делается 100000 шагов в произвольном направлении. Все гениальное просто.

Второй раз такой подход услышал опять же в Барнауле на разборе задач с финала ВКОШП 2010. Задача А про арифметическую прогрессию. Там достаточно много членов было во входном файле, поэтому случайным выбором пары из них и нахождения всех членов прогрессии можно было быстро получить ответ. Опять же я придумал не рандомизированный алгоритм, который работал дольше, но все равно укладывался.

Теперь мой опыт применения случайных чисел. Он касается задач с сайта acmp.

Для задачи Туристическое агентство, в которой необходимо было найти точки сочленения в графе, а потом еще и посчитать количество путей, проходящих через них. Правильное решение заключалось в модификации энциклопедичного алгоритма поиска точек сочленения, но думать было лень. Мое итоговое решение было следующим: нашел точки сочленения, затем для каждой из них (с вероятностью 10%) запустил dfs и посчитал ответ. А затем уже для всех остальных опять dfs\'ом считал ответ, используя уже найденые значения. Таким образом предподсчет некоторых значений позволил избежать мое программа TLE.

И сегодняшняя задача, которая и побудила написать этот пост. Задача Кубик. Там необходимо перебрать все варианты поворота шестигранного кубика. Применим способ Петра. Я написал три процедуру, которые вращают его на 90 градусов вокруг одной из осей. А потом запустил несколько произвольных вращений.

Пользуйтесь рандомом, но в меру :-)

2011-09-22


2011-09-22 demidenko
там на асмп есть ещё одна классная задача, которую можно классно рандомом сдать (я, если что, не так сдавал).

2011-09-22 kormyshov
а я ее уже сдал?

2011-09-23 demidenko
ещё нет

2013-06-04 kormyshov
Ещё и на Тимусе нашёл (задача 1219)

Система Orphus

(c) Copyright 2011-2014 Михаил Кормышов

kormyshov[dog]gmail.com