### MotaSanyal's blog

By MotaSanyal, history, 3 months ago, ,

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

Problem Source — Codenation Hiring Test

• +4

 » 3 months ago, # |   +1 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. No of even length paths till vertex v = No of odd length paths till all the vertices that have an outgoing edge to v. Similarly, compute the odd length paths. I think this should work.
•  » » 3 months ago, # ^ |   +1 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 :)
•  » » » 3 months ago, # ^ |   0 can you share other problems too.
•  » » » » 3 months ago, # ^ |   +1 Yeah Sure
•  » » » » » 3 months ago, # ^ |   0 Thank you very much.
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Did you solve constrained GCD, can u write constraints again , is N<=1e9.
•  » » » » » 3 months ago, # ^ |   0 how did you solve divisor luck?
•  » » 3 months ago, # ^ |   +3 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.
•  » » » 3 months ago, # ^ |   0 Yeah. That should work fine as well.
•  » » » 3 months ago, # ^ |   0 Yeah, topological sort can avoid any inconsistency i think
 » 3 months ago, # |   0 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 expoDivisor luck: for each number get its sum of divisors. After that process in sorted order.
•  » » 3 months ago, # ^ |   0 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 ?
•  » » » 3 months ago, # ^ |   0 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.
•  » » » » 3 months ago, # ^ |   0 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.
•  » » » » » 3 months ago, # ^ |   0 its not a linear recurrence as such. Try searching how to find number of walks in a graph.
•  » » » 3 months ago, # ^ |   0 for problem 3 :- link
•  » » 3 months ago, # ^ |   +4 Thanks for the brief solutions! Here are the author solution codes:Even Paths: http://p.ip.fi/GVI4Constrained GCD Array: http://p.ip.fi/agm1Divisor Luck: http://p.ip.fi/TVEI
•  » » » 3 months ago, # ^ |   0 Was you the author of all three questions ?
•  » » » » 3 months ago, # ^ |   0 Yes
•  » » » » » 3 months ago, # ^ |   0 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.
•  » » » 3 months ago, # ^ |   0 Hey Ashish, can you explain the solution a bit more about Even-Paths... Thanks in advance :-)
•  » » » » 3 months ago, # ^ |   +1 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.
•  » » » » » 3 months ago, # ^ |   0 ashishgup can't we submit it now ??? can you help in making it available for submission...
•  » » » » » » 3 months ago, # ^ |   0 the contest ended
•  » » » 3 months ago, # ^ |   0 Hey Ashish, Could you please explain the solution to Constrained GCD Array? Thanks in advance.
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » 3 months ago, # ^ |   0 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.
 » 3 months ago, # |   0 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.
•  » » 3 months ago, # ^ |   0 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)
•  » » » 3 months ago, # ^ |   0 oh yes, with n given up to 10^5
 » 3 months ago, # |   0 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.
 » 3 months ago, # |   0 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. //Optimise #include using namespace std; #define multitest 1 #ifdef Debug #define db(...) ZZ(#__VA_ARGS__, __VA_ARGS__); template void ZZ(const char *name, Arg1 &&arg1) { std::cerr << name << " = " << arg1 << endl; } template void ZZ(const char *names, Arg1 &&arg1, Args &&... args) { const char *comma = strchr(names + 1, ','); std::cerr.write(names, comma - names) << " = " << arg1; ZZ(comma, args...); } #else #define db(...) #endif using ll = long long; #define f first #define s second #define pb push_back const long long mod = 1000000007; auto TimeStart = chrono::steady_clock::now(); const int nax = 2e5 + 10; void solve() { int n, m, x; cin >> n >> m >> x; vector> Adj(n + 1), indegree(n + 1); int u, v; for (int i = 0; i < m; ++i) { cin >> u >> v; Adj[u].pb(v); indegree[v]++; } vector Oddways(n + 1), Evenways(n + 1); queue Q; for (int i = 1; i <= n; ++i) if (!indegree[i]) Q, push(i); Oddways[x] = 1; while (!Q.empty()) { auto top = Q.front(); Q.pop(); for (int child : Adj[top]) { Oddways[child] += Evenways[top]; Evenways[child] += Oddways[top]; Oddways[child] %= mod; Evenways[child] %= mod; indegree[child]--; if (!indegree[child]) Q.push(child); } } for (int i = 1; i <= n; ++i) cout << Evenways[i] << ' '; cout << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; #ifdef multitest cin >> t; #endif while (t--) solve(); #ifdef TIME cerr << "\n\nTime elapsed: " << chrono::duration(chrono::steady_clock::now() - TimeStart).count() << " seconds.\n"; #endif return 0; } 
 » 3 months ago, # |   0 can u plz put other 2 questions if u have , i was registerd for this test but missed that