LEBAMBOO - Editorial

PROBLEM LINK:

Practice
Contest

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.

6 Likes

OMG !, did it mean that there can be a single operation on a particular stem ?

No, there can any number of operations performed on a single stem.

Can you give me a test case where

N>2, d-h>0, (d-h)%(N-2)==0,(s+D[i]-H[i])%2 == 0

BUT xi<0 where xi = 0.5 * (s + H[i] - D[i]).

I got 20 WA because i missed the last condition :frowning:

As this have a unique solution, so no minimization required. I used a different approach.
First I calculate the D[i]-H[i], let we get R[i]. To attain D[i], we apply operation on minimum(R[i]) and we get R[i] = R[i]-1 (for all i != index of minimum(R[i])) and R[i] = R[i]+1 (for all i == index of minimum(R[i])). Do this operation till sum(R[i])>=0. If we get sum(R[i])<0 and we still not able to made all R[i]==0. Means no solution exist otherwise answer is number of steps involved. Here is my http://www.codechef.com/viewsolution/2775597

1 Like

N = 3
H = {0, 4, 2}
D = {10, 0, 0}

d = 10, h = 6, s = 4,

x1 = -3, x2 = 4, x3 = 3

1 Like

Well, never in any way could I have thought that the logical solution could be this simple and efficient.
Hats Off! My approach was, find the diff[i] = h[i]-d[i], for 0<=i<n, then the problem reduces to this “Make all elements of the diff array zero by doing this Operation - Increase any one element by one and reduce all other elements by one” . Now here I guessed(strengthened by some examples and my intuition) that we find the minimum-most element of diff array, and increase it by one, and decrease all others by one. Now I got stuck at how many times should I repeat this process, so as to check if the process is valid. For that I observed that during each Operation, the sum of all elements of diff array, decreases by n-2. So, the number of steps I should repeat this process was S/(n-2), where S is the sum of all elements of the diff array. After that I simply checked if all elements are zero , if yes then S/(n-2) is the answer else -1. And I seperated the cases of n==1 and n==2 . The Complexity of this approach is somewhere between n and n*n

2 Likes

My process is similar to the one described by vivekjnv93, I simply added the finer details.

1 Like

In the question, it is given that 1 <= Hi, Di <= 50
is it possible to get negative xi by satisfying this condition
and also satisfying N>2, d-h>0, (d-h)%(N-2)==0,(s+D[i]-H[i])%2 == 0?

Just increase all the numbers in D and H by 1, i.e.,

N = 3 H = {1, 5, 3} D = {11, 1, 1}

d = 13, h = 9, s = 4,

x1 = -3, x2 = 4, x3 = 3

1 Like

thank you :slight_smile:

For me, this was a bad experience. May be because I was relocating, and didn’t have time to spend behind the problem.

But, I wrote a code to do some brute forcing on small inputs and see some properties and patterns, and figured something out (which I still can’t explain). I wrote the code for it, and luckily, it accepted.

Feeling bad that I got a code accepted, and still I don’t really know what is happening!!

One thing I found out that, for any D to be a valid sequence from H, the difference sequence D-H (or equivalently H-D) should all be either odd numbers or even numbers.

When applying an operation once, the sum of heights should increase by exactly n-2. So, for n>2 (n=1 and n=2 can be handled separately as simple base cases, and need not be put into this), the difference sum(D) - sum(H) should be positive and a multiple of n-2. So, if this holds, then we would have performed exactly (sum(D)-sum(H)) / (n-2) operations, which would be our answer, if it satisfies that the number of steps be odd or even, according as the individual differences as said in the above para are odd or even. (Honestly, i figured it out by brute forcing on small inputs, and found it that these are necessary conditions, and have no idea, why these are sufficient.)

Here is a link to my code: http://www.codechef.com/viewplaintext/2823882

If anyone would like to comment or shed some more light on this (I mean, why those conditions are sufficient), you are welcome. And I thank you for that, in advance.

1 Like

I have looked at the editorials and other solutions but still can’t figure out what is wrong with my solution. Can someone give a test case which fails the below solution ?

http://www.codechef.com/viewsolution/2795221

2
2 2
1 3

Answer should be 1.

1 Like

Thanks a lot @kevinsogo !

is there any one tried like this
http://www.codechef.com/viewsolution/2759384

Loved this problem!

could u pls explain how is it working for n=1 ?