11380 - Down Went The Titanic

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11380 - Down Went The Titanic

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

Post by mf »

Correct.

Check this one, too:

Code: Select all

3 4 1
*@##
*@~#
*@~~
Answer: 3

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

Thanks!

Post by baodog »

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

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

Post by 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
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm

Post by jvimal »

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:

Post by mf »

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

Post by jvimal »

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:

Post by mf »

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

Post by jvimal »

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:

Post by mf »

That's all correct.

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

Post by jvimal »

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:

Post by 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
New poster
Posts: 16
Joined: Tue May 08, 2007 6:27 pm

Post by jvimal »

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

Post by jvimal »

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)
  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... :)

Post Reply

Return to “Volume 113 (11300-11399)”