Unable to find what's wrong with my code for solve spoj CWC15

Question

I am unable to find what's going wrong in both memotization and tabulation for spoj http://www.spoj.com/problems/CWC2015/.If you could point why both codes are giving respective errors that would be really helpful.

1--Memotization Error--time limit exceeded. Don't know why generated random cases and tested on ideone most of the solutions are coming out in less than a second.

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cstring>
using namespace std;
#define max 20000000

int a[40];
int n;
int m;
long long sum1;
bool dp[40][max];

int solve(long long sum,int x,int k)
{
    if(sum==0)
    {
        if(k==m)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    else if(x==n)
    {
        return false;
    }
    else if(dp[x][sum])
    {
        return dp[x][sum];
    }
    else
    {
        return dp[x][sum]=(solve(sum,x+1,k)||solve(sum-a[x],x+1,k+1));
    }
}


int main()
{
    int t;
    scanf("%d",&t);
    for(int l=1;l<=t;l++)
    {
        scanf("%d",&n);
        m=n/2;
        long long sum=0;
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        printf("Case %d: ",l);
        if(n%2)
        {
            printf("No\n");
            continue;
        }
        if(sum%2)
        {
            printf("No\n");
            continue;
        }
        sum=sum/2;
        if(solve(sum,0,0))
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    return 0;
}

2-tabulation Error-Sigsegv(Segmentation fault) I know segmentation fault can be caused by taking an array of too big a size. But the code works perfectely on ideone.

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cstring>
using namespace std;
#define max 20000000

int a[40];
int n;
long long sum;
bool dp[max+1][41];


bool solve()
{
    int k=0;
    //cout<<"sum is  "<<sum<<endl;
    for (int i = 0; i <= n; i++)
      dp[0][i] = true;
    for (long long i = 1; i <= sum; i++)
      dp[i][0] = false;

     for (long long i = 1; i <= sum; i++)
     {
       for (int j = 1; j <= n; j++)
       {
         dp[i][j] = dp[i][j-1];
         if (i >= a[j-1])
           dp[i][j] = dp[i][j] || dp[i - a[j-1]][j-1];
         if(i==sum && dp[i-a[j-1]][j-1])
         {
           k+=1;
         }
       }
     }

     /*cout<<k<<endl;*/

     return (dp[sum][n] && k==n/2);
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int l=1;l<=t;l++)
    {
        scanf("%d",&n);
        sum=0;
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
        }
        printf("Case %d: ",l);
        if(n%2)
        {
            printf("No\n");
            continue;
        }
        if(sum%2)
        {
            printf("No\n");
            continue;
        }
        sum=sum/2;
        if(solve())
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    return 0;
}

Note-In both programs k is keeping track of number of included elements in the solution so that I can tell whether distribution is equal in terms of number of players or not.If these approaches are wrong a hint towards right direction would be much appreciated.

Answer 1

Suggestion: The way you are solving will not work because of complexity. Although space complexity will work (limit is 1536MB and space used is around 785MB), but time complexity is too high for time limit of 5s. An estimate is 10^8 could be executed safely within 1 sec. If you submit only initialization part of your code, it will exceed time limit(i have done that to verify).

To Solve it: you do not need to travel all sum from 1 to 200 00 000, rather just iterate on generated sum when including ith player.

Lets say 4 players are there with experience 2 3 4 5.

You do not need to travel for sum: 1 to 8, rather do something like this:

Initial sum 0

if you include 1st element: 0 & 2

if you include 2nd element: 0, 2, 3, 4

if you include 3rd element: 0, 2, 3, 4, 6, 7

etc.

Now this way it could upto 2^N. So maintain a map of int of 20000000 and do not put a number in queue, if it is already there. This will solve your problem of iteration 20000000 * 40 to iterating over just unique reachable sum values (complexity will depend of nature of input).

Now if your reach desired sum, then it is reachable. To watch for equal number of players in both teams: i have a hint for you, remember i mention "map of int of 20000000", i said int because this map could be also used to store how many numbers could reach to a particular sum. Use bitwise operator to encode this info. You just need to maintain count and not which particular element is included.

PS: I solved this problem, it took a while and it was fun.