## 10983 - Buy one, get the rest free

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

Moderator: Board moderators

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan

### 10983 - Buy one, get the rest free

please suppose some useful I/O

I've tried to generate some but no use

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
I really need some I/O too
Crazy with WAs...

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
what's the time complexity of your algorithm ?

my one is of O(lgm * (m + x)), where x is the running time of Edmons-Karp Algorithm.
That is to say, I runned a maxflow algorithm O(lgm) times.

I got TLE.
should I use more fast maxflow algorithm, like a Relabel-To-Front O(V^3) or Preflow-Push algorithm O(V^2 * E) ?
since V is near 330, i think it can be slow too....

Sorry For My Poor English..

polone
New poster
Posts: 43
Joined: Sun May 08, 2005 2:31 am
Location: Taiwan
yes I agree that you shoule implent O(v^3) algo

since the number of edges is very big...

mine program is O(m*(n*d)^3)

using relabel-to-front

without bsearch

WA I'm thinking about the accuracy of my algo

If you know the actually relabel-to-front algo please send me a message about websit or code about the algo

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
There is no need to implement the complicated push-relabel. There is another algorithm that is also O(n^3), but is much, much, MUCH simpler to code. It's called Dinic's algorithm, and consists of Ford-Fulkerson, plus 1 extra line.

I have an implementation here:
http://shygypsy.com/tools
but please, don't just copy-paste it to solve this problem. ;-) Understand how it works.
If only I had as much free time as I did in college...

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
Abednego wrote:There is no need to implement the complicated push-relabel. There is another algorithm that is also O(n^3), but is much, much, MUCH simpler to code. It's called Dinic's algorithm, and consists of Ford-Fulkerson, plus 1 extra line.

I have an implementation here:
http://shygypsy.com/tools
but please, don't just copy-paste it to solve this problem. Understand how it works.
It seems very nice !

my implementation of push-relabel(or, relabel to front method) is very very very long and complicated !!
Your source code looks very fascinating, but I can't understand why it works in O(n^3) time.

As I searched some related informations in google,
some results say that the Dinic's Algorithm is of O(mn^2) time complexity, and that it's can be made in O(nm lgn) using another special data structures.

can you explain more detail for me, please?

Thanks.
Sorry For My Poor English..

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Sorry, you are correct.

The longest possible augmenting path has length n-1, where n is the number of vertices. Dinic's algorithm proceeds as follows:
1. BFS from S until we reach T at depth D (depth is measured in the number of edges).
2. If we cannot reach T, return.
3. Find a maximal set of augmenting paths of length D.
4. Goto step 1.
The total running time is O(mn^2).

However, in practice, Dinic's algorithm beats push-relabel. Look at this paper:

Code: Select all

``````Cherkassky and Goldberg, "On implementing push-relabel method for the maximum flow problem," Technical report. Stanford, CA, USA, 1994.
``````
Basically, they show that the only way for push-relabel to beat Dinic's algorithm is when they use "gap relabelling" or "global relabelling", which are two heuristics, and even in that case, it wins by a small margin even on huge graphs with n=100000.

For any problem that you might see in an ACM competition, there is almost no chance that you will find a test case on which push-relabel works faster than the O(mn^2) Dinic's.

Frank Chu implemented push-relabel, and it took him a long time to get the heuristics working before his code ran as fast as mine on a dense graph of 2000 vertices. At that point, reading the input was taking more time than finding the maximum flow.
If only I had as much free time as I did in college...

hoho
New poster
Posts: 3
Joined: Fri Jul 22, 2005 5:08 am
The input description included:
Day 0 is today, and all of the participants need to be in city n in the evening of day e.

What does it mean??

I think the e should be d.

I wrote my program as it is d but always got WA.
Who could give me more input/output?? Thanks.

What is the output when only one city??
I think the output should be 0. Am I right?

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
You are right. It should say
Day 0 is today, and all of the participants need to be in city n in the evening of day d.

When there is only one city, the answer is 0.
If only I had as much free time as I did in college...

FAQ
Learning poster
Posts: 84
Joined: Wed Jan 28, 2004 6:23 pm
Wow, your tools are really cool !!

I have checked my program with some special tests

1 1 0
100
output : 0

