patterncppMinor
Mathematical programming puzzles
Viewed 0 times
puzzlesprogrammingmathematical
Problem
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
-
I've done proper memoization for
-
As mod operator is said to be expensive so I've performed only when necessary etc.
-
The function
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
```
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAX 1000000007
long long int NChooseK_Sum(int N, int K){
vector prevV, V;
prevV.push_back(1); prevV.push_back(1);
for(int i=2;i 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= MAX)
res %= MAX;
}
return res;
}
class Divisors{
map >M;
public:
vector GetDivisors(int N){
map >::iterator mit = M.find(N);
if(mit != M.end())
return mit->se
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 and CPStrings 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 > could be expensive but I can't find any easier alternative of it.```
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define MAX 1000000007
long long int NChooseK_Sum(int N, int K){
vector prevV, V;
prevV.push_back(1); prevV.push_back(1);
for(int i=2;i 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= MAX)
res %= MAX;
}
return res;
}
class Divisors{
map >M;
public:
vector GetDivisors(int N){
map >::iterator mit = M.find(N);
if(mit != M.end())
return mit->se
Solution
-
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
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.
-
Some low-hanging fruit in the CountPeriodicStrings code:
Instead of testing
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.
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.
-
Some low-hanging fruit in the CountPeriodicStrings code:
Instead of testing
(edits_left
-
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.
Code Snippets
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);Context
StackExchange Code Review Q#9293, answer score: 2
Revisions (0)
No revisions yet.