# Approach for these problems

#1

Can anyone tell me how to solve these two problems?

problem 1
and
problem 2

I saw the solutions of others but am unable to understand the approach.

#2

Query on tree uses HLD of trees.
Avani and magic requires you to use Tries.
If you want author’s solutions for the problems, you can request below in the comments.

#3

import java.io.;
import java.util.ArrayList;
/

• @author rohan
*/
class AVIMAGIC {
public static void main(String[] args) throws java.io.IOException {
StringBuilder m,ans,printing=new StringBuilder();
ArrayList<int[]> vertex=new ArrayList<>();
root=new int[7];
root[5]=Integer.MAX_VALUE;
size=1;
for (int i = 0; i < n; i++) {
m=m.append(’`'); len= m.length(); pointer=0; tem=vertex.get(0); while(len>0){ ch=m.charAt(pointer)-96; pointer++; if(tem[ch]==0){ arr=new int[7]; arr[5]=Integer.MAX_VALUE; vertex.add(arr); size++; tem[ch]=size-1; if(ch<tem[5]){ tem[5]=ch; } if(tem[6]<ch){ tem[6]=ch; } } tem=vertex.get(tem[ch]); len--; } } q=Integer.parseInt(br.readLine()); for (int i = 0; i < q; i++) { tem=vertex.get(0); ans=new StringBuilder(); pre=0; m=new StringBuilder(br.readLine()); m=m.append('`’);
len= m.length();
pointer=0;
arr=null;
while(len>0){
ch=m.charAt(pointer++)-96;
if(tem[5]<ch){
arr=tem;
index=ch;
pre=pointer-1;
}
tem=vertex.get(tem[ch]);
len–;
}
tem=arr;
if(tem==null){
printing.append("-1
“);
continue;
}
ans=ans.append(m.substring(0, pre));
while (true) {
if(tem[–index]!=0){
ans.append((char)(index+96));
tem=vertex.get(tem[index]);
break;
}
}
while(tem!=root){
ans.append((char)(tem[6]+96));
tem=vertex.get(tem[tem[6]]);
}
printing.append(ans.substring(0,ans.length()-2)).append(”
");
}
System.out.print(printing);
}
}

#4

thank you. Please provide the solution. That would help a lot.

#5

Thanks alot

#6

For Query on tree, you can refer to anybody’s solution. They are almost same.