ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1315. MDPAR and MIIAR

HINT: Instructions to the problem statement.
Posted by TestKiller 3 Sep 2010 21:57
Finally I got AC.

The English statement is so confused that I feel it necessary to make something clear here.

1 What does SURFACE mean?
The surface means the uppermost row, in the other word, the row above the first input row. ONLY this row could be regarded as the surface. It means, the water could only pour in from these 'holes', and the man will rescue if he could reach the uppermost row.

2 What does the STARTING POINT mean?
The starting point could be ANYWHERE in the cave, even could be a BLOCKED cube (the cube with '#')(Test #22).
When we got the coordinate of the starting point, first notice that the Y-coordinate begins from the bottom. Then, you should do searching. Here:
(1) DO NOT think a blocked starting point means "rescue operation required". Just regard it as a empty cell and continue.
(2) When the man starts, he is at the starting point. Now he have just D-cube breaths, not D-1. That means the following testcase is correct:
3 3 2 1 3
#.#
#.#
#.#
Can be rescued by himself.
SO, IN ONE WORD, the starting point, although may be blocked or flooded with water, we can regard it as a place to breath as if it is empty without water.

3 How long could he stay in water?
Through D cubes. If you look at the samples carefully, you will get the answer, without the mistake of D and D-1.

4 What does "Here only the paths having no downward segments are considered" in statement mean?
It means the water could only flow lower and lower, not higher in any cases. So, in the sample data, the (5,3) cube will not be flooded with water and this cube can be used to breathe.

5 What does "It is known that a speleologist can reach the surface while cave is not filled with water." in statement mean?
It means there exist a path from the starting point to the surface. If there is no water, or the man has infinite breathe, he could reach the surface.

6 What is the time complexity of the problem?
O(W*H) could be achieved, though O(W*H*D) might have AC, too.

Hope the instructions above could help someone in trouble.
Re: HINT: Instructions to the problem statement.
Posted by † SiriuS † [TWYT Union] 12 Dec 2014 08:15
Tnx:). It's clear now!