TEAMSEL: Getting wa

general
, ,
1

http://www.codechef.com/problems/TEAMSEL/

Please tell me why am I getting wrong answer.
I have used Dynamic Programming.

#include<stdio.h>
#include<stdlib.h>

int max(int a, int b);

int main()
{
    int numberOfTestCases;
    scanf("%d", &numberOfTestCases);
    int val;
    long sum;
    for(;numberOfTestCases>0;numberOfTestCases--)
    {
        int N;
        scanf("%d", &N);
        int i, j;
        int Numbers[N];
        sum = 0;
        for(i=0;i<N;i++)
        {
            scanf("%d", &Numbers[i]);
            sum = sum + Numbers[i];
        }

        int ** Array1;
        int ** Array2;
        val = 0;
        int val0 = N/2;
        int val1 = val0 + 1;
        Array1 = (int **)malloc(sizeof(int *) * N);
        Array2 = (int **)malloc(sizeof(int *) * N);
        for(i=0;i<N;i++)
        {
            Array1[i] = (int *)calloc((sum/2) + 1, sizeof(int));
            Array2[i] = (int *)calloc((sum/2) + 1, sizeof(int));
        }
        if(Numbers[N-1] < (sum/2))
        {
            Array1[N-1][Numbers[N-1]] = 1;
            Array2[N-1][Numbers[N-1]] = 1;
        }

        for(i=N-2;i>=0;i--)
        {
            for(j=0; j<=(sum/2); j++)
            {
                if(j==Numbers[i])
                {
                    Array1[i][j] = 1;
                }
                else
                {
                    if( j-Numbers[i] >=0 && Array2[i+1][j-Numbers[i]] != 0)
                    {
                        Array1[i][j] = Array2[i+1][j-Numbers[i]] + 1;
                    }
                }
                Array2[i][j] = max( Array1[i][j], Array2[i+1][j]);

                if((Array1[i][j] == val0 || Array1[i][j] == val1) && N%2 == 1 )
                {
                    if(j > val)
                        val = j;
                }
                else if(Array1[i][j] == val0 && N%2 == 0 )
                {
                    if(j > val)
                        val = j;
                }
            }
        }
        if(numberOfTestCases != 1)
            printf("%d %ld\n\n", val, sum - val);
        for(i=0;i<N;i++)
        {
            free(Array1[i]);
            free(Array2[i]);
        }
        free(Array1);
        free(Array2);
    }
    printf("%d %ld", val, sum - val);
    return 0;
}

int max(int a, int b)
{
    return a>b ? a:b;
}
2

describe your approach…

3

I’m using two arrays of dimensions N x (SUM/2 + 1). The idea is if the list is to be divided in two sub lists with respective total sum as sum1 and sum2, then either sum1 or sum2 will be less than or equal to half of the total sum of the complete list (SUM/2).
Find the total sum of list with smaller sum. Take a small example and draw the arrays and you will understand. You can check for input
1

3
1
1
2