SEAKAM - Editorial

I used inclusion exclusion to solve this.

Without any removed edges there would be n! permutations.
Now when you remove m edges, the number of permutations reduce, by how much? We can find this by inclusion exclusion. Let f(mi) be number of permutations containing the edge mi. So for all edges, the total number of permutations we have is given by

f(m1) + f(m2) + f(m3) + … - f(m1 & m2) - f(m1 & m3) - … + f(m1 & m2 & m3) and so on.

Now to find, f(mi1 & mi2 & mi3 & …) we can observe 2 things :

  1. If these edges form a cycle they do not appear in any permutation

  2. If a node in any of these edges has degree more than 2, it cannot appear in any permutation

After checking these two condition it’s simple. We only have to count the number of components obtained by combining edges. Answer for f will be :

f(mi1 & mi2 & mi3 & … ) = (n-p+q)! * pow(2,q) where,

p-number of elements covered by edges mi1,mi2,…

q-number of components obtained after combining these edges.

All these operations can be done efficiently using a DSU

https://www.codechef.com/viewsolution/9077502

10 Likes

@animan123 Inclusion Exclusion principle I think is nice approach to solve this…I also did that

Yes, I think Inclusion Exclusion is a better and easy approach .My solution

@animan123 did the same could not come up with dp sol!

@animan123 Did the Same Dude…!!

Hey,

Can anyone tell me why my code gave a TLE (Even for the first subtask)? And how could I have improved the code?
https://www.codechef.com/viewsolution/9153177

#include<iostream>
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
long long int v[101];
long long int edges[1000][1000];
int main()
{
    long long int t,n,m,i,j,k,l,e,a,b,c,d;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld %lld",&n,&m);
        memset(edges, 0, sizeof(edges[0][0]*n*n));
        for(i=0; i<m; i++)
        {   scanf("%lld %lld",&a,&b);
            a--;
            b--;
            edges[a][b]=1;
            edges[b][a]=1;
            edges[i][i]=1;
        }
//        for(i=0;i<n;i++)
//        {
//            for(int j=0;j<n;j++)
//            {
//                cout<<edges[i][j]<<"  ";
//            }
//            cout<<endl;
//        }
        for(i=0;i<n;i++)
            v[i]=i;
            long long int f=0;
        do
        {   k=0;
            for(i=0;i<n-1;i++)
            {  //cout<<v[i];
                if(edges[v[i]][v[i+1]]==1)
                {   k=1;
                    break;
                    //cout<<endl;
                }
            }
            if(k==0) f++;
            f=f%1000000007;
            //cout<<v[i]<<endl;
        }
        while ( std::next_permutation(v,v+n) );
                printf("%lld\n",f);
 
    }
}

Thanks in advance!!

@rishabh.jain9196 Because you are using stl function next_permutation which is taking too much time.You may implement your own permutation generator to pass first subtask.

@rishabjain9196, here is a link to my solution for 25 points which exactly uses for ides for graph using adjacency matrix. CodeChef: Practical coding for everyone

You can also see my complete commented and explained code for 100 points which passed in 0.00 sec.
https://www.codechef.com/viewsolution/9091313

1 Like

The name was a giveaway in my case. No mention of a Salesman in the problem led me to work on a dp solution similar to the Travelling Salesman Problem.

Can someone explain that in the method of inclusion and exclusion how to calculate the number of permutations that have those k edges? K<m

I used Combinatorics only.
ans = P(1) - P(2) + P(3) - P(4) + …
where P(n) is number of permutations when n pairs are occurring.
My solution is here.

In above dp solution what dp[][][] should initialize with ?

And @admin solution link is broken .

Please allow access to setter and tester solution.

I solved by the combination of bitmask , dfs , inclusion-exclusion principle ;
Subtask1 got accepted , while as for the remaining , it is giving wrong answer .

below is the link of the solution ; could some point out the bug in the code ?

https://www.codechef.com/viewsolution/9131639

Link to my ACed Solution : CodeChef: Practical coding for everyone

1 Like

can anyone give me a link about inclusion exclusion technique.
thanks in advance !!

Hi Guys!

Here is a video editorial on the problem:

[DP With BitMasks - SEAKAM][1]

Cheers!
[1]: Dynamic Programming with Bitmasks - YouTube

1 Like

@animan123 Can you please explain how did you arrive at this formula
f(mi1 & mi2 & mi3 & … ) = (n-p+q)! * pow(2,q)

next_permutation(v,v+n) will run n! times. so your code complexity is n*n! which is too high to pass in 1 sec for n>10. Your code could have passed the first subtask if you had not included the statement f=f%1000000007 which also takes a lot of time to execute. Also this line is not necessary for the first subtask as your ans will never exceed 1000000007 in the first subtask

A lot of people have used inclusion exclusion. Did the same! I honestly didn’t think it to be a DP question!