### sarkarasm's blog

By sarkarasm, 2 years ago,

code

The question, in short, is to calculate the number of hamiltonian paths from 1 to n. Here I am storing the nodes present in a path as a subset using binary representation. The dp runs for time O(pow(2,n)*n^2) which should be around 4e8. This approach is giving TLE.

Any help would be appreciated and thanks in advance.

• 0

 » 2 years ago, # |   0 This is what you are looking for
•  » » 2 years ago, # ^ |   0 I have used the same algorithm. However something in my implementation gives TLE.
 » 2 years ago, # |   -6 const int N=20; ll n,m,q,t,u,v,x,y; ll adj[N][N], dp[1<>n>>m; f(m){ cin>>u>>v; u--,v--; adj[u][v]++; } dp[1][0]=1; for(ll i=2;i<(1<>(n-1))&1))continue; f2(n){ if((i&(1<
 » 2 years ago, # |   0 You have “ if(state & (1<
 » 2 years ago, # |   0 my approach worked — though i did top down dpi made one optimisation — if i reach vertex n before rest of the vertices are visited i return 0maybe topdown works because unlike bottom up all states arent calculated in top down?i dont really know a lot though i will include my accepted code MY AC CODE#include using namespace std; #define ll long long #define MOD 1000000007 vectoradj[22]; ll dp[1100000][22]; int n; ll F(int mask, int i) { mask = mask ^ (1 << i); if (mask == 0 && i == n - 1) return 1; if (i == n - 1) return 0; if (dp[mask][i] != - 1) return dp[mask][i]; dp[mask][i] = 0; for (auto j : adj[i]) { if ((mask & (1 << j))) dp[mask][i] = (dp[mask][i] + F(mask, j)) % MOD; } return dp[mask][i]; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int m; cin >> n >> m; for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; a--; b--; adj[a].push_back(b); } memset(dp, -1, sizeof(dp)); cout << F((1 << n) - 1, 0); return 0; } 
•  » » 2 years ago, # ^ |   +1 Thanks. ibit gave me the solution. The bound is pretty tight so you have to remove the redundant cases. The optimization you made of returning 0 when reaching vertex n, actually reduces the runtime by more than half and does the trick. Bottom Up or Top Down does not make any difference.
•  » » » 2 years ago, # ^ |   0 The optimization you made of returning 0 when reaching vertex n, actually reduces the runtime by more than half and does the trick.This is something i encountered the third time in cses problem set (there maybe more i am yet to do all)knights tourgrid pathsall these questions use some kind of wierd optimisation which i cant see mathematically how they affect the runtime but after that optimisation they get AC.
•  » » » » 2 years ago, # ^ |   0 I have not done grid paths, but I did not require any optimization in Knights tour. I just used Warnsdorf's rule.
•  » » » » » 2 years ago, # ^ |   0 oh i was treating Warnsdorf's rule as an optimisation too
•  » » » 2 months ago, # ^ |   0 This optimization worked for me flawlessly, thanks a lot man, AC after banging my head on 10 TLE attempts.