15,907,001 members
See more:
We have given a list of N numbers.

We then create 3 partitions A, B and C (thse can be just integers). We want to store the numbers in the three partitions in such way that the partition with the biggest sum to have the least minimum difference from the second and the third sum. So we want to store the numbers in that way so the sum of all partitions to be as close as possible between each other. The way we should store the numbers is linear. By that I mean every sum should have numbers that are one-next-to-the-other sequence. I don't know if you understand me so if someone has, please edit my question properly.

I will provide an example bellow to show you how.

Let's say we have the following numbers : 8 5 4 3 2 1 3

The best solution is :

C
```A = 8
B = 5 + 4 = 9
C = 3 + 2 + 1 + 3 = 9
```

I wanted to create a linear complexity solution of the problem but I don't know how. I created a O(n^2) solution but I wanted to sure if there is better solution. maybe logarythmic. I wan't upload my code just not to confuse you guys. If you want then I will.

The solution I want can be provided in C or just in an algorithm!

This is my view which is false and in no way you should base in that logic. I test many testcases to say that!

C#
```#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int sum_array(const int* array, int cnt)
{
int res;
for ( res = 0; cnt; --cnt)
res += *array++;
return res;
}

struct Partition {
const int *begin;
const int *end;
int sum;
};

int indexOfMax(const struct Partition *p, int partcount)
{
int i, maxIndex;
for (i = maxIndex = 0; i < partcount; ++i) {
if (p[i].sum > p[maxIndex].sum)
maxIndex = i;
}
return maxIndex;
}

// give a number to the partition to the right of t if possible
// and return the max of the two adjusted sums
int giveRight(struct Partition *p, int partcount, int t)
{
if (t >= partcount || t < 0)
return INT_MAX;
// only adjust if there is a right partition and we have more than one element
if (t+1 >= partcount || (p[t].end - p[t].begin == 1))
return p[t].sum;
p[t+1].begin = --p[t].end;
// n is the number we're moving
int n = *p[t+1].begin;
p[t].sum -= n;
p[t+1].sum += n;
if (p[t].sum > p[t+1].sum)
return p[t].sum;
return p[t+1].sum;
}

// give a number to the partition to the left of t if possible
// and return the new sum
int giveLeft(struct Partition *p, int partcount, int t)
{
if (t >= partcount || t < 0)
return INT_MAX;
// only adjust if there is a left partition and we have more than one element
if (t-1 < 0 || (p[t].end - p[t].begin == 1))
return p[t].sum;
// n is the number we're moving
int n = *p[t].begin;
p[t-1].end = ++p[t].begin;
p[t].sum -= n;
p[t-1].sum += n;
if (p[t].sum > p[t-1].sum)
return p[t].sum;
return p[t-1].sum;
}
#define PART_COUNT 3

int minmax(const int *array, int N)
{
const int sum = sum_array(array, N);
struct Partition p[PART_COUNT] = {
{&array[0], &array[1], array[0]},
{&array[1], &array[2], array[1]},
{&array[2], &array[N], sum - array[0] - array[1]}
};
int max, maxIndex, test;
do {
maxIndex = indexOfMax(p, PART_COUNT);
max = p[maxIndex].sum;
test = giveLeft(p, PART_COUNT, maxIndex);
if (test >= max) {
// not improved, but try one more
giveLeft(p, PART_COUNT, maxIndex-1);
test = p[indexOfMax(p, PART_COUNT)].sum;
if (test >= max) {
// not improved so reverse this move
giveRight(p, PART_COUNT, maxIndex-2);
giveRight(p, PART_COUNT, maxIndex-1);
// and try the right
test = giveRight(p, PART_COUNT, maxIndex);
if (test >= max) {
// not improved but try one more
giveRight(p, PART_COUNT, maxIndex+1);
test = p[indexOfMax(p, PART_COUNT)].sum;
if (test >= max) {
// not improved, so reverse this move
giveLeft(p, PART_COUNT, maxIndex+2);
giveLeft(p, PART_COUNT, maxIndex+1);
}
}
}
}
} while (test < max);
return max;
}

int main()
{
int N = 0;
FILE* input = fopen("share.in","r");

fscanf(input,"%d",&N);

int *array = malloc(N * sizeof(int));
if (array != NULL) {
for (int i = 0; i < N; i++) {
fscanf(input,"%i",&array[i]);
}
}
fclose(input);

printf("%d\n", minmax(array, N));
free(array);
}```
Posted
Updated 22-Feb-15 6:04am
v2
Kornfeld Eliyahu Peter 22-Feb-15 9:54am
According what you are saying the order of the original list can not be changed...
So the outcome for your list - '8 5 4 3 2 1 3' is not the same as of the list '8 3 2 5 4 3 1'...(it is 8, 10, 8)
Why the order is a must have?
Sergey Alexandrovich Kryukov 22-Feb-15 10:27am
What have you tried so far?
—SA
Nikos KLon 22-Feb-15 11:58am
ok the order of the numbers must not change! It's a MUST restrictions given from the exercise! I tried two codes. One with complexity O(n^2) which is worked and one with linear complexity which is not. I will post the linear but I don't want to use that logic cause is false. -Believe me I tried many tastcases!-
Kornfeld Eliyahu Peter 22-Feb-15 12:30pm
So let imagine an input of 8 1 100 5 4 3 2 1 - there is a acceptable solution for that?
Nikos KLon 22-Feb-15 12:47pm
yes the number 100. All numbers are type of int and the sum of all numbers isn't greater than 1.000.000.000

