10С–Игра в зачеркивание [Меньшиков]

[Тренировка 10]                      [Список тренировок]

Крайне любопытная задача.
Расскажу как мне далось ее решение. Рассказ будет не очень коротким, поэтому наберитесь терпения.

Итак мое первое решение было довольно тривиальным. Основывалось оно на опыте предыдущих задач. Суть заключалось в следующем:

1) Каждое состояние кодировалось числом. (X – единичка, O - нолик). В итоге получается 40 битное число, поэтому оно хранилось в типе long long.
2) Строилась матрица смежности, т.е. матрица переходов. Для каждого числа хранился список чисел, в которые можно попасть из текущего состояния.
3) Также отдельно хранился список всех возможных состояний(чисел) в игре.
4) После чего сортируем массив из п. 3) в порядке возрастания и начинаем его заполнять с конца.
5) Ответ будет находится в первом элементе массива из п. 3)

Чтож – неплохой план! Кодируем. Получаем нечто похожее на это. Каков же вердикт? На 9-и тестах из 31 получаем TLE.

И только после этого я начал ДУМАТЬ!

Самое время. Хорошо, что все вышеописанное было не на контесте.
Какие мной были сделаны ошибки?

1) Не оценил время работы на максимальном тесте! Даже не запускал такой тест.
2) Совсем не думал. Делал по накатанной. Как показывает практика “Не думать – это слишком большая роскошь!”.

Итак. После всего вышеописанного плавно переходим ко второй части рассказа, а именно ко второму решению.

Задача стояла убыстрить работу первого решения. Решение пришло почти сразу.
Рассмотрим случай N=6, K=2 и пустую полоску(OOOOOO). Посмотрим в какие состояния можно перейти:
1. XXOOOO ~ OOOO  (4)
2. OXXOOO ~ OOO   (3)
3. OOXXOO ~ OO,OO (2,2)
4. OOOXXO ~ OOO   (3)
5. OOOOXX ~ OOOO  (4)

Как наверное все уже успели заметить состояния 4 и 5 можно не рассматривать, т.к. они являются дубликатами состояний 1 и 2.
Итак, состояние описывается набором неуникальных чисел, значение которых не может быть меньше K. Хранить этот набор можно в контейнере vector<int>. Возникает логичный вопрос:”Как определить что два состояния равны?”. Ведь одно и тоже состояния можно получить несколькими путями. В таком случае договоримся, что все полученные состояния должны храниться в отсортированном виде.
Учитывая все вышесказанное можно запустить рекурсию с запоминанием. И хранить ранее полученные состояние в контейнере map<vector<int>, int>. Приведу пример реализации этой рекурсивной функции:

1. const int WIN = 1;
2. const int FAIL = 2;
3. const int NAN = 0;
4. typedef vector<int> SC; // state container
5. .......
6. int FindWinner(SC &state)
7. {
8.   if (state.empty()) return FAIL;
9.  
10.   MEM::iterator memIt = mem.find(state);
11.   if ( memIt != mem.end())
12.     return memIt->second;
13.  
14.   int res = NAN;
15.   for (SC::iterator it = state.begin(); it != state.end(); it++)
16.   {
17.     SC baseNextState = state; // новое состояние без элемента *it
18.     int value = *it;
19.     baseNextState.erase(find(baseNextState.begin(), baseNextState.end(),value));
20.     // элемент *it разбираем на все возможные состояния
21.     for (int i = 0; i <= value - k;i++)
22.     {
23.       SC nextState = baseNextState;
24.       if (i >= k)
25.         nextState.push_back(i);
26.       if (value - k - i >= k)
27.         nextState.push_back(value - k - i);
28.       sort(nextState.begin(), nextState.end());
29.       res |= FindWinner(nextState);
30.       if (res & FAIL)
31.         break;
32.     }
33.     if (res & FAIL)
34.       break;  
35.   }
37.   if (res & FAIL)
38.     res = WIN;
39.   else if (res & WIN)
40.     res = FAIL;
42.   mem[state] = res;
43.   return res;
44. }

* This source code was highlighted with Source Code Highlighter.

Обратите пристальное внимание на строчки 30-31 и 33-34. Благодаря им происходит очень неслабое отсечения перебора. Разберем их смысл. Как известно, позиция считается выигрышной, если из нее можно попасть хотя бы в одну проигрышную. Поэтому, при нахождении первой проигрышной позиции, в которую можно попасть из текущей делаем однозначный вывод, что текущая вершина является выигрышной.
Я понимаю, что кому-то сейчас захотелось увидеть реальные цифры, доказывающие правоту этих слов. Для этого рассмотрим наихудший тест:
40 1
OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO

С отсечением перебора получаем в структуре map 15405 элементов и время работы 0,105 сек. Без отсечения 44582 элементов и TLE на 6 тесте.
Автор в книге предлагает еще одну оптимизацию: отдельно рассмотреть случай, когда K = 1. Отличное дополнение к существующему решению. Но я его поленился сделать. И так, все выглядит довольно неплохо.

Вот полный исходник второго решения.

Ну чтож, это решение оказалось намного лучше первого. Мы получили законный Accepted. Но когда я говорил, что все довольно неплохо – я бессовестно врал. Всему виной лишние телодвижения в строчке 28, связанные с сортировкой массива. Как быть? На помощь нам придет контейнер multiset<int>. Я думаю теперь снят вопрос по поводу странной 4-ой строчки.

Третье решение мало чем отличается от второго с одним существенным отличием, что убран раздражающий фактор, связанный с сортировкой массива 15405 раз на худшем тесте. Отправляем – получаем AC.

Вот полный исходник третьего решения.

Но что это? Время работы на максимальном тесте 0,322. В 3 раза медленнее, чем на векторах? Подумаем почему!

1) добавление нового элемента в multiset происходит за O(logN), противовес O(1) у вектора, если не требуется перераспределение памяти.
2) Строчка:
for (SC::iterator it = state.begin(); it != state.end(); it++)
перебор всех элементов в контейнере для вектора будет происходить очень быстро (O(N)), т.к. следующий элемент находится сразу после текущего(не забываем, что вектор – это массив). Нельзя сказать тоже самое про multiset. Внутри оно представляет собой бинарное дерево поиска. Операция it++ будет сопровождаться несколькими перемещениями по узлам дерева, поэтому общая сложность выполнения перебора всех элементов будет дольше O(N).
3) Строчка:
MEM::iterator memIt = mem.find(state);
у меня вызывает опаску. Если для определения оператора меньше для multiset использовалась строка из п.2), то можно с уверенностью сказать, что операция find для multiset замедлится.

Итак что мы получили?  Код стал красивее, понятнее, компактнее, но медленее.

Четвертое решение разительно отличается от первых трех. Суть его заключается в том, что представленная игра является игрой класса НИМ. И наша задача решается с помощью функции Гранди. Теория по этому вопросу изложена у e-maxx’a.
Следующая реализация была полностью получена из описания раздела “Применение теоремы Шпрага-Гранди”.

Здесь представлен полный исходный код четвертого решения.