sarkarasm's blog

Help needed in CSES graph question Hamiltonian Flights
By sarkarasm, 4 years ago, In English

Link to question: link

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is what you are looking for

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I have not done grid paths, but I did not require any optimization in Knights tour. I just used Warnsdorf's rule.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          oh i was treating Warnsdorf's rule as an optimisation too

          → Reply
    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah you are correct this optimizations reduce the runtime by half. I have a bottom up soln .

      bottom up AC code
      → Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ?

    → Reply