10675 - Revenge of Faucet Flow

[Dreamer#1]

The problem description says:

"Water pours from the faucet at a rate of 1 cubic unit per second."

"You may assume that the water behaves ideally: it instantly spreads out across any flat surface, spilling over all adjacent edges at an equal rate of flow."

"Finally, M lines with N integers are given, specifying the height of each square in the aquarium."

"Print your answer accurate to two decimal places."

How can we have a fractional answer?

A sample I/O case with fractional answer would be really nice.
I must be missing something silly.
Someone please enlighten me.

Thanks in advance.

-Dreamer

[Yarin]

This case for instance

6 5
4 3
9 4 9 5 9
9 0 8 0 9
9 0 9 0 9
9 8 9 8 9
9 9 8 8 9
9 9 9 9 9
0 0

[rotoZOOM]

This case for instance

6 5
4 3
9 4 9 5 9
9 0 8 0 9
9 0 9 0 9
9 8 9 8 9
9 9 8 8 9
9 9 9 9 9
0 0

After 1 sec: (2,2) (3,2) (2,4) and (3,4) filled on 1/4 cubic
After 2 sec: (2,2) (3,2) (2,4) and (3,4) filled on 1/2 cubic
After 3 sec: (2,2) (3,2) (2,4) and (3,4) filled on 3/4 cubic
After 4 sec: (2,2) (3,2) (2,4) and (3,4) filled on 1 cubic
Now we can say after 4 sec units at element (2,2) (3,2) (2,4) and (3,4) become 1 (not 0).
After 8 sec they become 2.
After 12 sec they become 3.
And finally, after 16 sec they become 4 and water through unit (1,2) flow out.
My reasoning is when we pour water to unit (4,3), it flows to units (4,2) (4,4) (5,3) then it flows to less volume units.

What wrong ?

THanks in advance.

[Adrian Kuegel]

You missed that the water take the way (4,3) -> (5,3) -> (5,4) -> (4,4)
Other ways are:
(4,3) -> (3,3) -> (2,3)
(4,3) -> (3,3) -> (3,2)
(4,3) -> (3,3) -> (3,4)
But I am not sure myself how to calculate how much water each square gets in one second.
Maybe it is like this:
There are 6 edges down from (3,3), (4,3)
so (2,4) and (3,4) should get together (1/6 + 1/6 + 1/6 + 1/12)
and (2,2) and (3,2) together (1/6 + 1/6 + 1/12)
so it takes 17.14 seconds to reach height 5 in (2,4) and (3,4)
and it would take 19.2 seconds to fill (2,2) and (3,2) to height 4.
So answer would be 17.14.

[Yarin]

Yep, 17.14 is correct. It's a tricky problem, one has to carefully think through the simulation. It's not too hard to code it once you've figured out the simulation.

[coconut]

Hi,

I got W.A. though I did follow your approach

But I still need some clearance...May I know what is the answer for the test case below please? Would be 0.00 or 3.00?

Thanks a lot.

Code: Select all

5 5
3 3
4 4 4 2 4
4 1 2 2 4
3 2 4 2 4
4 1 2 1 4
4 4 4 4 4

[Adrian Kuegel]

The answer should be 0.00

Here are some additional test cases to check your program:

Code: Select all

5 5
3 3
0 0 0 0 0
0 2 2 2 0
0 2 1 2 0
0 2 2 2 0
0 0 0 0 0
5 3
2 2
5 5 5
5 0 5
5 2 5
5 0 5
5 1 5
5 3
3 2
5 5 5
5 0 5
5 2 5
5 1 5
5 2 5
4 5
2 3
5 5 5 5 5
1 0 4 3 5
5 5 3 2 3
5 5 5 5 5
0 0

Answer should be:
1.00
3.00
2.00
1.50

[coconut]

Thanks Adrian Kuegel a lot for your kindness. My answers are all same to yours. However I still got stuck at this problem (W.A )

Can u please check for me for the following test case?

Code: Select all

6 5
3 3
3 3 3 3 3
3 3 2 2 3
3 1 4 1 3
3 1 3 1 3
3 1 1 2 2
3 3 3 3 3
0 0

My answer is 3.43

If it is also correct, maybe there're some very very hidden problems that I cannot discover I've covered all the matter of precision, initialization...

[Per]

3.43 is correct.

Here is the test case that made me realise my mistake on this problem:

Code: Select all

8 8
4 4
8 8 8 8 8 8 8 8
8 5 3 5 5 5 5 8
8 5 5 5 5 5 5 8
8 5 5 5 5 5 5 8
8 5 5 5 5 5 5 8
8 2 5 5 5 5 0 8
5 2 5 5 0 0 0 4
8 8 8 8 8 8 8 8

The answer should be 18.00