274 - Cat and Mouse

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

Moderator: Board moderators

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia

274

Post by arc16 »

is there any trick on this problem? i've got WA on this.
first, i search all the room visitable by the cat and put the flag on.
next, i just search all the room visitable by the mouse. If the room's flag is on then mouse can meet the cat. if later, the mouse starting room is visited by the mouse again, then the cat can walk between rooms without having to meet the cat.
my solution works with the sample test case and official test case (ACM94). Do i miss something here?

jingye
New poster
Posts: 21
Joined: Sat Sep 07, 2002 5:28 am

274 runtime error ?!

Post by jingye »

I keep getting runtime error for this problem. I do not think I am reading the input correctly. Can someone show me how to read the input for this problem?

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra »

Hi!


Look out... the input is tricky !!

There can be no mouse or cat doors....

So make sure that you have considered such a possiblity... (this was my mistake ..)

Good Luck ;-)

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

274 cat & mouse TLE

Post by titid_gede »

i cant believe i got TLE for this problem. i've use DFS and also Transitive Closure, both of them got TLE. Do you have any suggestion or sample critical input ?

with love & light

titid
Kalo mau kaya, buat apa sekolah?

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Try to use BFS (something like floodfill). I got 0.031 sec that way :wink:

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

well i use something like flood_fill too, but i think that's DFS. how can you got AC?
oke here is my code :
[c]
--- cut got AC----
[/c]
Last edited by titid_gede on Sat May 17, 2003 3:40 pm, edited 1 time in total.
Kalo mau kaya, buat apa sekolah?

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Don't expect any help from me when you give wrong information :evil:

I spent almost half an hour looking at your code trying to find the cause of the TLE that you said you had. Then I submitted your code to the judge and got WA in 0.045 sec!

I tried to help you, but was looking in the wrong direction because you gave me the wrong information.
Your code is correct in principle, but doesn't catch all tricky input. But I am not going to help you anymore.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

hey sorry i dont mean to give wrong information. i'm pretty sure that i got TLE because i submitted it several times. perhaps i removed / added some lines before i posted it ( i forgot). i dont know why i got WA now. please forgive me.

with love & light,

titid
Kalo mau kaya, buat apa sekolah?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede »

anyway thank you very muc, little joey. now i got AC. there is a small bug in my code. :) :)

with love & light,

titid
Kalo mau kaya, buat apa sekolah?

sawamura
New poster
Posts: 3
Joined: Thu May 29, 2003 1:23 pm
Contact:

274- Cat n Mouse - TLE

Post by sawamura »

somebodyyy helppp
i had tried 5 types of coding for this problem
using linked list.
but in the end , i got the same result.
TIME LIMIT EXCEEDED.

:(

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

Post by Dominik Michniewski »

I use two DFS and got Acc in 0.301 sec If I correct remember ...

Bets 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)

sawamura
New poster
Posts: 3
Joined: Thu May 29, 2003 1:23 pm
Contact:

Post by sawamura »

:)
thanx
i used 2 DLinked list, or he cat n the mouse
i tried the sample case from the web
n i got the correct answer.
but now when i submit it , WRONG ANSWER.

"Your program has not solved the problem. It ran during 6.598 seconds"
i wanna ask
1. the problem said that the first answer is 'y' if the cat can meet the mouse in some room. is it means there shoud be more than 1 room where they can meet each other (2 rooms or above) to get the first 'y'?
2. can the cat meet the mouse in the mouse first room or can the cat enter the mouse room?


i already test my source code in thousands of case n i think i got the right answers for all of them. but its still wrong answer in the end
i assume that in the cat's first room, there is a cat.
so if the case is:

2
10 1 2
-1 -1
2 1
1 2

100 50 50
-1 -1


the answer is
"y n" -->or "n n" how many meeting rooms required to get the first 'y'?????
and for the seccond case
"y n" -->or "n n" ?????????????


can somebody help me with some other sample case??
pleaaseeeee
i just wanna make sure that i am right
thanxxx.

sawamura
New poster
Posts: 3
Joined: Thu May 29, 2003 1:23 pm
Contact:

Post by sawamura »

HORRRREEEYYYYYYY!!!!!!
i finally got accepted :D
even it's still PE
heheheheh
thanxx for your help :)
arigato!

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

Post by szymcio2001 »

For all who still have TLE:
My problem was that I thought that there must be a blank line after description of mouse doors, but there needn,t.

fpavetic
Learning poster
Posts: 51
Joined: Sat Mar 04, 2006 8:00 pm

WA

Post by fpavetic »

hello,
i am constantly getting wa with this problem :( so can somebody please help?

is the input realy in this format?

number_of_test_cases
blank_line
rooms cat_start mouse_start
list of cat edges
-1 -1
list of mouse edges
blank_line
the same for next case

i consider following tricky cases:
- cat and mouse have the same start room: Y N
- there are no cat or mouse edges

are there more tricks? thank you

Post Reply

Return to “Volume 2 (200-299)”