HackerEarth Fredo's Crush problem solution

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.

#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 %dn",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 %dn",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;
}

coding problems solutions