Click here to Skip to main content
15,028,618 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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
Comments
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
Sergey Alexandrovich Kryukov 22-Feb-15 13:14pm
   
I don't have to believe or not: you did not show anything you tried and discuss your problems. There is nothing special in this problem.
—SA
Nikos KLon 22-Feb-15 13:46pm
   
you really believe that I din't make any effort to solve the problem? I just asking for another advice. If you don't want to help me, please don't spam my question. :)
Sergey Alexandrovich Kryukov 22-Feb-15 13:50pm
   
Okay now, did you really read my comment above?
—SA
Nikos KLon 22-Feb-15 15:27pm
   
yes -.-
Andreas Gieriet 22-Feb-15 16:56pm
   
Tell us about your algorithm, e.g. in pseudo code or some prose. No one will read your code - too much. This is *quick* answers forum.
You posted code does not show any useful evidence. Explain what it does in general and why you think it's broken.
This is an optimization task. Requiring linear execution time may not produce an optimal solution, but maybe a good-enough solution.
The simplest solution is to produce all permutations and select the "best" according to your criterions. There may be multiple such solutions. On the other hand, this might not be the smartest way to approach... If it's so little elements, it is certainly a feasible approach.

So, what is your strategy in your algorithm?
Cheers
Andi

1 solution

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
Comments
Maciej Los 23-Feb-15 2:36am
   
+5!
Andreas Gieriet 23-Feb-15 16:16pm
   
Thanks for your 5!
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.
Andreas Gieriet 23-Feb-15 16:31pm
   
My sketch of an algorithm is not polished to the end, but I think you should be able rephrase it in your own words. I won't do more of your home work assignment.
Where do you struggle? E.g. did you take the numbers of your example and play manually through steps 0) to 5)? Which step causes problems?
Note that for some exotic cases, you might have bad results. E.g. a sequence of 1 number to be spread over 3 bins is a bit odd. Or having all 0 is also a degenerated case. Don't let you hold up by these. Start with the common case and treat degenerate cases later if needed at all. This is an *exercise* so that you can learn something *yourself*. Stand on your own feet!
Regards
Andi

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900