Interviewstreet- Перестановочная игра

Question

Алиса и Боб играют в следующую игру:

1) Для начала они выбирают перестановку первых N чисел.

2) Они играют попеременно, а Алиса играет первой.

3) По очереди они могут удалить любое одно оставшееся число из перестановки.

4) Игра заканчивается, когда оставшиеся числа образуют возрастающую последовательность. Человек, сыгравший последний ход (после которого последовательность увеличивается) выигрывает игру.

Предполагая, что оба играют оптимально, кто победит в игре?

Входной сигнал: Первая строка содержит количество тестовых примеров. Каждый случай содержит целое число N в первой строке, за которым следует перестановка целых чисел 1..N во второй строке.

Выход: Выведите T строк, по одной на каждый тестовый случай, содержащих «Алису», если Алиса выиграет игру, и «Боб» в противном случае.

Пример ввода:

2

3

1 3 2

5

5 3 2 1 4

Пример вывода:

Алиса

Bob

Ограничения:

1 <= T <= 100 </p>

2 <= N <= 15 </p>

Первоначально перестановка не будет возрастающей последовательностью.

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

В приведенной выше задаче для перестановки длины 2 всегда выигрывает игрок 1.

Для перестановки длины 3 игрок 2 выигрывает, если строка строго увеличивается или уменьшается.

Для перестановки длины 4, если игрок 1 может сделать строку, строго увеличивая или уменьшая ее, удаляя персонажа, он выигрывает, а игрок 2 выигрывает.

Отсюда вывод:

Если текущий игрок может сделать строку строго увеличивающейся, он / она выигрывает. (Банальный кейс)

Если он / она в состоянии сделать это строго уменьшая, победитель определяется количеством элементов в этой последовательности. Если в этой последовательности четное количество элементов, текущий игрок проигрывает, иначе выигрывает.

Но что делать, если результирующая строка не увеличивается и не уменьшается ??

Answer 1

Это типичная игровая проблема.У вас есть 2 ^ 15 возможных позиций, которые обозначают оставшиеся цифры.Из числа оставшихся чисел вы можете узнать, чья это очередь.Итак, теперь у вас есть график, который определяется следующим образом - вершины - это возможные множества оставшихся чисел, и есть ребро, соединяющее две вершины u и v, если есть ход, который изменяет набор u на набор v (то есть набор vимеет ровно на одно число меньше).

Теперь вы уже указали, для каких позиций вы сразу знаете, кто является победителем - те, которые представляют возрастающую последовательность чисел, которые эти позиции помечаются как проигрышные.Для всех остальных позиций вы определяете, выигрывают они или проигрывают следующим образом: позиция выигрывает, если есть край, соединяющий ее с проигрышной позицией.Таким образом, все, что осталось - это что-то вроде dfs с напоминанием, и вы можете определить, какие позиции выигрывают, а какие проигрывают.Поскольку граф относительно мал (2 ^ 15 вершин), это решение должно быть достаточно быстрым.

Надеюсь, это поможет.

Answer 2

Конечно, это может быть сделано с помощью "грубой силы" для малых N, но разве вы не подозреваете, что более легкий ответ вокруг инверсий и знака перестановки ?

Первоначально я подозревал ответ типа «Алиса выигрывает, если знак -1, иначе проигрывает», но это не так.

Но я хотел бы предложить представление проблемы, котораяне только ваш алгоритм может использовать, но и тот, который в равной степени повысит ваши бумажно-перьевые характеристики в этой игре.

Инверсия - это пара индексов, которые яа [J].Рассмотрим (i, j) ребро неориентированного графа с вершинами 1, ..., N.Каждый игрок удаляет вершину из этого графа и выигрывает, если не осталось ребер.

Для 5 3 2 1 4 результирующий граф равен

   5--3
  /|\ |
 / | \|
4  1--2

, и Алиса быстро видит, что удаление «5»дает Бобу возможность удалить 2. Тогда инверсии не осталось, и Боб выигрывает.

Answer 3

Эту игру можно решить рекурсивно.

Каждый раз, когда Алиса берет свой первый пик и выбирает i, вычитайте 1 из всех оставшихся чисел, которые больше, чем i. Теперь у нас та же игра, но с номерами от 1 до N-1

допустим, ваша последовательность

1,3,5,4,2

на своем первом ходу Алиса может выбрать любое число. Случай 1: она выбирает 1, Алиса может выиграть, если Боб не может выиграть с 3,5,4,2 (эквивалентно 2,4,3,1)

Вариант 2: сначала она выбирает 3 Алиса может выиграть, если Боб не может выиграть с 1,5,4,2 (эквивалентно 1,4,3,2)

Вопрос 3: сначала она выбирает 5 Алиса может победить, если Боб не может выиграть с 1,3,4,2

Вы поняли идею.

Таким образом, вы можете создать рекурсивную функцию для выработки решения для перестановки размера N, используя перестановки размера N-1 для каждого возможного первого предположения. базовый случай для рекурсии - когда у вас есть последовательность в порядке.

На каждом этапе рекурсии человек пробует все возможности и выбирает все, что заставляет их победить.

Поскольку существует множество комбинаций ходов, которые могут перейти к одной и той же последовательности, рекурсия имеет перекрывающиеся подзадачи. Это означает, что мы можем использовать динамическое программирование или просто «запоминать» нашу функцию, что значительно повышает эффективность.

Для дальнейшего ускорения можно использовать симметрию в перестановках, так как многие группы перестановок эквивалентны, например, обратное преобразование одной перестановки даст тот же результат.

Удачи.

Answer 4

Вы можете решить это с минимаксным алгоритмом.Вот код в 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));  
    }  
}  

Из блога: hackerrank-permutation-game

Answer 5

@ tiwo, @ rup COnsidering 5 3 2 1 4 - последовательность, в которой сначала Алиса удаляет 5, а Боб удаляет 2, затем последовательность 3 1 4, что не в порядке возрастания, тогда Алиса получает возможность удалить 1, а последовательность в порядке возрастания Алиса должна быть ответом. На графике, который вы дали, должно быть ребро между 3 и 1, так как 1 и 3 в инверсии.

Пожалуйста, скажите мне, где я ошибаюсь, поскольку ответ на вопрос - на самом деле БОБ

Answer 6

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

как 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 - правильный ход !!

Теперь очередь Боба .. он проверит то же самое .. но через некоторое время не будет такого числа, чтобы вы могли сделать ход, как указано выше ... так что вам нужно будет сделать случайный ход, и тот, кто победит, может быть легко рассчитан по количеству шагов, которые превратят последовательность в один элемент !!

Answer 7

Вот некоторый код, который строит график для вас, но требует, чтобы вы вызывали 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)

Answer 8

Для меня (используя почти ваши собственные слова):

Если он / она может увеличить его с первого хода, он / она выигрывает (тривиальный случай), в противном случае победитель определяетсяколичество элементов в этой последовательности.

Возьмите в качестве примера второй случай.

Я думаю, что решение с графиком в порядке, но оно забывает, что игроки играют оптимальным образом.Поэтому не нужно проверять все разные пути, поскольку некоторые из них будут получены из-за неоптимального выбора.