SEAKAM - Editorial

editorial
, , ,
8

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!!

9

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

10

@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
11

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.

12

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

13

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.

14

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

And @admin solution link is broken .

15

Please allow access to setter and tester solution.

16

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

17

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

1 Like
18

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

19

Hi Guys!

Here is a video editorial on the problem:

[DP With BitMasks - SEAKAM][1]

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

20

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

21

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

22

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

23

@sanchitkashyap if there are q distinct chains of edges and we consider each chain(containing one or more edges) as one component then total no of components = q + (n-p) . (n-p) are free vertices ie vertices not linked to any edge. no of permutations of (n-p+q) components is thus (n-p+q)! . also each of q chains has two arrangements ie forward and backward thus pow(2,q). thus total ways = (n-p+q)! x pow(2,q)

1 Like
24

thanks. the editorial is a community wiki. if you find errors, you can correct them.

25

Oops, Didnt know that, sorry.

26

Editorialist solution now available.

27

@mukul_chandel
@animan123
@rushilpaul
Hello, I still didnt not understand this solution, Can anyone please explain it in more detail ? That would be really really great.

Please explain the 2 formulae you get, I am familiar with only basic inclusion exclusion of finding the union if intersection and individual cardinality are given.

Thanks in advance.