Axel and Shawn’s Football game

Moderate
0/80
profile
Contributed by
1 upvote
Asked in company
Adobe

Problem statement

Axel and Shawn just finished their football practice and are now tired, so they can’t go back and play football, but they have come up with a new game to make the best out of their time.

There are two rooms, one of the rooms has ‘N’ baskets and the other has ‘M’ baskets, each basket is large enough to hold multiple footballs. In each turn, a player has to select a basket from their respective room and pick up some positive number of football(s), the player loses if he is not able to pick up any football.

In each round Axel plays the first turn and Shawn plays the second one. Both Axel and Shawn should be in different rooms when the round starts. Before the start of each round, you can decide the room each player is assigned. Axel is your close friend and you will try your best to make Axel win the game. Predict the winner if both the players play optimally and you try your best to make Axel win the game.

For Example : 
If room1: {1, 2, 3} and room2: {1, 1}

Then, Axel will be assigned room1 at the beginning of each round, and both Shawn and Axel will pick only one football in each round as they play optimally, this will result in Shawn exhausting the remaining balls in room2 early, and ultimately losing the game.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains two integers ‘N’ and ‘M’ denoting the number of baskets in each of the rooms respectively.

The next two lines of each test case contain the information about the balls in each basket, the first line contains ‘N’ integers denoting the balls in each basket of room-1 and the next line contains ‘M’ integers denoting the balls in each basket present in room-2.
Output Format : 
For each test case, print the name of the winner, print “Axel” if it’s possible for Axel to win the game, else print “Shawn”.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 ≤ T ≤ 10      
1 ≤ N, M ≤ 10000
0 ≤ Room1[i], Room2[i] ≤ 10^9

Time limit: 1 sec
Sample Input 1 :
2
3 2
1 2 3
1 1
1 1
5
7
Sample Output 1 :
Axel
Axel
Explanation For Sample Input 1 :
For test case 1 :
Axel will win because:
He will be assigned room1 at the beginning of each round, and both Shawn and Axel will pick only one football in each round as they play optimally, this will result in Shawn exhausting the remaining balls first, and ultimately losing.

For test case 2 : 
Axel will win because:
Axel will be assigned to room-1 as it has more footballs, and in each round both the players will pick one football, Axel will ultimately win the game.
Sample Input 2 :
2
1 1
5
5
4 3
4 0 2 1
3 1 0
Sample Output 2 :
Shawn
Axel
Hint

Axel will win the game if is placed in the room with more footballs at the beginning of each round, as both Axel and Shawn will remove only one football in each round. Try to find the conditions where Shawn will win!

Approaches (1)
Brute Force

Let’s start from a case when the game is fair and you are not allowed to assign rooms for Axel and Shawn. In this case, each person is assigned a room at the beginning and he continues to play in that room till the end of the game. Both the players will choose one football from any of the non-empty baskets in their room, this will result in Axel winning the game if and only if the total number of footballs in his room is greater than that in Shawn’s room. If both the rooms have an equal number of footballs then Axel will still lose as he is the first one to play his turn in each round.

 

Now let’s extend this logic to include the fact that you can assign a room to each player at the beginning of each round. From the above discussion about the fair case, the quickest intuition one might get here is that Axel will lose only if both the rooms have an equal number of footballs, but is this condition sufficient? The answer to this is NO, consider a case when room1 = { 1, 2, 3 } and room2 = { 6 }, in this case, both the rooms have an equal number of footballs, but Axel can still win if he is assigned room2 in the first round, as he will pick up all the 6 footballs from the only basket in that room, but Shawn at pickup 3 footballs at max from room1, so the rooms will now become: room1 = { 1, 2, 0 } and room2 = { 0 }, now for the second round Axel can be placed in the room1, and he will surely win as this room has a larger number of footballs. Try to think of the conclusion of this on your own!

 

To conclude, Axel can only lose the game if and only if the configuration of all non-empty baskets are the same in both the rooms, for all other cases Axel will always win the game.

 

The steps are as follows :

  1. Sort both the arrays ‘room1’ and ‘room2’ in decreasing order.
  2. Remove all the empty baskets from both rooms. As the array is sorted in decreasing order, so the empty baskets will be in the end and removing an element from the end of an array takes constant time.
  3. Compare ‘room1’ and ‘room2’, if they are similar then “Shawn” will win the game, else “Axel” will win in all other cases.
Time Complexity

O( N * log(N)  + M * log(M) ), where N and M denote the number of baskets in each room

 

We sort the baskets in each room to compare both the rooms, sorting an array of length ‘L’ takes time ~L*logL.

Hence the time complexity is O( N*logN + M*logM ).

Space Complexity

O( 1 )

 

No extra space is used.

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Axel and Shawn’s Football game
Full screen
Console