Last Updated: 23 Oct, 2021
Axel and Shawn’s Football game
Moderate
Asked in company
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.
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
Approaches
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 :
- Sort both the arrays ‘room1’ and ‘room2’ in decreasing order.
- 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.
- Compare ‘room1’ and ‘room2’, if they are similar then “Shawn” will win the game, else “Axel” will win in all other cases.