MotaSanyal's blog

By MotaSanyal, history, 5 years 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

| Write comment?
»
5 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years 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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      for problem 3 :- link

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

      Was you the author of all three questions ?

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

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

»
5 years 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 years 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 years 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;
}