ALTRTREE - Editorial (Kodeathon 15.2)

general
,
1

PROBLEM LINK:

Practice

Contest

Author & Editorialist: Pulkit Sharma

Tester: Satyam Gupta

DIFFICULTY:

EASY

PREREQUISITES:

Graphs, (DFS)

PROBLEM:

Given a Tree , find whether whether all the nodes of a tree satisfy the condition to make it an alternating tree. Read here to see details.

EXPLANATION:

let state store the state at which the current node is. There are two possible states . crest or trough.

What the problem boils down is to find whether all the paths from root to the leaves is of the form [crest,trough,crest,...] or [trough,crest,trough...] .

This can easily be done using DFS.

To start with DFS , we first need to find the state of the root node.
This can be done by comparing it with its children.

If all the child nodes have a value greater than the root , then the root's state is trough , stored as 0.

Similarly, if all the child nodes have a value less than the root, then the root's state is crest , stored as 1.

If none of the above is true , then the root is in an invalid state.
So, straightaway the tree is Not an Alternating Tree.

Once we have the root's state, we can start with our DFS . But we need to slightly modify the standard DFS implementation as we have to keep track of the state of the current node the DFS has reached.

The following DFS skeleton code should help you to understand:

	DFS(node,state)
	//other necessary code
	if state = 0 
		//every child should be greater than it
		for all children
		if(child_i is greater than node)
			DFS(child_i,1-state) //IMPORTANT , change the state
		else
			//exit from DFS, not an alternating Tree

	if state = 1 
		//every child should be smaller than it
		for all children
		if(child_i is smaller than node)
			DFS(child_i,1-state) //IMPORTANT , change the state
		else
			//exit from DFS, not an alternating Tree

If the DFS did not prematurely end, then depending upon the state of the root we can print our answer.

If the DFS did end prematurely , then the tree is not an Alternating Tree

AUTHOR’S SOLUTION:

#include<iostream>
#include<list>
#include<vector>
#include<cstdio>

using namespace std;

int a[10005];
vector< list<int> > g(10005);
bool notset,mat,nat;

void dfs(int x,bool y)
{
    for(list<int>::iterator it=g[x].begin();!nat && it!=g[x].end();it++)
    {
        if(notset)
        {
            if(a[x]<a[*it]) mat=1;
            else y=mat=0;
            notset=0;
        }
        else
        {
            if((!y && a[x]<a[*it])||(y && a[x]>a[*it]))
            {nat=1;return;}
        }

        //printf("\n[%d,%d] (%d,%d,%d)",x,*it,notset,mat,nat);

        dfs(*it,!y);

    }


}

int main()
{
    cin.sync_with_stdio(false);
    cin.tie(NULL);

    int t,i,j,n,x,y;
    cin>>t;

    while(t--)
    {
        cin>>n;

        for(i=0;i<n;i++){cin>>a[i];g[i].clear();}

        nat=0;
        notset=1;
        for(i=0;i<n;i++)
        {
            cin>>x;

            for(j=0;j<x;j++)
            {
                cin>>y;

                g[i].push_back(y);
            }
        }

        dfs(0,1);

        if(nat) cout<<"NAT\n";
        else if(mat) cout<<"MAT\n";
        else cout<<"VAT\n";

    }

    return 0;
}