Not an editorial!! Need help with chef and mover problem(August long contest)

general
, , , ,
1

Hello everyone,

Problem: Chef and Mover(August 2017 contest problem)

This is not an editorial and I believe what I’ll say isn’t even right. I just want you to guys please read my approach to this problem and please correct me where I’m wrong since I’m not able to solve this problem. So as we know the chef can add or subtract numbers from an array’s element to the other element with the help of mover(D). Let’s jump right to my approach. First, we will take the sum of the array and after that, we will divide the sum by the size of the array which will look like this in Java

 int x = sum/array.length;     //if we take the sum of an array and divide it by the size, for example 
                                 if we have 1 4 1 then the sum is 6 and x = 6/3 = 2 so now we know if we 
                                 want each element equal all element has to be 2, end up the array as 2 2 2

now, why we need “x”? x will help us to determine is it even possible to make all the elements of an array equal. So, to check that we will check if the sum is equal to x multiply by size.

 if(sum==x*size) //take same example 1 4 1 sum is 6 == 2(x)*3(size)

if the above condition is false then it is impossible to make all elements of that array equal. If the above condition is true, then we look at D. If D(the mover) is 1, then it is always possible to make all element equal no matter what. So, we will keep looping the array(try to subtract and add from elements) until all elements become x(In others words, all elements become equal). But if D is greater than 1 then we just loop the whole array(try to subtract and add from elements) once. If all the elements become equal then we return the number(answer). Otherwise, we return -1. So, the problem I found in my approach is if D is 1, and we have 10^5 elements in our array

for ex - we have 1 1 1 1 1 … 6 and size = 10^5

we will loop the above array so many times(comparing each element with the adjacent element) until we get all elements equal, and then restart from 0 to length of the array, will end up getting time limit exceed error. Please help me to solve this problem. Please help me with the right approach. I haven’t written the code yet with this approach because I was thinking looping the array so many times will give time limit exceed error. Please help!!

2

Check out my code and read my explanation side by side-

https://www.codechef.com/viewsolution/14775292

There is a general approach which can deal with d=1, and any other value of d (no need to specially consider the case).

Firstly, it must be clear that we have d “starting” points. Eg, in array {1,2,3,4,5} for d=2, we have starting point 1 and 2 from which series/equality must be checked. If we start from 1, we cover {1,3,5} and on starting from 2 we cover {2,4}.

Now, assume we are at an element arr[i]. Is it equal to x? If yes, then good, we proceed to (i+d)th element (read my para at end for better clarification). If no, then how will it get equal to x?

I made the approach simple this way. We are starting from the first element of the series (by series, i mean elements we can cover if we start from that index). If it is equal to x, then good, skip to next one.

If its more than x-

Then this means there must be some element(s) in series which is less than x (if this doesnt hold, then its impossible to equalize the array.) So we do operation and move the excess of values to (i+d)th index. Its just like concept of “carry over”. As we encounter elements less than x, this carry over reduces and reduces. At the last element of series, we can check if carry over is 0 or not. This can be easily seen by checking if last element of series is equal to x or not.

Now, what if its less than x?

We just borrow enough value from arr[i+d] to make arr[i] equal to x. Note that, it doesnt matter if arr[i+d] has enough value to make arr[i]=x or not. If arr[i+d] isnt large enough to make arr[i] x, then also its fine, because now we will have a carry over with negative sign. It will balance out and become 0 as we encounter elements more than x, just like above.

In a gist, the focus of my technique is to start from one direction (either start or end of array), and equalize the ith element. We “borrow” sufficient value from the next element in series so that our ith element is equal to x. Note that, starting from 1 direction and satisfying every index i am coming, has relieved me from checking on both sides of array. For every element at index i, i dont have to look at both i+d and i-d elements. Since my direction is left to right, I only have to check/see the element to right, since all elements to left are satisfying condition (being equal to x).

EDIT: I think its easier if you take an array and give a dry run to my code (meaning see how it works and executes). That will actually clarify much better than I can explain.

1 Like
3

Wow @vijju123 you’re a genius, thank you so much for the help

1 Like
4

@vijju123 can you please explain how (1 1 6 1 1) will work with D = 1? means how it will go left and then right? I’m sorry I’m confused

5

I forgot to add this part-

Can you comment on the complexity of above code? Its O(N) despite nested loops, because each element of array is visited only once. Its not O(ND) as many might have a misconception of. In O(ND), each element of array is visited D times.

6

Comment on my solution? I’m sorry but I’m not familiar with O(N) or O(ND)

7

I was clarifying time complexity of my solution :p.

Np, just google time complexity and get the basics. Its going to help you decide if your algo is quick enough to avoid TLE or not.

8

@vijju123 okay I’ll take a look thank you