I am required to count the minimum number of moves required such that an array is non-decreasing. In a move, we are able to split a single integer in place (so that when splitting arr[i], they become arr[i] and arr[i 1]) in any way, eg 4 could be split so that it becomes either (1,3) or (2,2). Thereby the length of the array increases by 1 in each move.

For example, consider the array [5, 2, 3]. In our first move, we could split 5 such that our array becomes [3, 2, 2, 3] and in our second move we could split 3, and our array would become [1, 2, 2, 2, 3]. Hence, the minimum number of moves for the array [5, 2, 3] such that the array is non-decreasing is 2.

I've currently come up with this.

def min_moves(x):
    moves = 0
    index = 2
    while index < len(x)   1:
        if x[-index] > x[-index   1]:
            moves  = 1
            split1 = x[-index] // 2
            split2 = x[-index] - split1
            x = x[:-index]   [split1, split2]   x[-index   1:]
 
        else:
            index  = 1
        
    return moves

However, this fails in cases such as when the input is [2, 7, 3]. In the case of my algorithm, the array would become [2, 3, 4, 3] after the first move. However, to find the minimum solution it should be [2, 4, 3, 3] after the first move. Any hints in the right direction would be appreciated. I believe I'm going about the question in slightly the wrong way as I do not need to actually perform the splits; rather I simply need to keep count of the minimum number of splits. A greedy approach seems like the logical route but I'm not really sure how to go about it. Any hints would be appreciated.

CodePudding user response：

Go from the right, and apart from the right-most number, break each number into the smallest number of pieces possible, with the left-most number as large as possible. That means, if the number to the right was broken into pieces and its left-most number was M, then you break the current number into k=ceil(a[i]/M) pieces, and its left-most number is floor(a[i]/k). It's easy to prove that these choices are without loss of generality optimal, because any other valid choice would result in the left-most number being smaller (and hence the remaining problem at least as hard).

For example: 5 2 3:

• 3 is not split, as it is the right-most number
• 2 is split into ceil(2/3) = 1 piece (ie: not split).
• 5 is split into ceil(5/2) = 3 pieces (ie: split twice), and its left-most piece is floor(5/3)=1.

So the total number of splits is 2.

Here's a python solution:

def parts(xs):
    M = xs[-1]
    s = 0
    for i in range(len(xs)-2, -1, -1):
        k = (xs[i]   M - 1) // M
        s  = k - 1
        M = xs[i] // k
    return s

print(parts([5, 2, 3]))
print(parts([2, 7, 3]))

CodePudding user response：

Algorithm

1. If current number is more than next number, divide current by 2. Increment count of moves.

2. Return an array of pairs

   [floor(current number/2), current number - floor(current number/2)]
   

3. Go back to #1 if it is still true otherwise...

4. Return current number

5. Next iteration go back to #1

6. Once array is finished, check if it is in non-decreasing order

7. If not, recursively call function and pass in the array then flatten it when returned

8. Return array when it is non-decreasing order.

function nonDecreasing(array) {
  let result = array.flatMap((num, idx, arr) => {
    let seg;
    // As long as the current number is more than the number ahead of it...
      while (num > arr[idx   1]) {
        // Increment count
        i  ;
        // Get a half of current number
        seg = Math.floor(num / 2);
        // Current number is now half or half 1
        num = num - seg;
        // Return both segment and current number in an array (will be flattened) 
        return [seg, num];
      }
    // Otherwise just return current number
    return num;
  });
  // If array is not in non-decreasing order...
  if (!checkOrder(result)) {
    // Recursively call nonDecreasing() passing in array and flatten when returned
    result = nonDecreasing(result).flat();
  }
  return result;
}

function checkOrder(array) {
  let result = array.flatMap((num, idx, arr) => arr[idx 1] && num <= arr[idx 1] ? [] : !arr[idx 1] ? true : false);
  return result[0];
}

let i = 0;
function nonDecreasing(array) {
  let result = array.flatMap((num, idx, arr) => {
    let seg;
    while (num > arr[idx   1]) {
      i  ;
      seg = Math.floor(num / 2);
      num = num - seg;
      return [seg, num];
    }
    return num;
  });
  if (!checkOrder(result)) {
    result = nonDecreasing(result).flat();
  }
  return result;
}

let A = [5, 2, 3];
console.log(JSON.stringify(nonDecreasing(A)), i);

let B = [8, 1, 5, 4, 6];
console.log(JSON.stringify(nonDecreasing(B)), i);

let C = [2, 7, 3];
console.log(JSON.stringify(nonDecreasing(C)), i);