11380 - Down Went The Titanic

[baodog]

Is the following correct?

Code: Select all

3 5 2
##@**
.~*~.
.....

3 5 2
##.**
.~*~.
.....

3 5 2
##.*.
.~*~~
.....

Code: Select all

3
2
2

Any tricky cases? I keep get wa. Thanks.

[mf]

Correct.

Check this one, too:

Code: Select all

3 4 1
*@##
*@~#
*@~~

Answer: 3

[baodog]

Thanks for your test case! I got ac.

[jvimal]

What is the idea for this problem?

I guess we can formulate it as a maxflow. We have both vertex capacities and edges capacities here. And, the main problem is the condition:

Two people cant be on the same iceberg at the same time.

How can I incorporate that condition into maxflow if there is no time in the state?

Thanks,

[mf]

Just ignore it - time doesn't matter.

In this problem people can stay at the same place for any period of time and nothing bad will happen. So, you could make people move to their destinations by one person at a time, and in this scenario no two persons would ever be at an iceberg at the same time.

[jvimal]

Just ignore it - time doesn't matter.

In this problem people can stay at the same place for any period of time and nothing bad will happen. So, you could make people move to their destinations by one person at a time, and in this scenario no two persons would ever be at an iceberg at the same time.

Ah yes, ... but in this case, I guess this approach would work:

Find the shortest path from each person to one of the wooden planks. since each wooden plank has a maximum capacity of P, the only thing we have to minimize in the path is the number of ices plates broken.

So, if we do the above shortest path for each person, repeatedly, and then updating the vertex capacities, it should give the right answer.

But what I said above is the shortest augmenting path algorithm for maxflow, am I right?

[mf]

Any maxflow algorithm will work.

To handle vertex capacities, just use the usual trick - split each vertex into two.

[jvimal]

Any maxflow algorithm will work.

To handle vertex capacities, just use the usual trick - split each vertex into two.

Hi, could you give some more cases?
I tried many examples... Still couldnt find the bug

[mf]

If you make and post some inputs, I can show the output of my accepted program for them.

[jvimal]

If you make and post some inputs, I can show the output of my accepted program for them.

Code: Select all

3 3 1
*.*
@#@
*.*
Ans: 1

1 12 1
*#*#*#*##***
Ans: 5

2 12 1
*~*~*~*~#***
..@.@@@@.@@@
Ans: 1

2 12 2
*~*~*~*##***
..@@@@@@.@@@

Ans: 4

Thanks!

[mf]

That's all correct.

[jvimal]

That's all correct.

Okay. I tried many more, got them right.
Let me explain the connections in the graph.

Each cell is a vertex. With a vertex capacity for
1. # => infi
2. @ => inf
3. "." => 1
4. * => 1
5. ~ => 1

Now, create a digraph where there are connections between
. and # @ . of capacity 1
. and * of cap 0
* and . of cap 1
* and # @ of cap inf
* and ~ or * of cap 0

# and # or @ of cap inf
# and . of cap 1
# with others of cap 0

@ and * of cap 0
@ and others cap inf

and (anything and ~) of cap 0
...
Edge capacities, I felt, were required. And not just vertex capacities...

Now, according to the vertex splitting method:
if u,v is an edge:
cap 2u, 2u+1 = vertex_cap u
cap 2u+1, 2v = cap u, v

cap v, 2v+1 = vertex_cap v

and no back edge.

now, edge between # (the odd numbered part) and sink is of capacity P,
edge between src and persons of cap 1.

Did I go wrong in the formulation?

[mf]

It seems correct to me.
But you could make it simpler - set all edge capacities to infinity, except for those which connect to ~ cell.

[jvimal]

It seems correct to me.
But you could make it simpler - set all edge capacities to infinity, except for those which connect to ~ cell.

Hmm, but if I do that, for this case:

Code: Select all

3 5 2
##.**
.~*~.
.....

I am getting an answer of 3. It should be 2.

[jvimal]

It seems correct to me.
But you could make it simpler - set all edge capacities to infinity, except for those which connect to ~ cell.

Thanks mf, I got it AC.

I just re-read my program (damn, I should do it properly next time), and the mistake I did was:

Code: Select all

for all vertices u,v:
  add (2u,2u+1) with vcap(u)
  add (2v,2v+1) with vcap(v)
  add(2u+1,2v) with edgecap(u,v) 

This is wrong because, I am re-adding

Code: Select all

  add (2u,2u+1) with vcap(u)
  add (2v,2v+1) with vcap(v)

for every edge that goes out of u And since the graph implementation took a vector, the edges were duplicated :'(

Silly mistake...