getting nzec.. plz help...

I tried to run this program for the primedistance question asked in august 13 challenge… I just visited every node and checked it’s distance from every other node… it’s giving correct answers for some test cases that I tried but on submitting it, it’s showing nzec error… help plz… here’s the code…

 class CLASSNAME {
	static long total=0;
    public void solve(int testNumber, InputReader in, OutputWriter out) {
    	int n=in.readInt();
    	boolean[][] tree=new boolean[n+1][n+1];
    	boolean[] isPrime=IntegerUtils.generatePrimalityTable(100001);
    	boolean[] isVis;
    	for(int i=1;i<n;i++){
    		int a=in.readInt();int b=in.readInt();
    		tree[a][b]=tree[b][a]=true;
    	}
    	
    	for(int i=1;i<=n;i++){
    		isVis=new boolean[n+1];
    		recurse(tree,isPrime,isVis,1,i);
    	}
    	//out.printLine(total);
    	out.printLine((total/2)/((n*(n-1))/2.0));
    }
    static void recurse(boolean[][] tree,boolean[] isPrime,boolean[] isVis,int sum,int level){
    	if(isVis[level])return;
    	isVis[level]=true;
    	//if(level>=tree[0].length)return;
    	for(int i=1;i<tree[0].length;i++){
    		if(tree[level][i]){
    			if(isPrime[sum] && !isVis[i]){
    				total++;
    			//System.out.println(level+" "+i+" "+sum);
    			}
    			recurse(tree,isPrime,isVis,sum+1,i);
    		}
    	}
    }
}

Your code for input

3
1 2
2 3

returns 0.3333333333333333

while for

3
3 2
2 1

it returns 0.0, but it is the same tree…

1 Like

Please remove the tag ‘aug13’ from this. Don’t pollute the AUG13 editorial space.

I changed the code where i am getting input…
for(int i=1;i<n;i++){
int a=in.readInt();int b=in.readInt();
tree[Math.min(a,b)][Math.max(a, b)]=true;
}
but still getting wrong answer… :frowning:

What about

7
1 2
2 3
3 6
3 4
4 5
6 7

?

Graph is:

1 - 2 - 3 - 4 - 5
        |
        6
        |
        7

your code returns 0.42857142857142855, but I think it’s 10/21 = 0.4761904

2: 1-3, 2-4, 2-6, 3-5, 3-7, 4-6
3: 1-6, 1-4, 2-5, 2-7

it should be 12/21…isn’t it?
how does it come to 10??

I wrote all “prime paths” and there are 10 above…

you missed out 4-7 and 5-6

you are correct, but you found your problem also, the probability is 12/21 instead of 9/21…

now it’s giving nzec… :frowning:
check the code…i’ve edited it in the question itself…

editorial tag is for editorials not aug13 :wink:

1 Like

@betlista- very well said… :slight_smile:

1 Like