JAGAM Editorial

PROBLEM LINK:

Practice
Contest

Author: Aleksa Plavsic
Tester: Hussain Kara Fallah
Editorialist: Hussain Kara Fallah

PROBLEM

Vanja and Miksi are playing a game on N integer numbers. There is a counter S which is equal to 0 at the beginning. At each turn, each player picks a number from the array and either subtract it or add it to S. You are given also 2 numbers Z1, Z2. Whenever the counter is equal to one of them the player who played the last move wins. At least one turn should be played.

Assuming both players are playing optimally you have to determine the winner. In some cases, none of the players can win the game and if they are playing optimally it may last for more than 1010 turns. In such case, you need to tell that the game ends in a tie. Vanja starts the game.

DIFFICULTY

EASY

EXPLANATION

If our array contains any of these values {Z1, Z2, -Z1, -Z2}, then the first player can win by 1 move.

Let’s introduce the term dead end. Whenever a player has his turn and he is not able to win in 1 move and no matter what number he chooses the other player can pick a number and make S equal to Z1 or Z2, then our player is in a dead end.

We need to check if Vanja’s first move is a dead end. In case it’s, then Miksi is the winner. Otherwise, we are sure that the game will last for more than 2 turns.

In such case (more than 2 rounds), we can prove that the game ends in a tie. No matter which player is taking the turn (since each player knows the numbers given and Z1, Z2), he can determine whether he is in a dead end or not. In case he is, he can just play exactly the opposite of the move the last player did and avoid losing the game (and since the previous player couldn’t win at his previous turn, the game lasts forever).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s/Editorialist’s solution can be found here.

2 Likes

i got a time limit error using bfs can this be simplified

import java.util.;
import java.lang.
;
import java.io.*;

class cd62
{
public static void main(String args[])throws IOException
{

	int i,j;
	
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	
	int T = Integer.parseInt(br.readLine());
	
	while(T>0)
	{
		int s = 0;
		
		HashMap<Integer,Integer> hmap = new HashMap<>();
		
		LinkedList<Integer> queau = new LinkedList<>();
		
		String input = br.readLine();

		String[] strs = input.trim().split("\\s+");

		int arr[]  = new int[strs.length];
	
		for (i = 0;i< strs.length; i++)
		{
		arr[i] = Integer.parseInt(strs[i]);
		}		
		
		//int N = Integer.parseInt(br.readLine());	
		
		int Z1=arr[1],Z2=arr[2];
		
		String input2 = br.readLine();

		String[] strs2 = input2.trim().split("\\s+");

		int arr2[]  = new int[strs2.length];
	
		for (i = 0;i< strs2.length; i++)
		{
		arr2[i] = Integer.parseInt(strs2[i]);
		
		}		
		
		queau.add(s);	
			
		hmap.put(s,0);
		
		int count =  0;
		
		while(!queau.isEmpty())
		{
			if(count==Math.pow(10,10))
			{
				System.out.println(0);
				
				break;
				
			}
			
			int temp = queau.poll();
			
			if(temp==Z1)
			{
				if(hmap.get(temp)%2==0){
					
				System.out.println(2);
					
					
				}else
				{
						System.out.println(1);
					
				}
				
				break;
				
				
			}else if(temp==Z2)
			{
				
				if(hmap.get(temp)%2==0){
					
				System.out.println(2);
					
					
				}else
				{
						System.out.println(1);
					
				}
				
				break;
				
			}
			
			for(i=0;i<arr2.length;i++)
			{
				queau.add(temp+arr2[i]);
				queau.add(temp-arr2[i]);
				hmap.put(temp+arr2[i],hmap.get(temp)+1);
				hmap.put(temp-arr2[i],hmap.get(temp)+1);
			}
	
			count++;
				
			}
		
		T--;
		
	}
	
	
	
}

}