Mathematical programming puzzles

Question

This is a solution I wrote for a programming puzzle which I believe and I'm sure is correct, but for two of their test cases the online judge gives me 'Time Limit Exceeded' only by a few 100ms! I've tried a lot to knock those few ms out, but no luck.

For a time limit of 3s I've submitted solutions which ran in 3.13127s, 3.2901s, 3.02861s. (personally, I find it annoying how a fraction of sec is keeping my solution from getting accepted)

Here's so far what I've paid attention to:

1. I've minimized the stdin, stdout operations by storing the input & output appropriately.

2. I've done proper memoization for Divisors and CPStrings class.

3. As mod operator is said to be expensive so I've performed only when necessary etc.

4. The function NChooseK_Sum sums up the Binomial coefficients of \$N\$ up to \$K\$, using Pascal's triangle approach \$O(N^2)\$. I wrote a \$O(KlogK)\$ solution but surprisingly it only went on to increase the run time on submission! (I've attached both functions) As far as logic of solution is concerned I'm sure this is pretty much it. It is a simple dynamic programming problem, requires divisors and some hamming distance calculations.

Help me review this code and point out the expensive lines/ideas in it. I think using map<int, vector<int> > could be expensive but I can't find any easier alternative of it.

#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<map>
#include<string>
#include<cstring>
#include<vector>
using namespace std;
#define MAX 1000000007
long long int NChooseK_Sum(int N, int K){
    vector<long long int> prevV, V;
    prevV.push_back(1);     prevV.push_back(1);
    for(int i=2;i<=N;++i){
        V.push_back(1);
        for(int j=0;j<(i-1);++j){
            long long int val = prevV[j] + prevV[j+1];
            if(val > MAX)
                val %= MAX;
            V.push_back(val);
        }
        V.push_back(1);
        prevV = V;
        V.clear();
    }
    long long int res=0;
    for(int i=0;i<=K;++i){
        res+=prevV[i];
        if(res >= MAX)
            res %= MAX;
    }
    return res;
}
class Divisors{
    map<int, vector<int> >M;
    public:
    vector<int> GetDivisors(int N){
        map<int, vector<int> >::iterator mit = M.find(N);
        if(mit != M.end())
            return mit->second;
        else{
            vector<int> V;
            int L = sqrt(N)+1;
            for(int i=1;i<L;++i)
                if( !(N%i) ){
                    V.push_back(i);
                    if(i != N/i)
                        V.push_back(N/i);
                }
            sort(V.begin(), V.end());
            M.insert(pair<int, vector<int> > (N, V) );
            return V;
        }
    }
};

class CPStrings{
    long long int cache[1000][1000];
    public:
    CPStrings(){
        memset(cache, -1, sizeof(long long int)*1000*1000);
    }
    long long int CountPeriodicStrings(vector<string> &V, int edits_left, int idx){
        if(idx == -1 && edits_left >=0)
            return 1;
        if(edits_left<0)
            return 0;
        if(cache[edits_left][idx] != -1)
            return cache[edits_left][idx];
        long long int ret = 0;
        char alphabet[2] = {'0','1'};
        for(int ch = 0; ch<2; ++ch){
            int edits_used = 0;
            vector<string>::iterator sit;
            for(sit=V.begin(); sit!=V.end(); ++sit)
                if((*sit)[idx] != alphabet[ch])
                    ++edits_used;
            ret += CountPeriodicStrings(V, edits_left-edits_used, idx-1);
        }
        if(ret >= MAX)
            ret %= MAX;
        cache[edits_left][idx] = ret;
        return ret;
    }
};
void BreakString(const string &s, int size, vector<string> &Res){
    int len = s.length();
    for(int i=0;i<len; i+=size)
        Res.push_back(s.substr(i, size));
}
class Problem{
    int _T;
    int *_N, *_K;
    map<int, string> Probs;
    public:
    Problem(){
        cin >> _T;
        _N = new int[_T];
        _K = new int[_T];
    }
    ~Problem(){
        delete []_N;
        delete []_K;
    }
    void ReadProblem(){
        for(int i=0;i<_T;++i){
            cin >> _N[i] >> _K[i];
            string s;
            cin >> s;
            Probs.insert(pair<int, string>(i, s) );
        }
        return;
    }
    void Solve(vector<long long int> &Result){
        Divisors D;
        for(int t=0; t<_T; ++t){
            int N=_N[t], K=_K[t];
            map<int, string>::iterator mit = Probs.find(t);
            string s = mit->second;
            long long int totalStrings = 0;
            //Total possible stringsCount = NC0+NC1+NC2+...+NCK
            totalStrings = NChooseK_Sum(N, K);
            //Periodic strings' period  will be of length (p=) 1,2,...(divisors of L)
            vector<int> divisors = D.GetDivisors(N);
            long long int periodicStringCount = 0;
            map<int, long long int> M; // Map M contains the divisor(d): #periodicstrings with period =d.
            for(int i=0; i<divisors.size()-1; ++i){//For all Periods calculate the possible periodic strings that could be formed...
                CPStrings CPS;
                int divisor = divisors[i];
                vector<string> subStrings;
                BreakString(s, divisor, subStrings);
                long long int periodicStringCount_withRep = CPS.CountPeriodicStrings(subStrings ,K, divisor-1);
                if(periodicStringCount_withRep){
                    vector<int> divs = D.GetDivisors(divisor);
                    for(vector<int>::iterator vit=divs.begin();vit!=divs.end()-1; ++vit){//Remove the repetaed patterns formed by the divisors of current Period.
                        map<int, long long int>::iterator mit = M.find(*vit);
                        if(mit != M.end())
                            periodicStringCount_withRep -= mit->second;
                    }
                }
                while(periodicStringCount_withRep < 0)
                    periodicStringCount_withRep += MAX;
                M.insert(pair<int, long long int>(divisor, periodicStringCount_withRep));
                periodicStringCount += periodicStringCount_withRep;
            }
            if(periodicStringCount >= MAX)
                periodicStringCount %= MAX;
            long long int result = totalStrings - periodicStringCount;
            while(result < 0)
                result += MAX;
            Result.push_back(result);
        }
        return;
    }
};
int main(){
    Problem P;
    P.ReadProblem();
    vector<long long int> Result;
    P.Solve(Result);
    for(int i=0;i<Result.size(); ++i)
        cout << Result[i] << endl;
    return 0;
}

