Problem Statement

Fox Ciel and Toastman are playing a game. The game uses a memory and N cards. Initially the value of the memory is set to zero. You are given a int[] cards containing exactly N elements. cards[i] is the number written on the i-th card. Ciel and Toastman take alternate turns, and Ciel plays first. In each turn, the player chooses a card and removes the card from the game (this card can’t be used later). If the chosen card contains x and the value of the memory is y, the value of the memory is changed to (x | y). The ‘|’ symbol stands for bitwise OR (see notes for clarification). If a player can’t make a move (because there are no cards left), or if after a player’s move the memory becomes 511, this player loses. Determine the winner when both players play optimally. If Fox Ciel wins, return “Fox Ciel”.

Tutorial

The problem is a variation of game theory problem. In this, both players play optimally. Consider a case where the number of N <= 10, then we can backtrack all possible permutation and output the result. But, we know that it doesn’t work for our constraints. In that case, we need to come with states and avoid recomputation. By understanding the game better, we can conclude that for any given round the memory score is what matters. Let us consider, player1, he can start the round with N possibilities. But, he picks the one that yields a winning. For any given Ith round with score M, the permutation of selection in the previous round doesn’t matter, and this works because of ‘|’ operation. Finally, the dp states will be [Score][Round]

Code

import java.util.*;
import java.math.*;
import static java.lang.Math.*;

public class FiveHundredEleven {


	int [][] dp = new int[560][55];
	int N;
	int [] cards;
	boolean [] visited = new boolean[55];
	int go(int memory_value, int n)
	{
		if(memory_value == 511)
			return (n % 2 == 0)? 1 : 0 ;
		if(n == N)
			return (n%2 == 0)? 0 : 1;

		int res = dp[memory_value][n];
		if(res != -1)
			return res;

		dp[memory_value][n] = (n % 2 == 0) ? 0 : 1;
		for(int i= 0 ; i < N ; i ++)
		{
			if(visited[i] == false)
			{
				visited[i] = true;
				if(n%2 == 0)
					dp[memory_value][n] = max(dp[memory_value][n], go(memory_value | cards[i], n+1));
				else
					dp[memory_value][n] = min(dp[memory_value][n], go(memory_value | cards[i], n+1));
				visited[i] = false;
			}

		}
		return dp[memory_value][n];
	}


	public String theWinner(int[] cards) {

		for(int i = 0 ; i < 560 ; i ++)
			Arrays.fill(dp[i], -1);
		N = cards.length;

		this.cards = cards;
		int aux = go(0, 0);

		if(aux == 0)
			return "Toastman";
		return "Fox Ciel";
	}
}

• ← Previous Post
• Next Post →