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:
I've minimized the
stdin
,stdout
operations by storing the input & output appropriately.I've done proper memoization for
Divisors
andCPStrings
class.As mod operator is said to be expensive so I've performed only when necessary etc.
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;
}