In this HackerEarth Fredo's Crush problem solution 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<=i<=n)
B = maximum value of S[i] (1<=i<=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.


HackerEarth Fredo's Crush problem solution


HackerEarth Fredo's Crush problem solution.

#include<bits/stdc++.h>
#define nmax 15
using namespace std;
int ans[nmax],sum[nmax];
void find_hamiltonian_paths(int adj[nmax][nmax],int n)
{
bool dp[nmax][1<<nmax]={0};
int i,j,k;
for(i=0;i<n;i++)
{
dp[i][1<<i]=1;
ans[i]=0;sum[i]=i+1;
}
int limit=1<<n;
for(i=0;i<limit;i++)
{
int s=0;
int count=0,temp=i;
while(temp)
{
s+=log2(temp&-temp)+1;
temp&=temp-1;
count++;
}
for(j=0;j<n;j++)
{
if(i & (1<<j))
{
for(k=0;k<n;k++)
if(k!=j && adj[k][j] && (i & (1<<k)) && dp[k][i^(1<<j)])
{
dp[j][i]=1;
ans[j]=max(ans[j],count-1);
if(ans[j]==count-1)sum[j]=max(sum[j],s);
break;
}
}
}
}
/*for(i=0;i<n;i++)
printf("%d %d\n",ans[i],sum[i]);*/
//printf("\n");
}
int gcd(int a,int b)
{
return (b)?gcd(b,a%b):a;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m,i,adj[nmax][nmax]={0};
scanf("%d%d",&n,&m);
for(i=0;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
adj[x-1][y-1]=adj[y-1][x-1]=1;
}
find_hamiltonian_paths(adj,n);
int minn,maxx;minn=maxx=sum[0];
for(i=1;i<n;i++)
{
if(minn>sum[i])minn=sum[i];
if(maxx<sum[i])maxx=sum[i];
}
int hcf=gcd(maxx,minn);
printf("%d %d\n",maxx/hcf,minn/hcf);
}
return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mk make_pair
ll power(ll a, ll b) {
ll x = 1, y = a;
while(b > 0) {
if(b%2 == 1) {
x=(x*y);
if(x>mod) x%=mod;
}
y = (y*y);
if(y>mod) y%=mod;
b /= 2;
}
return x;
}
int adj[15][15],dist[15],path[15];
int dp[15][1<<15];
int n;
pair<int,int> find(int x)
{
int i,s = 0;
int c = 0;
for(i = 0; i < n; i++) {
if(x & (1<<i)) {
s += i+1;
c++;
}
}
return make_pair(c,s);
}
void solve(int total)
{
pair<int,int>p = find(total);
p.first--;
int i,j;
for(i = 0; i < n; i++) {
if(total&(1<<i)) {
for(j = 0; j < n; j++) {
if(j != i && adj[i][j] != -1) {
if(dp[j][total&~(1<<i)] != -1) {
dp[i][total]++;
if(path[i] <= p.first) {
path[i] = p.first;
dist[i] = max(dist[i],p.second);
}
break;
}
}
}
}
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
int t,m,i,j,u,v;
cin>>t;
while(t--) {
cin>>n>>m;
memset(dp,-1,sizeof dp);
memset(adj,-1,sizeof adj);
while(m--) {
cin>>u>>v;
u--;
v--;
adj[u][v] = adj[v][u] = 1;
}
int maxi = INT_MIN;
int mini = INT_MAX;
for(i = 0; i < n; i++) {
dist[i] = i+1;
path[i] = 0;
dp[i][1<<i] = 1;
}
for(i = 0; i < (1<<n); i++) {
solve(i);
}
for(i = 0; i < n; i++ ) {
maxi = max(maxi,dist[i]);
mini = min(mini,dist[i]);
}
int lcm = maxi*mini/__gcd(maxi,mini);
cout<<lcm/mini<<" "<<lcm/maxi<<endl;
}
return 0;
}