Found this interesting problem:
Two integer arrays A and B are given. We need to convert array A to array B using some operation. Operation is defined as follows: Select any element from A decrease its value by 1 and add it to one of the two neighbours.
The array given is circular, meaning the last element can give its value to the first element.
Find the minimum cost to convert array A to array B, where cost id defined as the distance between them, distance between any consecutive element is 1.
Constraints: A,B<=100.
ex: A=[2,3,1,5] B=[2,2,1,6] We need to convert A to B, subtract 1 from index 1 of A i.e. element 3 and give it to 1 making it 2, now he array A is [2,2,2,5]. Now remove 1 from index 2(element 2) and give it to element 5 making it 6, now the array becomes [2,2,1,6], so total cost is 2.
Any suggestion to proceed to this problem.
Come on! Suggest some approach rather than downvoting.
Give some example to explain what you are asking.
yonkoaman Help him bro
itachi0012 plzz help
You can consider every operation as adding or subtracting vector of the form
to array (vector) A to get B. Your task is to find how many times (negative or positive) to add such vectors to A to get B. It can be rewritten with matrices like this:
Move A to the left side, and you can try to solve the linear system, get solution subspace and find minimal integer solution among them.
can u please explain how u r minimizing x1+x2+x3......+xn??
You need to minimize
If a solution exists, it always looks like
for some
you can find those solving the system from my comment above. It means that you need to minimize
This function is convex therefore you can use ternary search to find the minimum.
Sounds very similar to 1237G - Balanced Distribution with $$$K=2$$$.
but i guess there must exist some easy solution for K=2. can u provide one!!
This question should not be that hard as it was asked in a hiring test and the time alloted was also very less.
Yeah, I didn't say that it's hard, just similar. In this case, you're moving $$$1$$$-s one by one, so you can compute the difference $$$A-B$$$, find out from which elements of $$$A$$$ we need to move $$$1$$$-s (positive difference) and to which elements (negative difference), then find out how to move them so that the sum of distances is minimised. That's a standard problem, although kinda annoying due to the circularity.
u just explained problem statement! can u please tell how u r minimizing sum of distances
False.
It's called "minimum cost matching". Look it up, it's a standard algorithm.