HackerEarth Gandhi Tree March problem solution

In this HackerEarth Gandhi Tree March problem solution, Gandhijee is interested in building a human tree. He defined a human node as follows :

Person_Id = English alphabet {a…z} .

Person_Chain_Definition = Person_Id ( Person_Chain_Definition Person_Chain_Definition )

For example :

a( b(..) c( d( . e(..) ) f( . . ) ) ) refers to a human tree having a as the root human, whose chain links are are b and c, (spaces here are for clarity, input file has no spaces).

Note: After every Person_Id there is necessarily an opening parenthesis ( that starts the definition of the sub-tree under the person. For empty(NULL) human nodes, there is a ‘.’ character.

Now, Gandhijee figures out the tree as follows :

Step 1: He writes root human root id in column 0.

Step 2: Then he writes the left link’s person id in 1 column to the left and the right link’s person id in 1 column to the right.

He continues writing the subtree, in a way that, for an id written in column C, its left link’s id is written in column C-1 and the right link’s id is written in column C+1.

Now, Gandhijee wants to know the ids of people standing in a particular column C in lexicographically sorted order.

You are provided with column number C and the Tree definition string S. Gandhijee is very busy and hence he wants you to help him.

HackerEarth Gandhi Tree March problem solution.

#include<string>
#include<vector>
#include<cstdio>
#include<sstream>
#include<cassert>
#include<iostream>
#include<algorithm>
using namespace std;

int pos;
string S;
vector<char> L[10001], R[10001];

void buildTree(int C)
{
    if(S[pos]!='.')
    {
        if(abs(C)<=10000)
        {
            if(C>=0)  L[C].push_back(S[pos]);
            else  R[-C].push_back(S[pos]);
        }
        pos+=2;
        buildTree(C-1);
        buildTree(C+1);
    }
    pos++;
}

int main()
{
    int i, T, C, Size;
    cin>>T;
    while(T--)
    {
        pos=0;
        cin>>C>>S;
        for(i=0; i<=10000; i++)  L[i].clear(), R[i].clear();

        buildTree(0);

        if(C>=0)
        {
            if(Size=L[C].size())
            {
                sort(L[C].begin(), L[C].end());
                for(i=0; i<Size; i++) cout<<L[C][i];
                cout<<endl;
            }
            else cout<<"Common Gandhijee!n";
        }
        else
        {
            if(Size=R[-C].size())
            {
                sort(R[-C].begin(),R[-C].end());
                for(i=0; i<Size; i++)cout<<R[-C][i];
                cout<<endl;
            }
            else cout<<"Common Gandhijee!n";
        }
    }
    return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
#define maxc (1000)
#define assn(n,a,b) assert(n>=a && n<=b)
string arr[2*(maxc) + 100];
int a;
string str;
void process(int b)
{
    if(str[a]!='.')
    {
    if(abs(b)<=maxc)
        arr[b+maxc]+=str[a];
    a+=2;
    process(b-1);
    process(b+1);
    }
    a++;
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
    int c,i,j,n;
    a=0;
    for(i=0; i<2*maxc + 100; i++)
        arr[i]="";
    cin >> c >> str;
    n=str.length();
    assn(c,-1*maxc,maxc);
    process(0);
    sort(arr[c+maxc].begin(),arr[c+maxc].end());
    if(arr[c+maxc].size())
        cout << arr[c+maxc] << endl;
    else cout << "Common Gandhijee!" << endl;
    }
    return 0;
}

HackerEarth Gandhi Tree March problem solution.

Second solution

Leave a Reply