PROBLEM LINK:
Author: Vitaliy
Tester: Jingbo Shang
Editorialist: Ajay K. Verma
DIFFICULTY:
EASY
PREREQUISITES:
High school maths
PROBLEM:
Given a set of N linear equations (of a very specific form) on N variables, find if it has a solution where all variables take non-negative integer values, and if so, find such a solution where sum of variables is minimum.
QUICK EXPLANATION:
Since the equations are of a very specific form, they can be solved in linear time (discussed in more detail in the next section). One only needs to check if the solution consists of non-negative integer values. Also special care should be taken for the case N = 2, as in that case the set of equations is redundant.
EXPLANATION:
We are given two arrays H and D of the same size N, where H[i] represents the current height of i-th stem and D[i] represents the target height of i-th stem. A single operation on the i-th stem reduces its height by one unit and increases the height of all other stems by one unit. The goal is to find the minimum number of operations using which we can achieve the target height of all stems, if possible.
Let us represent the number of operations performed on i-th stem by variable xi.
Clearly, xi must be a non-negative integer for all i.
Using these variables we can write the height of i-th stem at the end of all operations as follows:
H[i] - xi + (x1 + x2 + … + xi - 1 + xi + 1 + … + xN)
Let us represent (x1 + x2 + … + xN) by a new variable s. Using this new variable we can rewrite the above expression as
H[i] + s - 2xi
Since the target height of the i-th stem is D[i], this gives us the following equation:
D[i] = H[i] + s - 2xi
Adding all these N equations (corresponding to each i) we get the following equation:
D[1] + D[2] + … + D[N] = H[1] + H[2] + … + H[N] + s * N - 2 (x1 + x2 + … + xN)
i.e., D[1] + D[2] + … + D[N] = H[1] + H[2] + … + H[N] + s * (N - 2)
Let us define two new constants
d = D[1] + D[2] + … + D[N]
h = H[1] + H[2] + … + H[N]
Using these constants the above equation can be written as
d = h + s * (N - 2)
This equation may provide us the value of s, if N != 2. We will handle the case of N = 2 later, for the time being let us assume N != 2.
s = (d - h) / (N - 2)
If s is not an integer, or s < 0, then we can immediately deduce that no valid solution (non-negative integer valued) of the above system of equations exists. On the other hand, if s is a non-negative integer, then we can compute each of the xi and check if it is a non-negative integer.
D[i] = H[i] + s - 2xi.
Hence, xi = 0.5 * (s + H[i] - D[i])
If all xi’s are valid, then the number of operations is x1 + x2 + … + xN = s, which we have already calculated. Note that in this case, we do not have to minimize anything as there is a unique solution.
Case where N = 2
In case of N = 2, we have only two equations:
D[1] = H[1] - x1 + x2
D[2] = H[2] - x2 + x1
Note that, the two equations are redundant, and hence they will either have no solution or an infinite number of solutions.
x1 - x2 = H[1] - D[1]
x1 - x2 = D[2] - H[2]
The LHS of both equations are the same, if the RHS are not the same, then we have no solution of this system of equations. On the other hand if the RHS are the same (say with value r), then we have infinitely many solutions, given by the following parametric representation:
x2 = t
x1 = t + r
where t is a free variable and can take any value.
Both x1 and x2 are non-negative. Hence t >= max(0, -r). Also we want to minimize (x1 + x2) = 2t + r, hence t must be as small as possible.
This means that in order to minimize the number of operations we should choose
t = max(0, -r)
The number of operations in this case is 2t + r = 2 * max(0, -r) + r = abs(r).
Time Complexity:
O (N)
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution will be put up soon.
Tester’s solution can be found here.
