10507 - Waking up brain

szymcio2001 · Post by **szymcio2001** » Mon Jun 16, 2003 2:22 pm

It seems to be an easy problem, but I steel get Wrong Answer. I simply use BFS, but I add the vertex to queue only if it is connected with three vericies I visited earlier. If the BFS doesn't visit all areas I output "THIS BRAIN NEVER..." otherwise I output the time that is needed to wake up the brain. Is this algorithm wrong or is there some tricky input? And if some edge is given in input more than once should I ignore each another or use all of them?

Adrian Kuegel · Post by **Adrian Kuegel** » Mon Jun 16, 2003 8:33 pm

First you should know that there are several test cases, even if the description doesn't say so. And there are inputs where the number of used letters for connections is smaller than n, like:
5
0
ABZ

Output: THIS BRAIN NEVER WAKES UP

szymcio2001 · Post by **szymcio2001** » Mon Jun 16, 2003 9:22 pm

Adrian Kuegel wrote:First you should know that there are several test cases, even if the description doesn't say so.

Thanks, my algorithm was correct but I did't consider that there could be more than one test case in the input. Now I got Acc.

hujialie · Post by **hujialie** » Tue Jun 17, 2003 4:48 pm

It's really a strange problem,why does't it tell us there is multiple input?
I got wrong answer 4 times until I saw the last post.

carneiro · Post by **carneiro** » Wed Jun 18, 2003 1:12 am

I got the same problem ...

But my question is to kuegel

How do you get to know ALL mistakes so soon ?

Adrian Kuegel · Post by **Adrian Kuegel** » Wed Jun 18, 2003 1:17 am

I don't know them soon. See the contest ranklist, I did a lot of submissions on problem A and H (H is 10507). I was almost sure my program for A was correct, so I began to check the input throwing a runtime error if something isn't correct.

carneiro · Post by **carneiro** » Wed Jun 18, 2003 1:32 am

Kuegel, what should be the answer for this input ?

6
11
HAB
AB
AC
AH
BD
BC
BF
CD
CF
CH
DF
FH
3
0
ABZ
4
0
ATJ
5
0
ABZ

szymcio2001 · Post by **szymcio2001** » Wed Jun 18, 2003 1:44 am

My finally accepted program gives:

Code: Select all

WAKE UP IN, 3, YEARS

WAKE UP IN, 0, YEARS

THIS BRAIN NEVER WAKES UP

THIS BRAIN NEVER WAKES UP

carneiro · Post by **carneiro** » Wed Jun 18, 2003 1:48 am

and does it skip lines for each output ?

Dominik Michniewski · Post by **Dominik Michniewski** » Wed Jun 18, 2003 7:47 am

Thanks Adrian, I got Acc too ... in contest appears message that problem A has more than one inputs in file, but nothing was posted about H ...

Finally I got one more input, on which my program fails:
5
6
ABC
AD
AE
BD
BE
CD
CE

WAKE UP IN, 1, YEARS

Best regards
DM

carneiro · Post by **carneiro** » Wed Jun 18, 2003 6:59 pm

argh, accepted .
I can't believe the problem was that I was not "reseting" the graph for each input

duhhhh

ok, thanls everyone.

sergio · Post by **sergio** » Sun Jun 22, 2003 11:33 pm

Hi,

I tried to solve this problem, but I only get WA

So, anyone can to put other test cases?

S

carneiro · Post by **carneiro** » Sun Jun 22, 2003 11:57 pm

Have you tried the input cases here in the forum ?

sergio · Post by **sergio** » Mon Jun 23, 2003 12:13 am

Yes, I have tried all input cases in the forum and I got the corret outputs.
All outputs in the forum are corret, aren't they??

S

carneiro · Post by **carneiro** » Mon Jun 23, 2003 12:58 am

yes, they are. At least the ones I posted.

Make you a huge test case, and post it in the forum, I can use my accepted program to give you the right output.