Sunday, February 14, 2016

TAP2012D SPOJ (Trie with HashMaps) solution Java

You need to put all the names first and second team players in the same trie. If your logic involves putting the names of team1 into trie and then using team2 player names, you're likely to get WAs. For eg. changing the order of queries for team2 names will get you different answers in some cases.

Check out these test cases:-

5
H HE HER HEREB HEREBY
HEREBY HEREB HERE HER HE

7
THIS IS JUST A SE NT ENCE
SENTTH IS JU SIS AS SE THUS

Check out my solution if you're still stuck.

Source:

import java.io.*;
import java.util.*;
 
class Node{
    HashMap<Character, Integer> children;
    int first =  0;
    int second = 0; 
     
    Node(){
        children = new HashMap<>();  
    }
    
    void init(){
        children.clear(); 
        first = 0;
        second = 0; 
    }
}

class TrieMap {
    static final int MAX = 500000; 
    static int gIndex;
    static Node trie[]; 
    static int count=0;
    
    public static void insert(String s, int type){  
        int cIndex = 0;
      
        for(int i=0;i<s.length();++i){
            char c = s.charAt(i); 
            Integer nIndex = trie[cIndex].children.get(c); 
            if(nIndex==null){ 
                    trie[cIndex].children.put(c, ++gIndex);  
                    if(trie[gIndex]==null)trie[gIndex] = new Node(); 
                    trie[gIndex].init();
                    cIndex = gIndex; 
                    nIndex = cIndex;  
            }else{
                cIndex = nIndex;  
            }
            
            if(type==1)trie[nIndex].first++; 
            else       trie[nIndex].second++;
        }  
    } 
    
    static int ans=0;
    public static int query(int cIndex, int depth){  
        
        int sub = 0;
        for(Map.Entry<Character, Integer> me:trie[cIndex].children.entrySet()){ 
            int value = me.getValue();
            
            if(trie[value].first>0 && trie[value].second>0){
                int r = query(value, depth+1);
                sub+=r;
                trie[cIndex].first -= r;
                trie[cIndex].second -= r;
            }
        } 
        int min  = Math.min(trie[cIndex].first, trie[cIndex].second); 
        if(cIndex!=0)ans+=depth*min; 
        return min+sub;
    } 
    
    public static void main(String[] args){
          
        trie = new Node[MAX];  
        
        while(true){ 
            int n = IO.nextInt();
            if(n==-1)return;
            trie[0] = new Node();
            trie[0].init();  
            count=0;
            gIndex = 0;
            for(int i=0;i<n;++i){
                String s = IO.nextString(); 
                insert(s, 1);
            } 
            ans=0; 
            for(int i=0;i<n;++i){  
                insert(IO.nextString(), 2);  
            }   
            query(0, 0);
            IO.println(ans);
        }
    }
    




    /***********************************IO***************************************/
    private static class IO {
        private static InputStream stream = System.in;
        private static byte[] buf = new byte[1024];
        private static int curChar, numChars; 

        private static int read() {
                if (numChars == -1)throw new InputMismatchException();
                if (curChar >= numChars) {
                        curChar = 0;
                        try {
                            numChars = stream.read(buf);
                        } catch (IOException e) {
                            throw new InputMismatchException();
                        }
                        if (numChars <= 0)return -1;
                }
                return buf[curChar++];
        }

        public static int nextInt() {
                int c = read();
                while (isSpaceChar(c))
                        c = read();
                int sgn = 1;
                if (c == '-') {
                    sgn = -1;
                    c = read();
                }
                int res = 0;
                do {
                    if (c < '0' || c > '9') throw new InputMismatchException();
                    res *= 10;
                    res += c - '0';
                    c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }

        public static char nextChar() {
                int c = read();
                while (isSpaceChar(c)) c = read();
                return (char) c;
        }
        
        private static String nextString(){
            int c = read();
            while(isSpaceChar(c))c=read();
            StringBuilder sb = new StringBuilder();
            do{
                sb.append((char)c);
            }while(!isSpaceChar((c=read())));
            return sb.toString();
        }

        private static boolean isSpaceChar(int c) {
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        
        private static void println(Object... a){
            for(Object o:a)System.out.print(o);
            System.out.println();
        }
    }
}

No comments:

Post a Comment