5 5 0
0 0 0 0 100
output : 0 (all passengers are already in the destination)
... But I still WA :'( ( the time running is ok )

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Abednego wrote:However, in practice, Dinic's algorithm beats push-relabel. Look at this paper:

Code: Select all

``````Cherkassky and Goldberg, "On implementing push-relabel method for the maximum flow problem," Technical report. Stanford, CA, USA, 1994.
``````
Basically, they show that the only way for push-relabel to beat Dinic's algorithm is when they use "gap relabelling" or "global relabelling", which are two heuristics, and even in that case, it wins by a small margin even on huge graphs with n=100000.
That is not the interpretation I got from their paper, they don't even use any push-relabel methods without heuristics in their comparisons. In fact, they go so far as to say:
Cherkassy and Goldberg wrote:The push-relabel method is superior to Dinitz' method in practice, often by a wide margin when the global and gap relabeling heuristics are used.
And though I believe this comment is a bit exaggerated and that their earlier comment that vanilla push-relabel has poor practical performance is closer to the truth (though that is of course also relative, it sure beats vanilla ford-fulkerson most of the time), I cannot agree with your interpretation of their paper above. (Though I only browsed through the paper quickly and have not read it thoroughly - sorry if I misread something)

I was not familiar with Dinitz' (Dinitz' google-wins Dinic's so I'm presuming this is correct) algorithm before. Thanks!

ackoroa
New poster
Posts: 4
Joined: Mon Mar 18, 2013 8:27 am

### Re: 10983 - Buy one, get the rest free.

I keep getting WAs too. Anybody can give some of the tricky cases?

Here's my code:

Code: Select all

``````#include <cstdio>
#include <vector>
#include <utility>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

#define INF 1e9
#define MAX_V 330

struct vertice {
int city;
int day;
vertice() {
}
vertice(int c, int d) {
this->city = c, this->day = d;
}
bool operator ==(vertice v) const {
return city == v.city && day == v.day;
}
int idx() {
return city * 10 + day;
}
};
typedef vector<vertice> vv;

int res[MAX_V][MAX_V], mf, f;
vertice s, t;
vi p;

int n, d, m, C;
#define NFLIGHT 1010
int uf[NFLIGHT], vf[NFLIGHT], cf[NFLIGHT], pf[NFLIGHT], ef[NFLIGHT],
sortedPF[NFLIGHT];
int pop[35];

void augment(int v, int minEdge) {
if (v == s.idx()) {
f = minEdge;
return;
} else if (p[v] != -1) {
augment(p[v], min(minEdge, res[p[v]][v]));
res[p[v]][v] -= f;
res[v][p[v]] += f;
}
}

void EdmondKarps() {
mf = 0;
while (1) {
f = 0;
bitset<MAX_V> visited;
visited.set(s.idx());
queue<vertice> q;
q.push(s);
p.assign(MAX_V, -1);
while (!q.empty()) {
vertice u = q.front();
q.pop();
if (u == t)
break;
for (int i = 0; i < (int) AdjList[u.idx()].size(); i++) {
vertice v = AdjList[u.idx()][i];
if (res[u.idx()][v.idx()] > 0 && !visited.test(v.idx())) {
visited.set(v.idx());
q.push(v);
p[v.idx()] = u.idx();
}
}
}
augment(t.idx(), INF);
if (f == 0)
break;
mf += f;
}
}

void initGraph() {
memset(res, 0, sizeof res);
s = vertice(0, 0);
t = vertice(n, d);

for (int i = 1; i <= n; i++) {
vertice v(i, 0);
res[s.idx()][v.idx()] = pop[i];
}

for (int i = 1; i <= n; i++) {
for (int j = 0; j < d - 1; j++) {
vertice v1(i, j), v2(i, j + 1);
res[v1.idx()][v2.idx()] = INF;
}
if (i == n) {
vertice v1(i, d - 1);
res[v1.idx()][t.idx()] = INF;
}
}

for (int i = 0; i < m; i++) {
if (pf[i] <= C) {
vertice v1(uf[i], ef[i]), v2(vf[i], ef[i] + 1);
res[v1.idx()][v2.idx()] = cf[i];
}
}
/*
printf("%d\n", C);
for (int i = 0; i <= 10 * n + d; i++) {
printf("vertice %d:", i);
for (int j = 0; j < AdjList[i].size(); j++) {
}
printf("\n");
}
*/
}

