TRAI6-Editorial (2021 HEADLINES)

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Setter: Harikrishna N

DIFFICULTY:

Medium

PREREQUISITES:

Extended Euclidean Algorithm and Linear Diophantine Equation.

Problem

There are two microchips for each robot (A and B). You are given powers of microchips A and B along with the total power C that is required to neutralize a robot. We need to find how many robots can be neutralized.

Observations:

  1. We can only insert a whole number of microchips.

  2. We can represent the problem in the form of Ax + By = C

Where, A = power of microchip A, B = power of microchip B, C = power required to neutralize the robot.

Therefore, we need to check if there is a positive integer solution for the above equation.

Explanation

There exists an integer solution for Ax + By = C if and only if C is a multiple of gcd(A, B) (Bezout’s identity).

Condition for an integer solution to exist:
C % gcd(A,B) = 0

Now we need to check if the equation has a positive solution.

For finding the initial solution of the equation Ax + By = gcd(A, B), we need to use the Extended Euclidean Algorithm.
Let (xg, yg) be the solution of Ax + By = gcd(A, B)

For finding initial solution of Ax + By = C, by using (xg, yg) we need to use Linear Diophantine Equation
Let (x0, y0) be the initial solution of the equation Ax + By = C.

From linear Diophantine equation, any general solution can be written as:

  1. x = x0 + k*(B/g)
  2. y = y0 - k*(A/g)

Where k is any integer and g is gcd(A, B)
Proof of the above equation

The above general solution gives all possible solutions of Ax + By = C for different values of k. We need to check if there is at least one solution such that x > 0 and y > 0.
Therefore,

  1. x0 + k*(B/g) > 0
  2. y0 - k*(A/g) > 0

So from rearranging the above two equations we get,
k > (-x0 * g) / B => L
k < (y0 * g) / A => R

Equation L and R can be considered the range of k (where k is an integer)
If there exist at least one integer between L and R, there is a positive integer solution

Time Complexity:
O(n * log(n))

Setter's Solution 
import sys

def multiple_input(): return map(int, sys.stdin.readline().strip().split())

def list_input(): return list(map(int, sys.stdin.readline().strip().split()))

def initial_solution(a, b):
    if a % b == 0:
        return [0, 1, b]
    x, y, gcd = initial_solution(b, a % b)
    return [y, x - (a // b) * y, gcd]


for _ in range(int(input())):
    n = int(input())
    count = 0

    for i in range(n):
        a, b, c = multiple_input()
        xg, yg, g = initial_solution(a, b)  

        # if c is not multiple of gcd(A, B), then solution does not exist.
        if c % g != 0:  
            continue

        else:
            # initial solution of Ax + By = C
            x0, y0 = xg * (c // g), yg * (c // g)  

            y = (y0 * g) / a
            x = (-x0 * g) / b

            if y - x > 1:
                count += 1
            elif y - x == 1:
                if y // 1 != y:
                    count += 1
            elif 0 < y - x < 1:
                if y != y // 1 and x != x // 1:
                    if y // 1 != x // 1:
                        count += 1
    print(count)
1 Like