You are viewing a single comment's thread. Return to all comments →
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(); } }
Seems like cookies are disabled on this browser, please enable them to open this website
Wire Removal
You are viewing a single comment's thread. Return to all comments →
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