Interviewstreet- Перестановочная игра
Алиса и Боб играют в следующую игру:
1) Для начала они выбирают перестановку первых N чисел.
2) Они играют попеременно, а Алиса играет первой.
3) В свою очередь, они могут удалить любое оставшееся число из перестановки.
4) Игра заканчивается, когда оставшиеся числа образуют возрастающую последовательность. Человек, сыгравший последний ход (после которого последовательность увеличивается) выигрывает игру.
Предполагая, что оба играют оптимально, кто победит в игре?
Входные данные: Первая строка содержит количество тестовых случаев T. T тестовых примеров следуют. Каждый случай содержит целое число N в первой строке, за которым следует перестановка целых чисел 1..N во второй строке.
Вывод: Выведите T строк, по одной на каждый тестовый случай, содержащих "Алису", если Алиса выиграет игру, и "Боб" в противном случае.
Пример ввода:
2
3
1 3 2
5
5 3 2 1 4
Пример вывода:
Алиса
боб
Ограничения:
1 <= T <= 100
2 <= N <= 15
Первоначально перестановка не будет возрастающей последовательностью.
Я пытаюсь решить вышеуказанную проблему. Я дошел до сих пор, но я застрял в точке. Пожалуйста, помогите мне продолжить.
В вышеуказанной задаче для перестановки длины 2 игрок 1 всегда выигрывает.
Для перестановки длины 3 игрок 2 выигрывает, если строка строго увеличивается или уменьшается.
Для перестановки длины 4, если игрок 1 может сделать строку, строго увеличивая или уменьшая, удаляя персонажа, он выигрывает, в то время как игрок 2 выигрывает.
Отсюда вывод:
Если текущий игрок может сделать строку строго увеличивающейся, он / она выигрывает. (Банальный случай)
Если он / она может сделать это строго уменьшая, победитель определяется количеством элементов в этой последовательности. Если в этой последовательности четное количество элементов, текущий игрок проигрывает, иначе выигрывает.
Но что делать, если результирующая строка не увеличивается и не уменьшается?
8 ответов
Это типичная игровая проблема. У вас есть 2^15 возможных позиций, которые обозначают оставшиеся цифры. Из числа оставшихся чисел вы можете узнать, чья это очередь. Итак, теперь у вас есть график, который определяется следующим образом - вершины - это возможные множества оставшихся чисел, и есть ребро, соединяющее две вершины u и v, если есть ход, который изменяет набор u на набор v (то есть набор v имеет ровно на одно число меньше).
Теперь вы уже указали, для каких позиций вы сразу знаете, кто является победителем - те, которые представляют растущие последовательности чисел, которые эти позиции помечены как проигрышные. Для всех остальных позиций вы определяете, выигрывают они или проигрывают следующим образом: позиция выигрывает, если есть край, соединяющий ее с проигрышной позицией. Таким образом, все, что осталось - это что-то вроде dfs с напоминанием, и вы можете определить, какие позиции выигрывают, а какие проигрывают. Поскольку граф относительно мал (2^15 вершин), это решение должно быть достаточно быстрым.
Надеюсь это поможет.
Конечно, это можно сделать с помощью "грубой силы" для малых N, но разве вы не подозреваете более легкий ответ относительно инверсий и знака перестановки?
Первоначально я подозревал ответ типа "Алиса выигрывает, если знак -1, иначе проигрывает", но это не так.
Но я хотел бы предложить представление о проблеме, которую может использовать не только ваш алгоритм, но и тот, который в равной степени повысит производительность вашей бумаги и ручки в этой игре.
Инверсия - это пара индексов ii,j) ребро неориентированного графа с вершинами 1,...,N. Каждый игрок удаляет вершину из этого графа и выигрывает, если не осталось ребер.
За 5 3 2 1 4результирующий график
5--3
/|\ |
/ | \|
4 1--2
и Алиса быстро видит, что удаление "5" дает Бобу возможность удалить 2. Тогда не остается инверсий, и Боб выигрывает.
Эту игру можно решить рекурсивно.
Каждый раз, когда Алиса берет свой первый выбор и выбирает i, вычтите 1 из всех оставшихся чисел, которые больше, чем i. Теперь у нас та же игра, но с цифрами от 1 до N-1
скажем, ваша последовательность
1,3,5,4,2
На своем первом шаге Алиса может выбрать любое число. case1: она выбирает 1, Алиса может выиграть, если Боб не может выиграть с 3,5,4,2 (эквивалентно 2,4,3,1)
case2: сначала она выбирает 3 Алиса может выиграть, если Боб не может выиграть с 1,5,4,2 (эквивалентно 1,4,3,2)
case3: сначала она выбирает 5 Алиса может выиграть, если Боб не может выиграть с 1,3,4,2
Вы поняли идею.
Таким образом, вы можете создать рекурсивную функцию для выработки решения для перестановки размера N, используя перестановки размера N-1 для каждого возможного первого предположения. базовый случай для рекурсии - когда у вас есть последовательность в порядке.
На каждом этапе рекурсии человек пробует все возможности и выбирает все, что заставляет их победить.
Поскольку существует много комбинаций ходов, которые могут перейти к одной и той же последовательности, рекурсия имеет перекрывающиеся подзадачи. Это означает, что мы можем использовать динамическое программирование или просто "запоминать" нашу функцию, что значительно повышает эффективность.
Для дальнейшего ускорения можно использовать симметрию в перестановках, так как многие группы перестановок эквивалентны, например, обратная перестановка приведет к тому же результату.
Удачи.
@tiwo,@rup COnsidering 5 3 2 1 4 - последовательность, в которой сначала Алиса удаляет 5, а Боб удаляет 2, затем последовательность 3 1 4, что не в порядке возрастания, тогда Алиса получает шанс удалить 1, и последовательность находится в В порядке возрастания Алиса должна быть ответом. На графике, который вы дали, должно быть ребро между 3 и 1, так как 1 и 3 в инверсии.
Пожалуйста, скажите мне, где я ошибаюсь, так как ответ на проблему - на самом деле BOB
Вы можете решить это с минимаксным алгоритмом. Вот код в Java
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
int t = ni();
for(int i=0; i<t; i++){
int n = ni();
Map<Long, Boolean> map = new HashMap<Long, Boolean>();
int[] numbers = new int[n];
for(int j=0; j<n; j++){
numbers[j] = ni();
}
if(aliceWin(numbers, map)) System.out.println("Alice");
else System.out.println("Bob");
}
}
public static boolean aliceWin(int[] a, Map<Long, Boolean> map){
long h = hashCode(a); int temp;
if(map.containsKey(h)) return true;
for(int i=0; i<a.length; i++){
if(a[i]>0){
temp = a[i] ;
a[i] = 0;
if(isIncreasing(a)){
map.put(h, true);
a[i] = temp;
return true;
}
if(!aliceWin(a, map)) {
map.put(h, true);
a[i] = temp;
return true;
}
a[i] = temp;
}
}
return false;
}
public static long hashCode(int[] a){
long result = 0;
for(int i=0; i<a.length; i++){
result = (result << 4) + a[i];
}
return result;
}
public static boolean isIncreasing(int[] a){
int last = 0;
for(int i=0; i<a.length; i++){
if (a[i] > 0){
if(last > a[i]) return false;
last = a[i];
}
}
return true;
}
public static int ni(){
return sc.nextInt();
}
public static void print(Object... args){
System.out.println(Arrays.deepToString(args));
}
}
Вот некоторый код, который строит график для вас, но требует, чтобы вы вызывали reverse() на графике, создавали исходный узел, соединяющийся со всеми узлами в базе, возвращались к источнику, чтобы увидеть, есть ли способ, которым победит Алиса.
input_ = """2
3
1 3 2
5
5 3 2 1 4""".splitlines()
perms = [map(int,perm.split()) for perm in input_ if len(perm)>1]
"[['1', '3', '2'], ['5', '3', '2', '1', '4']]"
if networkx is None:
import networkx
from itertools import combinations
def build_graph(perm):
base = set()
G = networkx.DiGraph()
for r in range(1,len(perm)+1):
for combo in combinations(perm,r):
combo = list(combo)
if combo == sorted(combo):
base.add(tuple(combo))
continue
for i in range(r):
G.add_edge(tuple(combo),tuple(combo[:i]+combo[i+1:])) #you may want to reverse the graph later to point from base to source.
return G,base
def solve(G,base):
#dfs,
pass
for perm in perms:
G,base = build_graph(perms[0])
print solve(G,base)
Мы не можем просто проверять на каждом шаге, что... делает одно изменение следующим игроком, сортирует последовательность... если да, тогда делает другой ход... или продолжает движение
например, 5 3 2 1 4, если Алиса делает 3 2 1 4 Боб не может выиграть за один ход, исключая любой... как, если он делает 2 1 4, он не сортируется.. он делает 3 1 4, он не сортируется.. он делает 3 2 4, он не отсортирован.. поэтому 5 3 2 1 4 -> 3 2 1 4 - правильный ход!!
теперь очередь Боба.. он проверит то же самое.. но через некоторое время.. не будет такого числа, чтобы вы могли сделать ход, как указано выше... так что вам придется сделать случайный ход и кто выиграет, то может быть легко рассчитано по количеству шагов, которые превратят последовательность в один элемент!!
Для меня (используя почти ваши собственные слова):
Если он / она в состоянии сделать его строго увеличивающимся с первого хода, он / она выигрывает (тривиальный случай), иначе победитель определяется количеством элементов в этой последовательности.
Возьмите свой второй случай в качестве примера.
Я думаю, что решение с графиком хорошо, но оно забывает, что игроки играют оптимальным образом. Поэтому не нужно проверять все разные пути, так как некоторые из них будут получены из-за неоптимального выбора.