int main() {
int tc, cnt = 1;
int lo, hi, mid, sumPpl, pplOut;

scanf("%d", &tc);
while (tc--) {
scanf("%d %d %d", &n, &d, &m);

hi = -1;
for (int i = 0; i < m; i++) {
scanf("%d %d %d %d %d", &uf[i], &vf[i], &cf[i], &pf[i], &ef[i]);
sortedPF[i] = pf[i];
}
sort(sortedPF, sortedPF + m);

sumPpl = 0;
for (int i = 1; i <= n; i++) {
scanf("%d", &pop[i]);
sumPpl += pop[i];
}
pplOut = sumPpl - pop[n];

int lo;
for (lo = 0; lo < m; lo++) {
C = sortedPF[lo];
initGraph();
EdmondKarps();
if (mf >= sumPpl)
break;
}

printf("Case #%d: ", cnt++);
if (pplOut == 0)
printf("0\n");
else if (lo < m)
printf("%d\n", sortedPF[lo]);
else
printf("Impossible\n");
}

return 0;
}

``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10983 - Buy one, get the rest free.

Check input and AC output for thousands of problems on uDebug!

ackoroa
New poster
Posts: 4
Joined: Mon Mar 18, 2013 8:27 am

### Re: 10983 - Buy one, get the rest free.

Yeah, I've been following that and can solve the sample inputs there correctly :S (I do remove the debug printouts before I submit)

Or did I miss something from there? I'll go recheck...

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10983 - Buy one, get the rest free.

Input:

Code: Select all

``````1
6 8 84
3 3 18 1158 0
3 6 13 39909 1
6 3 57 62653 1
2 3 28 3031 5
2 4 53 42589 0
6 5 36 55625 2
5 5 44 47028 3
1 4 73 19487 0
2 2 34 92291 0
5 4 61 28358 6
4 4 72 73803 3
6 6 98 69351 5
6 5 88 85837 3
5 2 92 18791 7
6 6 10 83256 4
3 5 2 50509 3
2 6 92 89175 0
5 6 56 66806 4
4 3 32 89645 0
2 5 66 78507 4
4 6 82 29358 2
6 6 8 88585 6
4 1 16 44024 6
4 5 76 4677 7
6 2 96 71995 6
1 2 87 63422 4
2 1 31 25696 7
1 3 17 85144 3
5 5 86 5906 2
2 3 49 11017 1
5 6 55 76899 1
6 5 66 66682 7
2 4 74 17277 3
3 3 24 62432 7
6 6 52 78018 1
4 6 80 66633 5
1 1 43 76724 2
4 5 32 28509 4
5 3 19 67224 1
1 2 33 5071 1
5 4 89 37674 7
4 6 92 29161 1
5 2 36 77719 1
2 5 21 40450 7
3 6 75 79575 3
3 4 57 93855 2
4 2 5 52294 5
1 2 78 63953 7
3 2 22 74433 3
4 6 84 83667 0
6 3 87 50344 5
3 1 13 72065 3
6 4 89 25631 7
3 1 6 85056 1
5 4 45 46825 3
6 3 53 86049 7
3 2 85 79112 2
1 4 98 15381 4
5 4 92 91140 1
6 3 68 77503 4
2 6 12 76781 2
3 1 21 14282 5
1 1 53 4761 1
4 5 46 52629 6
3 5 8 8467 1
4 4 65 26176 5
2 2 29 13653 3
2 2 24 27172 1
5 1 71 33000 0
4 3 21 50052 3
4 4 24 7057 0
4 6 32 79462 3
6 3 11 94877 6
6 2 11 59657 1
5 6 71 86334 2
1 4 93 49026 7
6 2 65 40501 7
2 2 24 38461 7
1 5 76 17734 2
3 5 32 72214 4
3 6 61 92481 5
1 6 39 29012 4
1 1 78 59528 3
3 4 24 46553 1
3 31 9 100 49 87
``````
AC output:

Code: Select all

``````Case #1: 66633
``````
Check input and AC output for thousands of problems on uDebug!