Hack the Interview 6 (Constructing a Tree)

help
,
1

i am able to come up with an algorithm but i have no idea to implement it.
if anyone can give an alogrithm with its implementation ,that would be great.

3

Your submission is not viewable.

2 Likes
4

yeah . its not visible. can u share it in other way.

5

Sorry…I thought that it’s visible…
I’m pasting my code as I can’t get the other wayy :no_mouth:

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef long long int ll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t;
    cin>>t;
    while(t--)
    {
    ll n,x;
    cin>>n>>x;
    if(n-1>x || x>(n*(n-1))/2)
        cout<<-1<<' '<<-1<<'\n';
    else
    {
        ll a[n+1]={0};
    
        ll s=0,i=n,pos=2;
        while(s<x)
        {
            if(i<pos)
            {
                pos++;
                i=n;
            }
            a[i]++;
            s++;
            i--;
            
        }
        for(int k=1;k<n;k++)
        {
            for(int u=k+1;u<=n;u++)
            {
                if(a[u]==a[k]+1)
                    cout<<k<<' '<<u<<'\n';
                else 
                    break;
            }
        }
        
    }
    }
    return 0;
}
2 Likes
6

no problem. thanks for the code :grin:

7 
#include "bits/stdc++.h"
using namespace std;

int main()
{
    long long t;
    cin >> t; 
    while(t--)
    {
        long long n , x , hi = 0, m[50001];
        cin >> n >> x;
        if(x>(n*(n-1)/2) || x<(n-1)) cout << "-1 -1\n";
        else if(n==1 && x==0) continue;    
        else
        {
            while((hi+2)*(hi+1)/2 + (n-hi-2) <= x) hi++;
            for(int i = 2 ; i < 2 + hi ; i++) m[i] = i-1 ;
            for(int i = 2 + hi ; i < n + 1 ; i++) m[i] = 1;
            m[hi+2] = (x - (hi*(hi+1)/2) - (n-1-hi) + 1);
            for(int i = 2 ; i < n + 1 ; i++) cout << i << ' ' << m[i] << endl;
        }
    }
}

Here is one implementation I can think of.

2 Likes
8

appreciate it.