CHEFTET - Editorial

PROBLEM LINK:

Practice
Contest

Author: Dymtro Berezein
Tester: Mugurel Ionut Andreica
Editorialist: Praveen Dhinwa

DIFFICULTY:

simple

PREREQUISITES:

simple math

PROBLEM:

You are given two arrays A and B. For each element B_i, you add B_i to either A_{i - 1} (provided it exists, i.e. i \geq 1), A_i or A_{i + 1} (provided it exists, i.e. if i < n). You have to tell whether you can make all the elements of the array A after all the operations equal or not. If yes, then what is the biggest number that you can achieve?

EXPLANATION:

First thing that you should note that each element of array B is added to some elements of the array A. Also, note that each element is added exactly once.

Due to the above observation, we can notice that sum of all the elements of the array A will be old sum of array A plus sum of array B. Let C denote the final array A we will get after adding elements of B. The sum of all elements of array C will be sum of elements of arrays A and B. Let us denote this sum by S. We want all elements of the array C to be equal, so S should be divisible by n.

Now, each element of the array C will be equal to \frac{S}{n}.

So, we know the final desired value of each element of the array C. It might be possible that this value is not achievable by our operations. If it is possible to achieve this value, then this is the only value that we can get for array C and so by default this will also be biggest value that we can get for each element of C.

Now, for checking whether it is possible to make each element of array equal to S or not. We can use a greedy solution which relies on the fact that for i-th element of array B, we are making changes in array B at quite a few indices which are very near to index i itself.

Let us iterate over array A from left to right and check for each element the set of elements from array B that we can add to get the desired value S.
Let us start from index 1.

  • If A_1 > S, then we can never get C_1 = S, as all the elements of array B are positive.
  • Otherwise, If we have A_1 < S, then we want to add S - A_1 into array A.
    • If B_1 = S - A_1, then we can add B_1 to A_1. Change value of B_1 to 0.
    • Otherwise if B_2 = S - A_1, then we can add B_2 to A_1. Change value of B_2 to 0.
    • If B_1 + B_2 = S - A_1, then we can add B_1 + B_2 to A_1. Change value of B_1, B_2 both equal to zero.
    • Otherwise, we can never make A_1 equal to S.
  • Now, we proceed for A_2. We add B_1 into A_2. Note that if the element B_1 of the original array was added to A_1, then we had already changed it to 0. So, it won’t be added twice. Also notice that you can’t omit to add B_1 now, as if it is not added for A_2, it can’t be added for any element A_3 and onwards. After that want to add B_2 and B_3 and want to make A-2 equal to S. This case is very similar to what we did in the above case. We check the conditions correspondingly and proceed.
  • Now, after the end, we know that we are able to make elements of A equal to S. We should check the condition that each B_i is indeed used. You can do it by checking whether there is some non-zero element B_i in array B.

Note that we are just doing a single pass over the array and greedily deciding the various conditions to check. This will be an \mathcal{O}(n) solution.

Setter’s and Tester’s Solutions:

Tester’s solution
Editorialist’s solution

1 Like

Can’t access both the solutions.

2 Likes

In this problem can any one help me to understand why i got stuck in the 10th test case…??
here is my solution…
https://www.codechef.com/viewsolution/10759208

How s/n will be the biggest value possible? Not able to understand it, please explain.

why is it that my code is stuck at 7th and 12th test case ? CodeChef: Practical coding for everyone

Priority is given to i - 1 element to be included, is this the correct order to check:

  1. b[i - 1]
  2. b[i - 1] + b[i]
  3. b[i - 1] + b[i + 1]
  4. b[i - 1] + b[i] + b[i + 1]
  5. b[i]
  6. b[i + 1]
  7. b[i] + b[i + 1]

can anybody help me why i got stuck in 9th test case?? here is my code:CodeChef: Practical coding for everyone

i tried it using different method, can anyone check this method and tell why it isn’t satisfying few cases CodeChef: Practical coding for everyone

Also, the backtracking solution to check all possible states worked :slight_smile:

Code

1 Like

hi can any one please tell me why my solution is not working for test case 8,9,11 because i have implemented by seeing tester’s solution?
Or can any one please provide me test case at which my program is not working?
Thanks

@prashan_93_y: if remainder of s/n is 0, then it is possible, else it is not possible at all to find such a solution.
If possible, that will be the only biggest value, as you can not make a number greater than average, for each number to be equal.

@the_run: Please add your answer as a comment to @prashan_93_y’s comment. It seems that you mistakenly wrote answer instead of comment.

@aj619 Your code would output “-1” for the following test case wherein the answer is “4”.

1

3

1 1 2

4 1 3

This is because the case “A[i]+B[i]+B[i+1]==S” is checked before “A[i]+B[i-1]+B[i+1]==S” (where S=sum/N). So, in a case where B[i-1]==B[i], you would choose to add B[i] to A[i] instead of B[i-1] resulting in B[i-1] not being added to any element in array A and also A[i+1], which should have had B[i] added to it, will be deficit of it.

1 Like

Fixed now. :slight_smile:

Your order is not correct a[i]+b[j-1]+b[j+1] should come earlier than a[i]+b[j]+b[j+1]. Just think why ? If not able to figure out comment :slight_smile:

1 Like