Approach for these problems

general
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

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

4

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

  • @author rohan
    */
    class AVIMAGIC {
    public static void main(String[] args) throws java.io.IOException {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    int n=Integer.parseInt(br.readLine()),q,len,ch,tem[],arr[],size,index=0,root[],pre,pointer;
    StringBuilder m,ans,printing=new StringBuilder();
    ArrayList<int[]> vertex=new ArrayList<>();
    root=new int[7];
    root[5]=Integer.MAX_VALUE;
    vertex.add(root);
    size=1;
    for (int i = 0; i < n; i++) {
    m=new StringBuilder(br.readLine());
    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\n");
    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("\n");
    }
    System.out.print(printing);
    }
    }
1 Like
5

Thanks alot

6

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