[CSES] Coin Piles

2 minute read
Algorithm

Number Spiral

Task:

You have two coin piles containing $a$ and $b$ coins. On each move, you can either remove one coin from the left pile and two coins from the right pile, or two coins from the left pile and one coin from the right pile.

Your task is to efficiently find out if you can empty both the piles.

Input

The first input line has an integer $t$: the number of tests.

After this, there are $t$ lines, each of which has two integers $a$ and $b$: the numbers of coins in the piles.

Output

For each test, print "YES" if you can empty the piles and "NO" otherwise.

Constraints

  • $1 \le t \le 10^5$
  • $0 \le a, b \le 10^9$
Example

Input:
3
2 1
2 2
3 3

Output:
YES
NO
YES

Solutions:

Intuition:

Reducing the gap between 2 piles as fast as possible is the proper way. Because with each move, the gap reduces 1 unit and the valid state is when both piles contain $0$ coin. Hence, $x$ falls into 3 cases: ($x$ is the value of 2 piles when its value is same ).

  • $x=0$ $=>YES$
  • $x>0$: Because, it's equal, we need to do removing interchangeably until reaching $0$. That means we take out 3 coins for each move from 2 piles.
    • If x % 3 == 0 $=>YES$
    • Otherwise, $=>NO$
  • $x<0$ $=>NO$
How can we find x?. As mentioned, each move reduces 1 unit in the gap between them. Hence, the number of necessary move equals the gap, that's gonna make 2 piles have x coins after doing these amounts move.

Implementation:

 1def solve(a,b):
 2    # find the gap
 3    n=abs(a-b)
 4
 5    # assign x for a and b
 6    a=b=b-n if a>b else a-n
 7
 8    if a==0 and b==0:
 9        return "YES"
10    elif a>0 and a%3==0:
11        return "YES"
12    else:
13        return "NO"
14if __name__=="__main__":
15    for i in range(0,int(input())):
16        a,b=map(int,input().strip().split())
17        print(solve(a,b))
18

Analysis:

Time complexity: O(1).

Space complexity: O(1).

Help me water it