11434 - Careless Postman Problem

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

Moderator: Board moderators

Post Reply
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

11434 - Careless Postman Problem

Post by sclo » Mon Mar 31, 2008 6:28 am

I am trying to solve this problem using min cost flow, but I don't quite understand the 3rd sample testcase.

Code: Select all

2 2
1 2 1 1 0
2 1 1 1 0
Why is the result 2?
Shouldn't it be Impossible, since qi>pi?

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Mar 31, 2008 6:51 am

There was a clarification that the third case should be:

Code: Select all

2 2
1 2 1 1 1
2 1 1 1 1
-----
Rio

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Mar 31, 2008 9:30 am

rio wrote:There was a clarification that the third case should be:

Code: Select all

2 2
1 2 1 1 1
2 1 1 1 1
-----
Rio
Ok, now I don't understand why I keep getting WA.
Basically, I convert each edge into an edge with 0 as lower capacity and p-q as upper capacity, and I adjust the supply/demand on the vertices accordingly. I create a new source and connect it to all the supply vertices, and connect all demand vertices to the new sink.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Mar 31, 2008 5:12 pm

Well, I did the same thing. And this solution has a problem.

I didn't notice that this solution is not correct until reading the discussion on the top coder forum.
It fails on case:

Code: Select all

1
4 6
1 2 1 1 2
2 1 1 1 2
3 4 1 1 2
4 3 1 1 2
2 4 1 0 1
3 1 1 0 1
The correct answer is 8 but my code outputs 4.

Anyway, since my code got AC, the judge solution seems to did the same thing (or maybe I was just lucky).
So, I don't know where the problem is. Maybe your code is calculating the true answer. or maybe some bug in your code.
-----
Rio

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Re: 11434 - Careless Postman Problem

Post by sclo » Tue Apr 01, 2008 4:50 am

I'm starting to think that the judge input contains bugs.
I used

Code: Select all

assert(u>=1 && u<=n);
assert(v>=1 && v<=n);
and it gave run time error.

Post Reply

Return to “Volume 114 (11400-11499)”