Sort by

recency

|

19 Discussions

|

  • + 1 comment

    Test case 18,30 and 50 are failing any one has idea?

  • + 0 comments

    Can any one help how to find probability?

  • + 1 comment

    Hello Everyone!

    First post on here so please be gentle.

    I've posted my code below, and would like some suggestions how to optomise it. (I'm aware that it's a pretty basic solution).

    I'm passing the first 10 or so test cases but getting all the later ones wrong.

    Carl

    import java.io.*;
    import java.util.*;
    import java.text.*;
    import java.math.*;
    import java.util.regex.*;
    
    public class Solution {
        
        public static int setLeafHeight(int element, int[] parentTree){
            if(parentTree[element] == 0){
                return 0;
            }
            return setLeafHeight(parentTree[element], parentTree) + 1;
            
        }
              
        
        public static int[] findHeights(ArrayList<Integer>[] tree, int[] parentTree){
            int[] heights = new int[tree.length];
            
            for(int i=tree.length-1; i>0; i--){
                if(i==1){
                    heights[i] = 0;
                }
                else if(tree[i].size() ==0){
                    heights[i] = setLeafHeight(i, parentTree);
                }
                else{
                    int max = 0;
                    for(int j=0; j<tree[i].size(); j++){
                        if(heights[tree[i].get(j)]>max){
                            max = heights[tree[i].get(j)];
                        }
                    }
                    heights[i] = max-1;
                }
            }
            
            return heights;        
        }
        
        public static int findSize(int element, ArrayList<Integer>[] tree){
            int size = 1;
            
            if(tree[element].size() == 0){
                size = 1;
            }
            
            else{
                for(int i=0; i<tree[element].size(); i++){
                    size += findSize(tree[element].get(i), tree);
                }
                
            } 
            
            return size;
            
        }
        
        public static int[] findTreeSize(ArrayList<Integer>[] tree){
            int[] sizes = new int[tree.length];
            for(int i=tree.length-1; i>0; i--){
                
                
                if(tree[i].size()==0){
                    sizes[i] = 1;
                } else {
                    sizes[i] = findSize(i, tree);
                }
            }
            return sizes;
        }
        
    
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            int n = in.nextInt();
            ArrayList<Integer> tree[]=new ArrayList[n+1];
            int[] parentTree = new int[n+1];
            
            for(int i=1; i<=n; i++){
                tree[i] = new ArrayList<Integer>();
            }
            
            
            for(int a0 = 0; a0 < n-1; a0++){
                int x = in.nextInt();
                int y = in.nextInt();
                
                tree[x].add(y);  
                parentTree[y] = x;
            }
                   
            
            int[] heights = findHeights(tree, parentTree);
            int[] sizes = findTreeSize(tree);
            
            
            int sumOfHeights = 0;
            for (int j = 1; j<heights.length; j++){
                sumOfHeights += heights[j];
            }        
            
            double treeLost = 0;
            for(int k=1; k<tree.length; k++){
                for (int l=0; l<tree[k].size(); l++){
                
                treeLost += ((heights[tree[k].get(l)])/(double)sumOfHeights)*sizes[tree[k].get(l)];
    
                }
            }
            
            double treeLeft = ((double)n-treeLost);
            
            System.out.println(treeLeft);
            
    
            in.close();
        }
    }
    
  • + 1 comment

    Can anyone help me with this ?

    I am getting 5 testcases wrong. Is it only because of the precision or something else?

    import java.io.*;
    import java.util.*;
    import java.text.*;
    import java.math.*;
    import java.util.regex.*;
    
    public class graph {
    
        int n,e;
        HashMap<Integer,ArrayList<Integer>> list = new HashMap();
        boolean v[];
      static  int distance[];
        
        //Constructor takes input
        graph(){
           
           n = i();      //no of nodes 
           e = n-1;      //no of egdes
           
           
           for(int i=1;i<=n;i++)
           list.put(i,new ArrayList());    
               
               for(int i=0;i<e;i++)               //creating adjacency list
           {
                int a = i();
                int b = i();
               
                list.get(a).add(b);
                list.get(b).add(a);
           }
           
           v = new boolean[n+1];
           cl = new int[n+1];
           distance=new int[n+1]; 
           distance[0]=0; 
        }
        
        public int dfs(int root)
        {
            v[root] = true;
            ArrayList<Integer> ar = list.get(root);
            int c=1;
            for(int i=0;i<ar.size();i++)
            {
                int node = ar.get(i);
                
                
                if(!v[node])      // if element is not visited
                {
                    distance[node]=distance[root]+1;
                    c+=dfs(node);
                }
            }
            cl[root]=c;
            return c;
        }
        
        static int cl[];    
        
        public static void main(String[] args) {
            
           PrintWriter out=new PrintWriter(System.out); 
           graph g = new graph();
           int root = 1;
           g.dfs(root);
            
           double dd = 0.0d;
           double totaldist=0.0d;
            
           for(int i=2;i<=g.n;i++)
           {
               //System.out.println(i+" "+g.cl[i]+" "+distance[i]);
               dd += (g.n-g.cl[i])*distance[i];
               totaldist+=distance[i];
           }
           
             
            // out.printf("%.14f\n", dd/totaldist);
             System.out.print(dd/totaldist); 
         //  System.out.print(dd/(g.n-1));
        }
        
        
       static Scanner sc = new Scanner(System.in);
      
       static long l(){
            return sc.nextLong();
        }
        static int i(){
            return sc.nextInt();
        }
        static String s(){
            return sc.nextLine();
    }
    }
    
  • + 1 comment

    can anyone done it in java ???