PROBLEM LINK:
Author: Chandan Boruah
DIFFICULTY:
SIMPLE
PREREQUISITES:
Brute Force, Data Structure, Graph Theory, Greedy.
PROBLEM:
Given a Tree, each node being a string you need to print the alphabetically smallest string you can print by following a path from root to a leaf node in the tree.
QUICK EXPLANATION:
Since alphabetically smallest is asked, at every level it is best to choose the alphabetically smallest string at every level of the tree.
EXPLANATION:
Since the tree is given in adjacency matrix, all the positions that are set to 1 in a level will be all the index positions in a row that are 1.
Example:
0 1 1
0 0 0
0 0 0
Here, the tree is
@
/ \
@ @
Notice that the same row has the same level in the tree. So in every level we can sort the alphabetically smallest string and store in a list with its index position, it is greedy. After which these lists can be used to reach a leaf node resulting in an alphabetically smallest string.
ADDITIONAL NOTES
In the contest, the author (that is me) forgot to mention that a leaf node needs to be reached. Omission of this information results in confusion, since an empty string is alphabetically smallest string, so how many levels needs to be reached remains unclear.
SOLUTIONS:
Author's Solution
using System;
using System.Collections.Generic;
class some
{
public static void Main()
{
int n=int.Parse(Console.ReadLine());
string[]ss=Console.ReadLine().Split();
int[,]graph=new int[n,n];
for(int i=0;i<n;i++)
{
string[]temp=Console.ReadLine().Split();
for(int j=0;j<n;j++)
{
graph[i,j]=int.Parse(temp[j]+"");
}
}
List<List<string>>ll=new List<List<string>>();
for(int i=0;i<n;i++)
{
List<string>t=new List<string>();
for(int j=0;j<n;j++)
{
if(graph[i,j]==1)
{
t.Add(j+" "+ss[j]);
}
}
t.Sort();
ll.Add(t);
}
string now=ss[0];
for(int i=0;;)
{
if(ll[i].Count==0)break;
string[] kk=ll[i][0].Split();
now+=kk[1];
i=int.Parse(kk[0]);
}
Console.WriteLine(now);
}
}
