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 » Sun Jan 06, 2008 4:31 am

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 » Sun Jan 06, 2008 5:34 am

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 » Sun Jan 06, 2008 5:53 am

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 » Sun Jan 06, 2008 10:24 am

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 » Sun Jan 06, 2008 10:36 am

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 » Sun Jan 06, 2008 11:22 am

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 » Sun Jan 06, 2008 11:47 am

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 » Sun Jan 06, 2008 8:54 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:

Post by mf » Sun Jan 06, 2008 8:57 pm

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 » Sun Jan 06, 2008 9:11 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:

Post by mf » Sun Jan 06, 2008 9:12 pm

That's all correct.

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

Post by jvimal » Sun Jan 06, 2008 9:29 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:

Post by mf » Sun Jan 06, 2008 10:47 pm

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 » Mon Jan 07, 2008 4:40 am

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 » Mon Jan 07, 2008 8:05 am

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)”