#define 1000000007 MAX
void ExtendedEucledian(long long int a, long long int b, long long int& gcd, long long int& x, long long int& y){
        x=0, y=1;
        long long int u=1, v=0, m, n, q, r;
        gcd = b;
        while (a!=0) {
                q=gcd/a; r=gcd%a;
                m=x-u*q; n=y-v*q;
                gcd=a; a=r; x=u; y=v; u=m; v=n;
        }
}
long long int NChooseK_Sum1(int N, int K){
        long long int val = 1, sum = 1;
        for(int k=0;k<K;++k){
                long long int gcd, moduloInverse, y;
                ExtendedEucledian(k+1, MAX, gcd, moduloInverse, y);
                if(moduloInverse<0)
                        moduloInverse += MAX;
                val = val * (N-k);
                if(val >= MAX)
                        val %= MAX;
                val *= moduloInverse;
                if(val >= MAX)
                        val %= MAX;
                sum += val;
                if(sum >= MAX){
                        sum %= MAX;
                }
        }
        return sum;
}

Answer 1

1. Some low-hanging fruit in the NChooseK_Sum code:

   Initialize two vectors up-front to a full allocation of N elements to avoid resizing overhead.

   Don't call clear -- instead, just use V[0] = 1; V[j] = ...; V[i] = 1; instead of V.push_back.

   Also, you could avoid the vector-to-vector copying by defining V and prevV as pointers to vectors and swapping the two pointers at the bottom of the loop. (The vectors could STILL be stack-based if you care, just give them other names like vecA and vecB and take their addresses to set the pointers.

2. Some low-hanging fruit in the CountPeriodicStrings code:

   Instead of testing (edits_left<0) (effectively twice!?) inside every call, save function call overhead by skipping the recursive call in the equivalent case (edits_left<edits_used).

   Since V doesn't change for the duration of a the recursive call and needn't change over the lifetime of the CPStrings object, save some argument passing by making it a data member.

   You could also save iterator overhead by pulling the vector iterator loop out of the for(int ch... loop so it only gets called once. That requires calculating two different edits_used values in parallel, one per {'0','1'}. I'd probably eliminate the for(int ch... loop for edits_used calculation purposes, especially since '0' and '1' are mutually exclusive, and save the looping for the recursive call like this:

   long long int ret = 0;
   int edits_used[] = {0,0};
   for(vector<string>::iterator sit=V.begin(); sit!=V.end(); ++sit) {
       switch ((*sit)[idx]) {
       case '0':
           ++(edits_used[0]);
           break;
       case '1':
           ++(edits_used[1]);
           break;
       default:
           break;
       }
   }
   for(int ch = 0; ch<2; ++ch)
       if(edits_left>=edits_used[ch])
           ret += CountPeriodicStrings(V, edits_left-edits_used[ch], idx-1);
   

3. There are a number of for loops over vectors that use size() and integer indexing rather than iterators. I'm not sure how this effects performance, but it's not as readable.

It's hard to tell without profiling whether these changes are addressing actual pain points, but they're what jumped out. They may give the slight edge you are seeking.