Help needed in CSES graph question Hamiltonian Flights

sarkarasm's blog

By sarkarasm, 4 years ago, In English

Link to question: link

code

        cin>>n>>m;
 
        vector<vll> rev(n,vll(n,0));
        rep(i,m)
        {
            cin>>l>>r;
            l--;r--;
            rev[r][l]++;
        }
 
        vector<vll> dp(n,vll(1<<n,0));
        dp[0][1]=1;
 
        rep(state,(1<<n))
        {
            rep(curr,n)
            {
                if(state & (1<<curr))
                {
                    rep(ch,n)
                    {
                        if(state & (1<<curr))
                        {
                        dp[curr][state]+=(dp[ch][state^(1<<curr)]*rev[curr][ch]);
                        dp[curr][state]%=MOD;
                        }
                        
                    }
                }
            }
                
        }
 
        out(dp[n-1][(1<<n)-1]);

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.

#graph, #cses, #hamiltonian-path

sarkarasm
4 years ago
10

Comments (9)

Show archived | Write comment?

kingmanas

4 years ago, # |

This is what you are looking for

→ Reply

sarkarasm

4 years ago, # ^ |

I have used the same algorithm. However something in my implementation gives TLE.

→ Reply

ibit

4 years ago, # |

-6

const int N=20; ll n,m,q,t,u,v,x,y; ll adj[N][N], dp[1<<N][N]; class Execute{ public: int solve(){

cin>>n>>m;
    f(m){
        cin>>u>>v;
        u--,v--;
        adj[u][v]++;
    }
    dp[1][0]=1;
    for(ll i=2;i<(1<<n);i++){
        // if(i==(1<<n)-1)continue;
        // if(i&(1<<(n)))continue;
        if(i!=(1<<n)-1&&((i>>(n-1))&1))continue;
        f2(n){
            if((i&(1<<j))){
                ll ntr=i^(1<<j);
                for(ll k=0;k<n;k++){
                    if((ntr&(1<<k))&&(adj[k][j])){
                        // dp[i][j]+=dp[ntr][k];
                        dp[i][j]+=adj[k][j]*dp[ntr][k];
                        dp[i][j]%=mod;
                    }
                }
            }
        }
    }
    // f((1<<n)){
    //     f2(n){
    //         cout<<dp[i][j]<<" ";
    //     }pn
    // }
    p(dp[(1<<n)-1][n-1])
    return 0;
}

};

→ Reply

Redux

4 years ago, # |

You have “ if(state & (1<<curr))” twice.

→ Reply

Shameek

4 years ago, # |

my approach worked — though i did top down dp

i made one optimisation — if i reach vertex n before rest of the vertices are visited i return 0

maybe 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<bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
vector<int>adj[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;
}

→ Reply

sarkarasm

4 years ago, # ^ |

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.

→ Reply

Shameek

4 years ago, # ^ |

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 tour

grid paths

all 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.

→ Reply