Hello everyone ! It would be nice if anyone helps me with the solution to this problem — Even Paths
Problem Source — Codenation Hiring Test
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Hello everyone ! It would be nice if anyone helps me with the solution to this problem — Even Paths
Problem Source — Codenation Hiring Test
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
Did you solve constrained GCD, can u write constraints again , is N<=1e9.
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
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...
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
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.