Critical tests..

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Zyaad Jaunnoo
Experienced poster
Posts: 122
Joined: Tue Apr 16, 2002 10:07 am

Critical tests..

Post by Zyaad Jaunnoo »

I think that many of the algorithms that we develop are correct for general cases but usually fails for simple & critical tests.

for example:
1! = 1
0! = 1

So how do we identify the critical tests?
Can someone help please?

JackBauer
New poster
Posts: 19
Joined: Sun Mar 21, 2004 8:07 pm

Post by JackBauer »

I am not really experienced, and sometimes fail to those limit conditions, but here are a few things.

I think it's related to the limits of the problem. In example, some problem that requires a calculation on a given input N (integer between -3 and 33). In this case -3 and 33 would be the limits.

Pay attention to _off by one errors_ in things like (<= vs < and so on). Regarding this, things like "between 10 and 30" may be 11-29 so pay attention to the exact wording and so on. Another example: Dates can get messed up by a few seconds extra or less when constructing a timestamp.

Still I think the biggest problem is unexpected stuff in input, wich in some problem's is not known in advance / they don't say it may appear (leading zeros and spaces and so on).

TopCoder problems seam to be a little better in discribing input.

yaro
New poster
Posts: 17
Joined: Sat Jan 03, 2004 3:18 pm
Location: Poland

Post by yaro »

JackBauer wrote: TopCoder problems seam to be a little better in discribing input.
That's right but consider that TopCoder matches have quite different rules about "getting accepted".

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Re: Critical tests..

Post by stubbscroll »

Zyaad Jaunnoo wrote:I think that many of the algorithms that we develop are correct for general cases but usually fails for simple & critical tests.

for example:
1! = 1
0! = 1

So how do we identify the critical tests?
Can someone help please?
Some examples of critical tests:

- angles near 0 or 360 degrees in geometry problems
- printing -0.000 (floating point output) when answer should be 0.000
- 0 things taken from 0 is 1
- input of 0
- in BFS problems, start state == end state
- not really a critical test, but a common mistake is overflow in intermediate calculations (int->long long)
yaro wrote:
JackBauer wrote: TopCoder problems seam to be a little better in discribing input.
That's right but consider that TopCoder matches have quite different rules about "getting accepted".
Not really, one incorrect output to a test case and the submission gets a score of 0. In UVa/ACM we can at least try to correct the mistake after getting WA. The things I like about topcoder problems is that input/output handling is much easier (parameters/return value), and there's a lot of sample input/output with explanations.

Post Reply

Return to “Algorithms”