## 11380 - Down Went The Titanic

Moderator: Board moderators

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### 11380 - Down Went The Titanic

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Correct.

Check this one, too:

Code: Select all

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

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### Thanks!

Thanks for your test case! I got ac.

jvimal
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm

### Re: 11380 - Down Went The Titanic

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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm
mf wrote: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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Any maxflow algorithm will work.

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

jvimal
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm
mf wrote: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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
If you make and post some inputs, I can show the output of my accepted program for them.

jvimal
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm
mf wrote: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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
That's all correct.

jvimal
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm
mf wrote: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
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm
mf wrote: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
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm
mf wrote: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)