SEAKAM - Editorial

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

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