lucky number game

This was a medium level kind of Problem from CodeChef and basically focused on your ability to understand the problem and to check whether you go for iterative approach or you understand the problem in the Optimal way, bcz if you go for iterative way then surely you will get a TLE, so keep that in mind.

It was kinda productive day cause there was no college today, and most probably there won't be any tomorrow too. Maybe tomorrow I will be blogging on some concept of OS. 

  

Well, of to Linux See Ya!

Problem Statement:-

Bob and Alice are playing a game with the following rules:

• Initially, they have an integer sequence ${�}_1,{�}_2,\dots ,{�}_{�}$; in addition, Bob has a lucky number $�$ and Alice has a lucky number $�$.
• The players alternate turns. In each turn, the current player must remove a non-zero number of elements from the sequence; each removed element should be a multiple of the lucky number of this player.
• If it is impossible to remove any elements, the current player loses the game.

It is clear that one player wins the game after a finite number of turns. Find the winner of the game if Bob plays first and both Bob and Alice play optimally.

Input

• The first line of the input contains a single integer $�$ denoting the number of test cases. The description of $�$ test cases follows.
• The first line of each test case contains three space-separated integers $�$, $�$ and $�$.
• The second line contains $�$ space-separated integers ${�}_1,{�}_2,\dots ,{�}_{�}$.

Output

For each test case, print a single line containing the string "ALICE" if the winner is Alice or "BOB" if the winner is Bob (without quotes).

Constraints

• $1\le �\le 10$
• $1\le �\le 2\cdot 10^5$
• $1\le �,�\le 100$
• $1\le {�}_{�}\le 10^9$ for each valid $�$

Subtasks

Subtask #1 (18 points): $�=�$

Subtask #2 (82 points): original constraints

Sample 1:

Input

Output

2
5 3 2
1 2 3 4 5
5 2 4
1 2 3 4 5

ALICE
BOB

Explanation:

Example case 1: Bob removes $3$ and the sequence becomes $[1,2,4,5]$. Then, Alice removes $2$ and the sequence becomes $[1,4,5]$. Now, Bob is left with no moves, so Alice is the winner.

Code Implementation:-

for _ in range(int(input())):

    # Lucky Numbers

    n,bob_a,alice_b=map(int,input().split())

    # Numbers

    nums=list(map(int,input().split()))

    alice_coun,bob_coun=0,0

    # To check if there are common numbers associated to both Alice and Bob

    chk=False

    for num in nums:

        if((num%alice_b==0) and (num%bob_a==0)):

            chk=True

            continue

        if(num%alice_b==0):

            alice_coun+=1

        if(num%bob_a==0):

            bob_coun+=1

    if(chk==True):

        bob_coun+=1

       

    # Basically Bob will win only if he has greater nums associated with him,

    # else Alice wins

    print("BOB") if(bob_coun>alice_coun) else print("ALICE")

Explanation:-

To win the Game both players will first of all remove the lowest possible numbers at a single move, and considering this we can get the answer at constant Time Complexity. Simply if we think about it, then when the numbers associated to both the players(means the multiples of their lucky numbers) are distinct then if both of them have the same quantity then Bob loses as he is starting the game first, but there is a corner idea here that is when the numbers will intersect, like 15 can be a multiple of 5 and 3 both so it will be associated to both Bob and Alice. And for this cases, the simple idea is that Bob will remove all such elements in the very first move only so that Alice cannot get the move to use any of these numbers and thus Bob will get 1 number advantage for all such numbers. So... we don't care about how many intersecting numbers are present in the array, but we just care about are there any such numbers or not? If yes, then Bob gets 1 more number in his count of numbers, else not. And after all this we just check if Bob has his count of numbers greater than that of Alice or not, if yes then Bob wins else Alice wins. That's it!