SEAKAM - Editorial

editorial
, , ,
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

1 Like
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.

28

I have same doubt did you got it how did this arrive???

29

I have doubt in test cases can anybody explain it??
for test case 2
input:-
2 1
1 2

here there should be 2 possible combinations
12
and
21
so the ouput should be 2
but output is 0 why???

30

The M edges given are not connected. 1 and 2 are not connected by an edge. So the graph has no edges. Hence answer is 0.

32

Thanks bro actually i read the question wrong i thought here m is the number of edges connected but it was not connected

1 Like