Hello everyone ! It would be nice if anyone helps me with the solution to this problem — Even Paths

Problem Source — Codenation Hiring Test

Before contest

Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)

32:42:32

Register now »

Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)

32:42:32

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3645 |

2 | Radewoosh | 3403 |

3 | Um_nik | 3348 |

4 | LHiC | 3336 |

5 | Benq | 3316 |

6 | V--o_o--V | 3275 |

7 | mnbvmar | 3241 |

8 | yutaka1999 | 3190 |

9 | ainta | 3180 |

10 | Petr | 3106 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 192 |

2 | Radewoosh | 177 |

3 | PikMike | 165 |

4 | rng_58 | 164 |

5 | Vovuh | 160 |

6 | majk | 158 |

7 | antontrygubO_o | 154 |

7 | 300iq | 154 |

9 | Um_nik | 151 |

10 | kostka | 149 |

Hello everyone ! It would be nice if anyone helps me with the solution to this problem — Even Paths

Problem Source — Codenation Hiring Test

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/24/2019 08:52:29 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

It can be solved using DP. Build up adjacency list for the graph and an adjacency list for the reverse graph. Then, maintain a memoization table to store the no of even and odd paths from source till every vertex v. Now, looping over all the vertices who haven't been visited yet and are sink vertices(outdegree = 0) call a recursive function.

Similarly, compute the odd length paths. I think this should work.

Thanks. I had the same idea but unfortunately haven't been able to submit, so I needed a confirmation. Good to see that you got the exact same approach :)

can you share other problems too.

Yeah Sure

Constrained GCD Array

Divisor Luck

Even Paths

Thank you very much.

Did you solve constrained GCD, can u write constraints again , is N<=1e9.

how did you solve divisor luck?

I think that we can also do topological sorting and then we have already result for source vertex and calculate answers for vertex in order of topological sorting by the help of reverse edges as you mentioned.

Yeah. That should work fine as well.

Yeah, topological sort can avoid any inconsistency i think

Brief solutions: evenpaths: for each node try to count odd and even length paths using info of nodes that have a edge going into current node in a dp style.

Constraint gcd: hint : for each segment try to reduce it to counting walka in a suitable graph after which it is matrix expo

Divisor luck: for each number get its sum of divisors. After that process in sorted order.

Can you please explain, how do you reduce the problem "Constrained GCD Array" to a graph problem. Are there any source from where I can get to read about it ?

Not sure about source. Hint: try to make a graph with nodes as numbers 1 to 20. Put edge between x and y if gcd(x,y) = Gi.

how this graph would make a linear sequence(as you said matrix expo), can you explain a bit on that part? if possible what should be the linear sequence for an array of size 3 and gi to be made is 4 in all.

its not a linear recurrence as such. Try searching how to find number of walks in a graph.

for problem 3 :- link

Thanks for the brief solutions!

Here are the author solution codes:

Even Paths: http://p.ip.fi/GVI4

Constrained GCD Array: http://p.ip.fi/agm1

Divisor Luck: http://p.ip.fi/TVEI

Was you the author of all three questions ?

Yes

why the expected value of sum of values of divisors did not work ? , first i found sum of values of divisors of each numbers in range L1 , R1 and add them as whole , similarly for L2,R2 then divide by their size ie. (R1-L1+1)

thus is would get expected value of the sum of values divisors and it was giving WA, can you explain why? and which ever range has higher expected value i outputed it.

Hey Ashish, can you explain the solution a bit more about Even-Paths... Thanks in advance :-)

Hey! My idea of making the implementation simpler is to reverse the graph and compute the number of paths that start at the ith node and end at X with odd parity!

For that, I've written a 2*N DP where dp[i][0] is the number of ways to start from ith node and end at X with odd parity, and dp[i][1] is the number of ways to start from ith node and end at X with the even (same) parity.

The recurrence is simple: The number of ways to start at node i with parity 0, is the summation on the number of ways to start its children with parity 1, and similarly for the other parity.

ashishgup can't we submit it now ??? can you help in making it available for submission...

the contest ended

Hey Ashish, Could you please explain the solution to Constrained GCD Array? Thanks in advance.

why the expected value of sum of divisors did not work ? , first i found sum of divisors of all numbers in range L1 , R1 and then in L2,R2 then divide by their size ie. (R1-L1+1)

thus is would get expected value of the sum of divisors and it was giving WA, can you explain why? and which ever range has higher expected value i outputed it.

why the expected value of sum of divisors did not work ? , first i found sum of divisors of all numbers in range L1 , R1 and then in L2,R2 then divide by their size ie. (R1-L1+1)

thus is would get expected value of the sum of divisors and it was giving WA, can you explain why? and which ever range has higher expected value i outputed it.

How about the following solution to the problem 3 - Taking the node x as src, start dfs and have a parameter in the dfs function which will increase by one with every recursive call of dfs, whenever that parameter is odd, we increment that current node value by one. At end we just print out the values associated with all the nodes.

I think the problem with this one is that it will time out. A normal dfs from X will visit all the path more than once( since more than one path can update the value of a node)

oh yes, with n given up to 10^5

Can we use sieve method in "Divisor luck" problem, and usng the sieve we can find the highest power of a prime number in the numbers of our range.

Here is the code, It passed all the test cases.

Code Speaks for itself, but feel free to ask doubts.

Knowledge required for this is Dp on trees and Topological Sort.

can u plz put other 2 questions if u have , i was registerd for this test but missed that