InterviewStreet Challenges: Permutation Game
Problem Statement
Alice and Bob play the following game:
1) They choose a permutation of the first N numbers to begin with.
2) They play alternately and Alice plays first.
3) In a turn, they can remove any one remaining number from the permutation.
4) The game ends when the remaining numbers form an increasing sequence. The person who played the last turn (after which the sequence becomes increasing) wins the game.
Assuming both play optimally, who wins the game?
Input:
The first line contains the number of test cases T. T test cases follow. Each case contains an integer N on the first line, followed by a permutation of the integers 1..N on the second line.
Output:
Output T lines, one for each test case, containing "Alice" if Alice wins the game and "Bob" otherwise.
Constraints:
1 <= T <= 100
2 <= N <= 15
The permutation will not be an increasing sequence initially.
Sample Input:
2
3
1 3 2
5
5 3 2 1 4
Sample Output:
Alice
Bob
Solution
#include<iostream>
#include<set>
using namespace std;
#define set(a,i) a|1<<i
#define unset(a,i) ((a)&(~(1<<i)))
int array[32770];
int permu(int a[],int n,int r);
int get1(int a,int i)
{
return ((a&(1<<i))>>i);
}
int main()
{
int T;
cin>>T;
while(T--)
{
for(int i=0;i<32768;i++)
array[i]=-1;
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
cin>>a[i];
int res=permu(a,n,(1<<n)-1);
if(res==0)
cout<<"Bob\n";
else
cout<<"Alice\n";
}
}
int permu(int a[],int n,int r)
{
if(array[r]!=-1)
return array[r];
int last=0,i;
for(i=0;i<n;i++)
{
if(get1(r,i)==1)
{
if(a[i]>last)
last=a[i];
else
break;
}
}
if(i==n)
{
array[r]=0;
return 0;
}
set<int> s;
for(int i=0;i<n;i++)
{
if(get1(r,i)==1)
{
s.insert(permu(a,n,unset(r,i)));
}
}
set<int>::iterator iter;
iter=s.begin();
if(*iter==1)
array[r]=0;
else
array[r]=1;
return array[r];
}
// If you find this blog somewhat helpful, please share it.......&.......Keep visiting..:)
I tried a solution using a Negamax algorithm with AB pruning and memoization of permutations but it simply took too long. Maybe 10 seconds instead of the allotted 5.
ReplyDeleteYour solution is super fast but the bit tricks are unclear. Can you explain what they represent in the problem domain?
r indicates current permutation (using bit mask), and array[] is just memoization (recurisve algo speed-up). Seems easy after short study, but not quite easy to come up with. Good job Sachin!
DeleteAccording with statement the second example can be played as follow, [5 3 2 1 4] If Alice removes 5 => [3 2 1 4] Bob removes 1, 2 or 3 => [3 2 4] , [3 1 4] or [2 1 4] Alice can remove from above cases (3 or 2), (3 or 1) or (2 or 1) => [2 4] [3 4], [1 4] [3 4] or [1 4] [2 4] in all these are incremental, hence this is the last turn. Therefore Alice wins all cases, no chance for Bob. How is possible that Bob wins in the example?
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteOther approach:
ReplyDeleteimport 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 map = new HashMap();
int[] numbers = new int[n];
for(int j=0; j map){
long h = hashCode(a); int temp;
if(map.containsKey(h)) return true;
for(int i=0; i0){
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 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));
}
}
from http://traceformula.blogspot.com/2015/12/hackerrank-permutation-game.html