JARJAR challenge on SPOJ

Question

I tried this problem and I saw that my solutions was way too slow compared to others. I want to know how I can improve time complexity.

A job has been assigned to Jar Jar Binks, it goes as follows: There are N spaceships parts, each with a weight of Wi kg. Given a weight W, he has to show how many parts can be used in order to make a ship with a weight of exactly W kg. He has to show all possible solutions, of course if possible. Everybody knows Jar Jar Binks particularly because of his clumsiness, so you have to help him. Write a program that solves his problem!

Input

There will be several cases, each beginning with two integers N, Q (1<=N<=60, 0<=Q<=10000). Next there will be N positive integers representing the weights of the N spaceship parts (1<=Wi<=1000). Q lines will follow, each one with only one integer W, the total weight of the spaceship. End of input will be denoted with N = 0 and Q = 0. This case should not be processed

Output

Print a line with K integers per query in ascending order. They must represent the amount of pieces that can be used to make a spaceship with weight W. If there is no way to make a spaceship with weight W, output a line with the string “That's impossible!” (quotes to clarify)

#include <bits/stdc++.h> // I don't think this would have any impact on run-time , right?

using namespace std;

#define pb push_back 

#define FOR(i,a,b) for(int i=a;i<=b;++i)

int a[60]; 
int dp[61][61][60001]; // dp[number of weights considered][no. of weights selected from earlier][if this sum is possible]
int main() 
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); // for speed improvement

    int n,q;

    while(1)
    {
        cin>>n>>q;

        if(n==0&&q==0)break;

        int sum=0;
        FOR(i,1,n){cin>>a[i];sum+=a[i];}

        memset(dp,0,sizeof(dp));

        dp[0][0][0]=1;
        // I know that a 3d array is not needed but this would affect only memory, right?
        FOR(i,1,n)
        {
            dp[i][0][0]=1;
            FOR(j,1,i)
            {
                FOR(k,0,sum)
                {
                    if(k>=a[i])
                    dp[i][j][k]=dp[i-1][j-1][k-a[i]]; // typical dp. either a[i] is taken into account

                    dp[i][j][k]|=dp[i-1][j][k];       // or it is not
                }
            }
        }

        while(q--)    // handling queries
        {
            int x;
            cin>>x;
            vector<int> v;   // we will store answers here

            if(x>=1&&x<=sum) 
            {
                FOR(j,1,n)
                if(dp[n][j][x])v.pb(j);

                if(v.empty())cout<<"That's impossible!";

                else for(auto it :v)cout<<it<<" ";

                cout<<"\n";
            }

            else cout<<"That's impossible!\n";
        }
    }
    return 0;
}

Answer 1

At first glance:

The code is a bit difficult to read. The macros and variable names do not improve readability (using the same names than the problem would help a lot). If I understand correctly (and I'm honestly not sure) you compute all possible solutions, then use this huge table on the input. This would be a good idea if the result set was small and the number of 'Q' benefiting from it (much) bigger. (I'd say the order of 10E+7 'Q', give or take an order of magnitude)

A bit deeper:

The sum of weights as a quick elimination is a good idea.

But your algorithm involves this brutal O(m * n²) loop. This does not inspire confidence in the execution speed. Also, your main buffer takes 850MB of memory (assuming an int is 32 bits). That's a LOT of cache misses : another downer.

The way I imagine the algorithm, only 2 arrays of 60 integers are needed (plus bonuses). That's 240 bytes or ~4 to ~8 lines of L0 cache : fast. As for the work for a given total weight, it should be broadly O(n*log(n))

Reading the problem, a few obvious algorithm optimization steps are presenting themselves.

First, there is no precision that say that pieces weights are different (and if the test is interesting, there should be a fair amount of pieces with identical weights in the input, if only to make room for subtlety).

The weight pieces should be sorted in reverse order and the number of different weights counted. Note that by starting with the bigger values on each iteration, the test of overflow you will do after each addition will trigger earlier.

Now that you know how many times a weight is used, you only start from it once and multiply the amount of solutions for that starting weight by U. (Repeat for all different weights)

There is also no precision that the total weight cannot be repeated. I'm assuming that's what your O³ was meant for. But instead of computing what you don't need, just store the results by total weight in a map (that you will reset for each new set of pieces weights).

And at last, since it's C++11. You could take advantage of the amount of CPUs and dispatch the test. This part is actually tricky because knowing if you have to divide by (N+Qs) (and have a printer dispatch, the main thread, that centralizes the printing to keep order) or to divide for each Q of an N requires a bit of experiment and tuning.

An example to be clear, with [] being a thread.

[N0 Q01 Q02 Q03 ...] [N1 Q10 ...] per thread, plus [printer dispatch].

or

[N0 Q00] [N0 Q01] [N0 Q02] [N0 Q03] [N1 Q10], plus [printer dispatch].

These are the first ideas but the result should be quite fast.