SEAKAM - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sergey Nagin
Tester: Antoniuk Vasyl and Misha Chorniy
Editorialist: Pushkar Mishra

DIFFICULTY:

Medium

PREREQUISITES:

Bitmask DP, Combinatorics

PROBLEM:

Given is a graph with N nodes which is almost complete, i.e., all but M edges are present. Count the number of permutations P[1..N] such that if the permutation was considered to be the order in which nodes are visited in the graph then it is a valid traversal. In other words, there exists an edge from P[1] to P[2], from P[2] to P[3], …, i.e., from P[i] to P[i+1] for i = 1 to N-1.

EXPLANATION:

Subtask 1
Simply iterate over all permutations of the nodes and count the valid ones by checking the presence of edges between P[i] and P[i+1]. This approach takes \mathcal{O}(N!) time and is fine for this substask.

Subtask 2, 3, 4
Most of the counting questions can be solved using DP. Let us see how we can think about this particular problem in terms of optimal sub-structure and overlapping sub-problems, i.e., the two necessary and sufficient requirements of a DP.

Let us think of the problem now in a way that we get to a DP. We can see that the number of missing edges are extremely few, i.e., just 7. In other words, the graph is an almost complete one. 7 missing edges means we just need to worry about the arrangement of at max 14 nodes. The other nodes can be shuffled in any manner since they don’t affect the correctness of a permutation.

Let us call the set of nodes which have certain edges missing faulty\_nodes. So it is the relative placement of the nodes of this set. Let x and y be two nodes in this set. If x and y HAVE an edge between them, i.e., edge (x, y) is not amongst the M missing edges, then we needn’t worry about how x and y are placed relative to each other in a permutation. This is our only concern is that the nodes which share a missing edge should not be adjacent to each other in a permutation. Even if x and y appear adjacent to each other, that won’t make the particular permutation invalid.

But what happens if x and y do not share an edge? We have to make sure they don’t appear adjacent to each other. How do we ensure that? We basically need to make sure that there always exists at least one element z such that z has an with both x and y. In other words, z behave as a bridge.

This gives us a hint towards the solution, i.e., the DP. We know that there only exist at maximum 14 nodes in the faulty\_nodes set. This means that we can iterate over all possible relative placements of the faulty nodes. Not clear? Let us take an example. Let the given graph have 5 nodes n_1, n_2, n_3, n_4, n_5. Of these 5, let us assume that edges (n_2, n_3) and (n_3, n_4) are missing, i.e., n_2, n_3, n_4 are faulty nodes.

In this case, there are 6 (i.e., 3!) possible relative placements of the faulty nodes in a permutation. There are (n_4, n_2, n_3), (n_4, n_3, n_2), (n_2, n_4, n_3), (n_2, n_3, n_4), (n_3, n_4, n_2) and (n_3, n_2, n_4). Note that these are relative placements of the faulty nodes only. This means that the remaining nodes, i.e., n_1 and n_5 can be placed anywhere between these faulty nodes to form a permutation P of the graph. If then each adjacent pair P[i], P[i+1] have an edge between them then the permutation is a valid one. Now let us pick up any one of the 6 relative arrangements and try to add the two remaining nodes in it.

Let’s take (n_2, n_4, n_3). Now let us see where all we can fit the n_1 and n_5 nodes so as to form valid permutations. We must place one between n_4 and n_3 since they can’t be together. There must be a node between them to act as a bridge. So one valid placement of n_1 and n_5 can be (n_1, n_2, n_4, n_5, n_3). Another one can be made by swapping n_1 and n_5. Further another one can be made one by moving around n_1 in (n_1, n_2, n_4, n_5, n_3), something like (n_2, n_4, n_5, n_1, n_3).

Now, we have a way to count the number of valid permutations that can be made. First, we take a relative arrangement of the faulty nodes. Then between each pair of faulty nodes that have a missing edge, we must place at least one normal node to act as bridge. This way, we will be able to count all the valid permutations.

One way to go about this is to cycle through all the arrangements of the faulty nodes. For a particular arrangement, we check which all pairs of adjacent faulty nodes need a bridge element between them. If a pair x, y needs one, we “tie” a normal node z to the front of y. Thus, we treat pair z, y as one element. Now, we arrange the “modified” nodes in the faulty nodes set (modified as in tied with normal nodes where required) in the (N- number of normal nodes used as bridges$)$ possible positions. The number of ways to do this further multiplied by the factorial of number of normal nodes (this is because any of the normal nodes can be used and bridge and they can be shifted around) gives the number of valid permutations for the particular relative arrangement. But this method has a problem. There can be total of 14! possible arrangements of the faulty nodes. This is not practical. We have to reduce the number of cases to consider.

This is where DP comes into picture. Let’s maintain a DP with three states: DP[mask][first\_node][number\_tied]. What do these states indicate? mask tells us which of the faulty nodes have been arranged; first\_node is the first node of the arrangement and number\_tied tells the stores the number of normal nodes that have been used as bridges, i.e., tied to a faulty node. The state mask goes from 1 to 2^{14}-1, first\_node has 14 possible values and number\_tied also has 14 possible values at max.

Thus, DP[mask][first\_node][number\_tied] gives the number of arrangements of the faulty nodes whose bit is 1 in the number mask such that the first node of the arrangement is first\_node and the number\_tied is the number of normal nodes used as bridges.

We can now formulate the recurrence:

let k = faulty_nodes.size()
let ans = 0 //counter variable
let normal_nodes = N - k;

for mask = 1 to (2^k-1)
{
    for first_node = 0 to k-1
    {
        for number_tied = 0 to k-1
        {
            //appending a new node to the beginning of the arrangement that
            //is given by mask.
            for new_first = 0 to k-1
            {
                if(new_first bit in mask == 0)
                {
                    new_mask = bitwise_or(mask, 2^new_first)
                    missing_edge = 1 if edge (new_first, first_node) missing else 0

                    //adding to the count of sequences starting with new_first and
                    //containing faulty nodes as the ones in the new_mask
                    dp[new_mask][new_first][number_tied + missing_edge] += dp[mask][first_node][number_tied];

                    //note that if the edge (new_first, first_node) is missing,
                    //we will have to tie an element to first_node, i.e.,
                    //increasing number_tied by 1.
                }
            }

            if(mask == (2^k - 1))
            {
                //if all the faulty nodes have been arranged then we can
                //count the number of valid permutations for this
                //particular arrangement

                total_objects = N - number_tied;
                val = dp[mask][first_node][number_tied];
                
                //getting all ways of arranging items
                get_ways = (total_objects choose k) * (val);

                //multiplying the number of ways of permuting normal nodes.
                get_ways = (get_ways * factorial[normal_nodes]);

                //adding to the counter variable
                ans = (ans + get_ways);
            }
        }
    }
}

return ans;

The editorialist’s program follows the editorial. Please see for implementation details. The (n choose k) mod m has been calculated using inverse factorials since m in this case is a sufficiently large prime.

OPTIMAL COMPLEXITY:

\mathcal{O}(M^32^M) per test case.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

5 Likes

I think there is a mistake in paragraph 4 of subtask 2,3,4’s explaination.

“But what happens if x and y DO share an edge,”

It must be “DO NOT”

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

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

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

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.

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!

@rishabjain9196, here is a link to my solution for 25 points which exactly uses for ides for graph using adjacency matrix. https://www.codechef.com/viewsolution/9053712

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

@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

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.

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