on what test cases code is failed for poblem walk on binary tree?

general
1

Home » Walks on the binary tree » All Submissions » yogi10 [15066666]
Solution: 15066666
CodeChef submission 15066666 (JAVA) plaintext list. Status: WA, problem WALKBT, contest CODECHEF. By yogi10 (yogi10), 2017-08-21 22:13:06.
import java.util.Scanner;
import java.lang.Math;
class node
{
node left;
node right;
}
public class Main
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int t,q,cnt=1;
int n;
long x;
char ch;
t=sc.nextInt();
while(t–!=0)
{node root=new node();
cnt=1;x=0;
n=sc.nextInt();
q=sc.nextInt();
while(q–!=0)
{
ch=sc.next().charAt(0);
if(ch==’!’)
{int k=0;
int i=n-1;
byte []s=new byte[n];
int c;
c=sc.nextInt();
x=(x+(int)Math.pow(2,c))%(int)Math.pow(2,n);
long y=x;
while(y!=0)
{
s[k++]=(byte)(y%2);
y/=2;
}
node temp=root;
while(i>=k)
{
if(temp.left==null)
{
temp.left=new node();
cnt++;
}
temp=temp.left;
i–;
}
while(k–!=0)
{
if(s[k]==1)

{
    if(temp.right==null)
    {
        temp.right=new node();
        cnt++;
    }
temp=temp.right;
}
else
{
if(temp.left==null)
        {
         temp.left=new node();
         cnt++;
        }
temp=temp.left;
}
}
}
else
System.out.println(cnt);
}
}
}
}
 
Submission Info:
Sub-Task	Task #	Score	Result
(time)
1	0	NA	AC
(0.070000)
1	1	NA	AC
(0.070000)
1	2	NA	WA
(0.150000)
1	3	NA	WA
(0.160000)
1	4	NA	WA
(0.200000)
1	5	NA	WA
(0.180000)
1	6	NA	WA
(0.200000)
Final Score - 0.000000	Result - WA
2	7	NA	TLE
(6.010000)
2	8	NA	TLE
(6.010000)
2	9	NA	TLE
(6.010000)
2	10	NA	TLE
(6.010000)
2	11	NA	WA
(5.880000)
2	12	NA	WA
(3.360000)
2	13	NA	AC
(5.500000)
Final Score - 0.000000	Result - TLE
2

ctrl + A then ctrl + v of your solution page? give some clarity to your code!

3

In the initial phase, I think you won’t need any specific test cases now since your code will break in almost all test cases. Reason being the case that you are literally calculating 2^{c} where c \in [1,100000). I am saying this because 2^{100000} is like shifting the MSB 100000 times towards left. On a 64-bit machine, you can at most left shift by that many bits after which it starts overflowing. Then you have typecasted the result to (int) which further reduced the exponential value. This would lead to the wrong result since you are using the wrong x to start with.

You can start with how to handle or store such big numbers if you want to go via that route.