All Tracks Algorithms Graphs Hamiltonian Path Problem

Fredo's Crush

Bitmask, Dynamic Programming, Graph Theory, Medium


Fredo has crush on a girl in his class. He went to ask her out for a date. She, being a coder, gave her a simple graph with $$N$$ vertices and $$M$$ edges and asked him to solve a problem on the graph in order to go on a date with her.
The problem says:
Let there be some functions defined below:
For each vertex in the graph:
S = max (sum of all vertices lying in the maximum length simple path ending at that vertex)
That is, if there are two simple paths with length 3 ending at some vertex and there can be no simple path with length greater than 3, and P be the sum of vertices of first path and Q of second. So, S = max(P,Q).

Let A = minimum value of S[i] ($$1 \le i \le n$$)
B = maximum value of S[i] ($$1 \le i \le n$$)
You are given an equation Ax = By
Find the minimum value of $$x$$ and $$y$$ satisfying the equation.
Note: If there are no simple paths ending at some vertex, S for that vertex will be number of that vertex.
A simple path is a path in a graph which does not have repeating vertices.

Input Format:

First line contains an integer $$T$$ denoting the number of test cases.
First line of each test case consists of two space separated integers denoting $$N$$ and $$M$$ and the following $$M$$ lines consist of two space separated integers $$X$$ and $$Y$$ denoting there is an edge between vertices $$X$$ and $$Y$$.

Output Format:

For each test case, print the values of $$x$$ and $$y$$ (space separated) in a separate line.

$$ 1 \le T \le 10 $$
$$ 1 \le N \le 15 $$
$$ 0 \le M < N*(N-1)/2 $$
$$ 1 \le X, Y \le N $$

3 0
3 2
1 2
2 3
3 1
6 5

In the first case, there are no simple paths ending at any vertex, so S={1,2,3}, we need to solve for 1 * x=3 * y.
In the second case,
paths ending at 1 are: 3-2-1 and 2-1. The maximum length path is 3-2-1 having sum=3+2+1=6
paths ending at 2 are: 1-2 and 3-2. Both have the same length, s[2]=max(1+2,3+2)=5
and similarly for 3, s[3]=6
so we need to solve for 5 * x=6 * y.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin


Initializing Code Editor...
Your Rating:


View All Notifications