## Solution 1

A possible approach (which is not necessarily optimal - this would require a deeper analysis) is to calculate the average of the remaining numbers for spreading over the remaining bins and fill each bin in sequence until adding is worse than not adding for the current bin - then go to the next bin.
E.g.
```0) Calculate the average of the remaining numbers and the remaining bins.
1) If the current bin is empty, add the first of the remaining numbers to the current bin.
2) Try to add the next remaining number to the current bin.
2.1) If adding is increasing the distance to the average, reject adding and go to 3).
2.2) Else, add the number and go to 2).
3) If current bin is not last bin, move to the next bin and go to 0).
4) Else, add the remaining numbers to the current bin.
5) Done.```
Cheers
Andi
PS: To stay in the integer number domain, you can work on the sum of the remaining numbers and probe adding by multiplying by the number of remaining (plus current bin) and then compare that number against not adding the number.
E.g.
```S  = 8 5 4 3 2 1 3
N  = 3

S0 = 26 (8+5+4+3+2+1+3)
B0 = 8       -> Delta = Abs(B0*N - S0) = 2
B0 = 8+5     -> Delta = Abs(B0*N - S0) = 13 -> reject
B0 = 8

N--
S1 = S0-B0 = 18 (5+4+3+2+1+3)
B1 = 5       -> Delta = Abs(B1*N - S1) = 8
B1 = 5+4     -> Delta = Abs(B1*N - S1) = 0
B1 = 5+4+3   -> Delta = Abs(B1*N - S1) = 6 -> reject
B1 = 5+4

N--
S2 = S1-B1 = 9 (3+2+1+3)
B2 = 3       -> Delta = Abs(B2*N - S2) = 6
B2 = 3+2     -> Delta = Abs(B2*N - S2) = 4
B2 = 3+2+1   -> Delta = Abs(B2*N - S2) = 3
B2 = 3+2+1+3 -> Delta = Abs(B2*N - S2) = 0
B2 = 3+2+1+3```

v2
Maciej Los 23-Feb-15 2:36am
+5!
Andreas Gieriet 23-Feb-15 16:16pm
Cheers
Andi
Nikos KLon 23-Feb-15 7:31am
I created your aproach before and didn't work. Lets assume in B0 after the worst case we have a better one. How do I know that? If the procedure break only by finding only one worst case then we have the above problem. How can we manage that?
Andreas Gieriet 23-Feb-15 16:17pm
"[...] didn't work [...]" is not leading anywhere. Try to express more precisely what the problem is. With "didn't work", no one can help you.
Andi
PS: I understand that you cannot rearrange the sequence to be put into N bins. So, adding a new number leads to a better or worse result compared to the average (which was the ideal splitting if that was possible). E.g. average = 17, the current bin has say the sum 15, the next number to try to add is 5, would you add 5 (over shot by 3) or not add (under shot by 2)?
Nikos KLon 23-Feb-15 9:05am
Ι think I didn't undesratnd your points. Can you make an algorythm base structure so I can have the hole idea? Then I can safely accept your answer.