10507 - Waking up brain

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

10507 - Waking up brain

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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

User avatar
szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

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
New poster
Posts: 43
Joined: Thu Apr 17, 2003 10:24 am
Location: Shanghai,China

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. :cry:

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

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 ?
[]s
Mauricio Oliveira Carneiro

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

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
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

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
[]s
Mauricio Oliveira Carneiro

User avatar
szymcio2001
New poster
Posts: 38
Joined: Mon Dec 09, 2002 1:53 pm
Location: Poznan, Poland

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
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

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

and does it skip lines for each output ?
[]s
Mauricio Oliveira Carneiro

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

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.
[]s
Mauricio Oliveira Carneiro

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:

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
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

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

Have you tried the input cases here in the forum ?
[]s
Mauricio Oliveira Carneiro

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:

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
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

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.
[]s
Mauricio Oliveira Carneiro

Post Reply

Return to “Volume 105 (10500-10599)”