Discussion @ 1364. LaraKiller @ Timus Online Judge

Keworker `~ Overrated + Easy BFS // Problem 1364. LaraKiller 14 Aug 2024 11:05

It's strange that 1377 has 295 rating while 1364 has 953 rating. Solutions are almost same)

Sandro (USU) Problem 1364 “LaraKiller”. The statement was updated. [1] // Problem 1364. LaraKiller 6 Dec 2020 11:47

The original version of the statement was unclear, and not all the limitations were described in the input data format.

Both English and Russian version of the statement were updated.

Harkonnen Re: Problem 1364 “LaraKiller”. The statement was updated. // Problem 1364. LaraKiller 12 Aug 2022 10:38

It's still unclear what to output if Lara has enough time to escape (i.e. there is no reason to hide) - empty output? My AC solution ignores that case like if entrance is locked.

Artem Ladik wa on 6 test!!! [2] // Problem 1364. LaraKiller 16 Aug 2008 01:17

RASTA Re: wa on 6 test!!! // Problem 1364. LaraKiller 19 Mar 2009 15:10

check some tests
input
5 5
1 5
1 3
0
output
1 3

input
5 5
1 5
1 3
10000000
output
1 1
1 2
1 3
1 4
1 5

input
100 100
51 50
1 1
1000000
output
1 1
1 2
...
51 51
51 50
#10000 points

input
2 100
2 1
1 1
100000
output
1 1
1 2
...
1 99
1 100
2 100
2 99
...
2 2
2 1
#200 points

MOPDOBOPOT (USU) Re: wa on 6 test!!! // Problem 1364. LaraKiller 2 Aug 2012 16:36

Just check more carefully borders you print!
For example (Lara's position - T) can be less or equal to zero. Try this test:

2 2
2 1
2 1
4

Romow Peter Help me please, I am very stupid [1] // Problem 1364. LaraKiller 2 May 2007 02:10

I don't understand, why output have (2,3),(3,3),(4,3) graves? When Lara will dig out the second grave with treasure, she at once will go back, it is true?

jagatsastry Re: Help me please, I am very stupid // Problem 1364. LaraKiller 14 Feb 2008 02:00

I guess the statement "As soon as Lara finds the second treasure (and goes immediately to buy the usual bottle of champagne), a new alarm system (of "LaraKiller" brand) will be set off." should not be there in the question.
I wrote my program with the assumption that the alarm can ring even before Lara has found the treasure and i got AC 0.031.
I used recursion to do the whole thing(The problem reverts to a (N-2)X(M-2) cemetry problem after each round).

Krayev Alexey (PSU) that's icredible! why wa#1? (+) // Problem 1364. LaraKiller 17 Aug 2006 02:21

I checked, the 1st test is actually sample, but my program proccesses it correctly on my computer. then why wa1?

Edited by author 17.08.2006 18:58

test Why in the test 9 I'm have TLE? // Problem 1364. LaraKiller 23 Mar 2006 12:47

Fu Dong What does this problem mean??? [2] // Problem 1364. LaraKiller 14 May 2005 14:30

I'm sorry I don't understand this problem, who can explain it to me? Thank you.

Fu Dong I have understood! [1] // Problem 1364. LaraKiller 15 May 2005 18:02

With someone's help, I've understood the mean of this problem.

Silviu Ganceanu Re: I have understood! // Problem 1364. LaraKiller 5 Jul 2005 03:27

Can you explain me the problem? To be more specific, I don't understand what Lara does.

semiconductor I found some ambiguity of LaraKiller(1364) [2] // Problem 1364. LaraKiller 24 Apr 2005 20:15

The problem states:
"[output]The graves shall be sorted by the distance that Lara will have to run from this grave to the cemetry entrance."
But in the sample output:
####
5 2
5 1
4 1
3 1
2 1
2 2
2 3
3 3
4 3
####
Clearly (2,1) is the nearest grave to entrace (1,1), but it appears in the middle !
Another thing is: (4,3) has not been digged by the time Lara is detected. So Lara shouldn't have time to be able to be (4,3). But (4,3) is in the sample output.
I think before Lara is detected, she does a snake shaped traversal( (1,1)->(1,2)->(1,3)->(1,4)->(2,4)->... ), am I right?
And what is the right interpretation of this problem, please ?

Pavel Tolstikov Re: I found some ambiguity of LaraKiller(1364) [1] // Problem 1364. LaraKiller 25 Apr 2005 00:06

Lara runs through the underground passage she dugged before.
And "graves shall be sorted by the distance" through this passage. As you can see output is a part of passage.

Lara is detected only then she stoled treasure.

Lara does a right spiral traversal.

semiconductor Re: I found some ambiguity of LaraKiller(1364) // Problem 1364. LaraKiller 26 Apr 2005 17:58

Thanks Pavel, now I got ac. This problem is pretty easy after one figures out what it means

Style: flat | tree | nested
Thread Order: bubble | fixed

Discussion of Problem 1364. LaraKiller