### sarkarasm's blog

By sarkarasm, 4 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

| Write comment?
 » 4 years ago, # |   0 This is what you are looking for
•  » » 4 years ago, # ^ |   0 I have used the same algorithm. However something in my implementation gives TLE.
 » 4 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<
 » 4 years ago, # |   0 You have “ if(state & (1<
 » 4 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; } 
•  » » 4 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.
•  » » » 4 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.
•  » » » » 4 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.
•  » » » » » 4 years ago, # ^ |   0 oh i was treating Warnsdorf's rule as an optimisation too
•  » » » 12 days ago, # ^ |   0 Yeah you are correct this optimizations reduce the runtime by half. I have a bottom up soln . bottom up AC code int n,m; cin>>n>>m; vector> g(n+1); forn(0,m,i){ int a,b; cin>>a>>b; g[a].pb(b); } int mod=1e9+7; int a=1LL<> dp(n+1,vector(a,0)); dp[n][0]=1; forn(1LL<<(n-1),a-1,i){ // skipping iterations for 1 to 2^(n-1) -1, which reduces iterations by 2 forn(1,n+1,j){ if((i&(1LL<<(j-1)))==0){ for(int x:g[j]){ if(i&(1LL<<(x-1))){ int temp=i^(1LL<<(x-1)); dp[j][i]=(dp[j][i] + dp[x][temp])%mod; } } } } } cout<
•  » » 3 weeks ago, # ^ |   0 i had a similar approach , but mu states were inverted and it gave me tle . But when i had the states like yours it got accepted , why is so ? I have heard its better to choose the states with lower no first , why it fails here ?
•  » » » 2 weeks ago, # ^ |   0 god knows bro i also faced the same thing