So I created a program in C to answer the follwoing problem.
Giving a dynamic array, we want to pass the array elements from a file. The first number in the file N gives us the array length. They follow N numbers, the actual elements of the array. Three brothers are going to work in the shop of their father for a time. The shop is doing well and every day generates profit which the three brothers may provide. The brothers agreed that they would divide the total time in three successive parts, not necessarily equal duration, and that each one will be working in the shop during one of these parts and collects the corresponding profit on his behalf. But they want to make a deal fairly, so that one received from three more profit someone else. Specifically, they want to minimize the profit the most favored of the three will receive.
So to answer the question I first created a program that WORKS! with complexity O(n3).
Code:
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int sum_array(int* array, int cnt)
{
int res = 0;
int i;
for ( i = 0; i < cnt ; ++i)
res += array[i];
return res;
}
int main()
{
FILE* input = fopen("share.in","r");
int N = 0;
fscanf(input,"%d",&N);
int *array = (int*)malloc(N * sizeof(int));
for (int i = 0; i < N; i++)
fscanf(input,"%d",&array[i]);
fclose(input);
int Min = 0;
int bestA = 0, bestB = 0, bestMin = INT_MAX;
int A, B;
int i;
for ( A = 0; A < N - 2; ++A)
{
for ( B = A + 1; B < N - 1; ++B)
{
int ProfitA = sum_array(array, A + 1);
int ProfitB = sum_array(array + A + 1, B - A );
int ProfitC = sum_array(array + B + 1, N - 1 - B );
//here the values are "current" - valid
Min = (ProfitA > ProfitB) ? ProfitA : ProfitB;
Min = (ProfitC > Min) ? ProfitC : Min;
if( Min < bestMin )
bestA = A, bestB = B, bestMin = Min;
}
}
printf("%d\n", bestMin);
free(array);
return 0;
}
Then I wanted to reduce the complexity to O(N) using greedy solution. I make the programm but it don't work in every input.
Code:
#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;
}
int *fetch(int *N)
{
FILE* input = fopen("share.in","r");
*N = 0;
fscanf(input,"%d",N);
int *array = malloc(*N * sizeof(int));
if (array != NULL) {
for (int i = 0; i < *N; i++) {
fscanf(input,"%d",&array[i]);
}
}
fclose(input);
return array;
}
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;
int *array = fetch(&N);
printf("%d\n", minmax(array, N));
free(array);
}
Let's assume that we have the follwoing input:
10
1 1 8 1 1 3 4 9 5 2
The ouptur should be 15 -> A = 1 + 1 + 8 + 1 + 1 + 3 = 15 , B = 4 + 9 = 13 , C = 5 + 2 = 7.
But the ouptut is 16!
So I have two questions:
- What is the problem in my second code?
- If you can't help me with the above at least, How can I reduce the complexity of my first working! C code?
Regards,
Nikos
Originally Posted by Nikos KLon
