WA ADAIndex

[vaishcr7]

Was getting nzec and wa earlier due to I/O related issues.

AC now. Thanks to simes for bearing with me.

[simes]

I don’t know Java, but I had the same kind of problem when coding with Free Pascal.

I discovered that all the newing of trie nodes was relatively slow. So now when I use a trie, I create a static array of trie nodes, and allocate the elements of that array instead of newing them. I just keep a variable with the last used index.

YMMV.

[vaishcr7]

I have changed tle to WA. Any suggestions now.

[simes]

Yes, the usual process:

1. Find a test case where you get the wrong answer.
2. Debug the code to find out why you get the wrong answer.
3. Change the code so you no longer get the wrong answer.

[vaishcr7]

Sure, that was easy. I have already tried everything i can think of . It’s just a simple trie implementation so I don’t know what is so wrong with my code. I even stored all the matching strings at each level for easy debugging but I couldn’t find any issue. Can you check if question wants me to print in some other format maybe related to newlines or spaces.

[simes]

Once I commented out the debug statements, the program didn’t output anything at all. Please could you show the code you actually submitted?

[simes]

I can’t find a test case where your code gives the wrong answer.

My only suggestion is to remove the exception ignoring - perhaps something is going wrong, and you don’t know it?

[vaishcr7]

the fast I/o class I am using is a checked exception so I can’t remove it and using normal scanner for input causes TLE.
Also I didn’t understand why they specified the length of all words <10^6 ?
The output format is correct right ?

[simes]

But do you need to ignore the exception? Can’t you re-throw it? or throw another? At least then you’d know something was not as you expected.

Length of all words <10^6 tells you how many trie elements you need.

The output format looks ok to me. Are you removing the line feed after the final test case? There’s no need to.

[vaishcr7]

After removing return, spoj did give a nzec. I will try to see why now. Can it be related to heap space for java. I also removed the extra list of words that i had introduced for devugging . It did reduce the memory consumption 10 times but still runtime error (NZEC) .
But in other questions this has happened too when I used this method of i/o . And after just returning , i used to get AC. Like CSTreet and other questions. Still I will try some far fetched test cases.

[simes]

String []s=sc.readLine().trim().split(" ");
n=Integer.parseInt(s[0]);
q=Integer.parseInt(s[1]);

This kind of thing is fragile, all it takes to break it is an extra space in the input. Try using the nextInt function.

[vaishcr7]

updated the code for nextInt(). Same thing again. I just got an AC for blinnet . In that I faced no issues like this.

[vaishcr7]

found the issue. readlIne() is the culprit . i get outof index exception for large test cases but i can’t increase the buf array size as it will cause tle then. Guess this question is not made for java.

[simes]

Or try increasing the buffer size from 64.

[vaishcr7]

allready tried that.

[simes]

Did you try 10^6+1? I wouldn’t put it past Morass to test a single item with the maximum length.

[vaishcr7]

Tle with buffer 10^6, and nzec with any lesser powers of 10.

[simes]

A bit of asserting shows that all the words are shorter than 20 characters,.

[vaishcr7]

Sorry for the delay. I didn’t get what you meant there.

[simes]

I used assert statements to discover that none of the words in the list are longer than 20 characters,