Sudhanshu_Kumar's blog

convert one array to another
By Sudhanshu_Kumar, history, 5 years ago, In English

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.

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Come on! Suggest some approach rather than downvoting.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Give some example to explain what you are asking.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

yonkoaman Help him bro

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

You can consider every operation as adding or subtracting vector of the form

$$$ (0, \dots, 0, 1, -1, 0, \dots, 0) $$$

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:

$$$ A + \begin{bmatrix} 1 & -1 & 0 & 0 & \dots & 0 \\ 0 & 1 & -1 & 0 & \dots & 0 \\ \vdots \\ -1 & 0 & 0 & \dots & 0 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} = B $$$

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u please explain how u r minimizing x1+x2+x3......+xn??

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You need to minimize

      $$$ |x_1| + |x_2| + \dots + |x_n| $$$

      If a solution exists, it always looks like

      $$$ (c_1 + x_n, c_2 + x_n, \dots, c_{n-1} + x_n, x_n) $$$

      for some

      $$$ c_1, \dots, c_{n-1} $$$

      you can find those solving the system from my comment above. It means that you need to minimize

      $$$ |x_n + c_1| + |x_n + c_2| + \dots + |x_n + c_{n-1}| + |x_n| $$$

      This function is convex therefore you can use ternary search to find the minimum.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sounds very similar to 1237G - Balanced Distribution with $$$K=2$$$.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but i guess there must exist some easy solution for K=2. can u provide one!!

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This question should not be that hard as it was asked in a hiring test and the time alloted was also very less.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        u just explained problem statement! can u please tell how u r minimizing sum of distances

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          u just explained problem statement!

          False.

          can u please tell how u r minimizing sum of distances

          It's called "minimum cost matching". Look it up, it's a standard algorithm.

          → Reply