MotaSanyal's blog

By MotaSanyal, history, 5 weeks ago, In English,

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

Problem Source — Codenation Hiring Test

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 :)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like 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.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      for problem 3 :- link

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Was you the author of all three questions ?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like 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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like 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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 <bits/stdc++.h>
using namespace std;

#define multitest 1
#ifdef Debug
#define db(...) ZZ(#__VA_ARGS__, __VA_ARGS__);
template <typename Arg1>
void ZZ(const char *name, Arg1 &&arg1)
{
	std::cerr << name << " = " << arg1 << endl;
}
template <typename Arg1, typename... Args>
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<vector<int>> 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<int> Oddways(n + 1), Evenways(n + 1);
	queue<int> 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<double>(chrono::steady_clock::now() - TimeStart).count() << " seconds.\n";
#endif
	return 0;
}
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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