the great pile up

Question

There are several piles of cards on the table arranged from left to right. All of them do not contain the same number of cards. As the boss insists on symmetry, Ramu is asked to merge the minimum number of adjacent piles so that if a list of the number of cards in each pile is given in left to right order, the list reads the same whether it is read in the left to right order or the right to left order.

For example, if the piles of cards initially were 1 2 2 5 1 3 1 1, there can be three merges (2,2), (5,1) and (3,1) to give 1 4 6 4 1.
Note that merging 3 numbers, say (1,2,2) is counted as 2 merges, one between (1 2) and the next between the resulting 3 and the next two. Hence another solution (1,2,2) (5,1) (3,1,1) resulting in 5 6 5 takes 2 + 2 + 1 or 5 merges, and is not minimal.

Another (trivial) solution is to merge all the piles to give 16. This may be the only solution in some cases, and shows that all initial sets have at least one (not necessarily minimal) solution

 

 

Answer 1

Idea

You want the final list to be a palindrome, using the minimum number of merges of adjacent piles.

At any moment compare:

1. left pile sum
2. right pile sum

Rules

1. If left == right, move both pointers inward (no merge needed)
2. If left < right, merge left pile with the next pile to the right (one merge)
3. If left > right, merge right pile with the previous pile to the left (one merge)

Why this works:

1. To make a palindrome, the two ends must eventually match
2. If one side is smaller, the only way to possibly match the other side is to grow that smaller side by merging inward
3. Greedy is optimal here

C Solution

#include <stdio.h>

int minMergesToPalindrome(int a[], int n) {

int i = 0, j = n - 1;

int merges = 0;

while (i < j) {

if (a[i] == a[j]) {

i++;

j--;

} else if (a[i] < a[j]) {

// Merge a[i] with a[i+1]

a[i + 1] = a[i] + a[i + 1];

i++;

merges++;

} else {

// Merge a[j] with a[j-1]

a[j - 1] = a[j] + a[j - 1];

j--;

merges++;

}

}

return merges;

}

int main() {

int n;

scanf("%d", &n);

int a[1000];

for (int i = 0; i < n; i++) {

scanf("%d", &a[i]);

}

int result = minMergesToPalindrome(a, n);

printf("%d\n", result);

return 0;

}

Example

Input:

8

1 2 2 5 1 3 1 1

Output:

3

Time Complexity

1. O(n)
2. Each pointer moves inward, and each merge reduces the active number of piles.

Space Complexity

1. O(1) extra space (in place)