无法找到我的代码解决spoj CWC15的错误

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.

我无法在memj http://www.spoj.com/problems/CWC2015/的memotization和制表中找到出错的地方。如果你能指出为什么两个代码都给出了真正有用的错误。

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.

1 - 记忆错误 - 超出时间限制。不知道为什么生成随机案例并在ideone上测试大多数解决方案都在不到一秒的时间内推出。

#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.

2-tableulation Error-Sigsegv(分段错误)我知道分段错误可能是由于一个太大的数组引起的。但是代码完全适用于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.

注意 - 在两个程序中,k都跟踪解决方案中包含的元素的数量,以便我可以判断分配在玩家数量方面是否相等。如果这些方法是错误的,那么向正确方向的提示将非常受欢迎。

1 个解决方案

#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).

建议:由于复杂性,您解决的方式无效。虽然空间复杂度可行(限制为1536MB,使用的空间约为785MB),但时间复杂度对于5s的时间限制来说太高了。可以在1秒内安全地执行估计10 ^ 8。如果您只提交代码的初始化部分,它将超过时间限制(我已经完成了验证)。

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.

要解决它:你不需要从1到200 00 000之间的所有总和,而只是在包含ith玩家时迭代生成的总和。

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

让我们说有4名球员有经验2 3 4 5。

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

你不需要旅行总和:1到8,而是做这样的事情:

Initial sum 0

初始总和0

if you include 1st element: 0 & 2

如果你包含第一个元素:0和2

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

如果你包括第二个元素:0,2,3,4

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

如果你包括第3个元素: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).

现在这种方式可以达到2 ^ N.因此,维护一个20000000的int映射,如果已存在,则不要将数字放入队列中。这将解决您的迭代问题20000000 * 40,以迭代唯一可达的和值(复杂性将取决于输入的性质)。

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.

现在,如果您达到所需的总和,那么它是可达的。要观察两队中相同数量的球员:我有一个暗示你,记得我提到“20000000的int地图”,我说int因为这张地图也可以用来存储多少数字可以达到一个特定的总和。使用按位运算符对此信息进行编码。您只需要维护计数,而不是包含哪个特定元素。

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

PS:我解决了这个问题,花了一段时间,很有趣。

#1