## 10092 - The Problem with the Problem Setter

Moderator: Board moderators

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
One more thing:
I know that 10249-Grand dinner can be easily solved with greedy, but I just got it AC with preflow-push in 8.xxx CPU.
I think that lift-to-front is still faster
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
If you want to speed up a push-preflow algorithm, the most useful optimization is a Global Relabelling heuristic. After every |V| relabels (or lift's), compute new height function: h(u) = min(d(u,t), |V|+d(u,s)). (here, d(u,v) is shortest distance between u and v, in edges). This can be done with two BFSs, from the source and the sink.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
Hello, mf!

You wrote:
If you want to speed up a push-preflow algorithm, the most useful optimization is a Global Relabelling heuristic. After every |V| relabels (or lift's), compute new height function: h(u) = min(d(u,t), |V|+d(u,s)). (here, d(u,v) is shortest distance between u and v, in edges). This can be done with two BFSs, from the source and the sink.

Well, I've just done it, but got TLE. Please have a look at this (here d stands for distance between u and source, d - for distance between u and sink; I do two full traverses - from source and from sink; but I think my code is quite transparent)

Code: Select all

``/``
(also, pray don't laugh at my bitwise operations - I just wanted to tweak my memory, but it's still 456 or so - far-far from your 64 )

Thank you.
Last edited by serur on Wed May 17, 2006 8:42 pm, edited 1 time in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
Hi mf!

I searched the web "Global relabelling heuristics" - got something from mexmat MGU (Maxim Babenko), but "page cannot be opened".
Can you show me good URL? Preferable in russian Thank you.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
This gives me TLE.

mf, am I on the right tack?

Code: Select all

``````/*"Internet Bandwidth"*/
/*preflow-push with Global Relabelling Heuristic*/
#include <stdio.h>
#include <string.h>
#include <limits.h>
#define min(a,b)((a)<(b)?(a):(b))
#define oo SHRT_MAX
#define N 101

int s,t,n;
int c[N][N],e[N],h[N],residual[N][N];
int f[N][N];
int d[N];
int visited[N];

int Q[N];
int last,first;

init(){
last=-1;first=0;
}
enqueue(int x,int circle,int ind){
Q[++last]=x;
d[x][ind]=circle;
visited[x]=1;
}
int dequeue(int *x,int ind){
*x=Q[first++];
return d[*x][ind];
}
int empty(){
return(last<first);
}
bfs(int root){
int u,v;
int circle;
int ind=0;
if(root==t)
ind=1;
memset(visited,0,sizeof(visited));
init();
enqueue(t,0,ind);
do{
circle=dequeue(&v,ind);
++circle;
for(u=1;u<=n;u++)
if(residual[v][u]>0 && !visited[u])
enqueue(u,circle,ind);
}while(!empty());
}
new_height()
{
int u;
for(u=1;u<=n;u++)
if(d[u]<oo)
h[u]=d[u];
else if(d[u]<oo)
h[u]=(n+d[u]);
else
h[u]=(2*n-1);

}
init_preflow()
{
int u,w;
memset(f,0,sizeof(f));
memset(e,0,sizeof(e));
memset(h,0,sizeof(h));
h[s]=n;
for(u=1;u<=n;u++)
if(w=c[s][u])
{
f[s][u]=w;
f[u][s]=-w;
residual[s][u]=c[s][u]-f[s][u];
residual[u][s]=c[u][s]-f[u][s];
e[u]=w;
}
}
relabel(int u)
{
int v;
int m=oo;
for(v=1;v<=n;v++)
if(m>h[v] && residual[u][v]>0)
m=h[v];
h[u]=(m+1);
}
push(int u,int v)
{
int d=min(e[u],residual[u][v]);
f[u][v]+=d;
residual[u][v]=(c[u][v]-f[u][v]);
f[v][u]=-f[u][v];
residual[v][u]=(c[v][u]-f[v][u]);
e[u]-=d;
e[v]+=d;
}
int get_overflowing()
{
int u;
for(u=1;u<=n;u++)
if(e[u] && u!=t && u!=s)
return u;
return 0;
}
generic_preflow_push()
{
int u,v;
int relabel_counter=0;
init_preflow();

while(u=get_overflowing())
{
for(v=1;v<=n;v++)
if(h[u]==h[v]+1 && residual[u][v]>0)
{
push(u,v);
goto next;
}
relabel(u);
++relabel_counter;
if(relabel_counter==n)
{
memset(d,oo,sizeof(d));
bfs(s);
bfs(t);
new_height();
relabel_counter=0;
}
next:continue;
}
}
int main()
{
int i,j,k,volume,cs=0;
#ifndef ONLINE_JUDGE
freopen("A.in","r",stdin);
#endif
scanf("%d\n",&n);
while(n)
{
scanf("%d %d %d\n",&s,&t,&k);
while(k--)
{
scanf("%d %d %d\n",&i,&j,&volume);
c[i][j]+=volume;
c[j][i]=c[i][j];
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
residual[i][j]=c[i][j];
generic_preflow_push();
printf("Network %d\nThe bandwidth is %d.\n\n",++cs,e[t]);
scanf("%d\n",&n);
if(n)
memset(c,0,sizeof(c));
else
return 0;
}
return 0;
}``````
Thank you.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
I've learned global relabelling from this paper. Sorry, I don't know any good russian urls on push-preflow algorithms.
memset(d,oo,sizeof(d));
In this case, memset will set all elements of d to -1. (the lower 8 bits of oo is 0xff, and (int)0xffffffff == -1)

In bfs() function:
1. you always start BFS from sink (regardless of value of 'root' parameter),
2. it seems, like you are finding values of d(t,u), while you need d(u,t); you should traverse edges of residual network in opposite direction.
got something from mexmat MGU (Maxim Babenko), but "page cannot be opened".
It's MSU's new policy.
They had a fire recently, and now all mechmat's servers (like shade.msu.ru) are down during night and weekends.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
Hello mf!

Global Relabelling Heuristic improves running time of preflow push - my pure preflow-push
run 0.583 before AC, but preflow-push seasoned with heuristics - in every n relabellings I did BACKWARD bfs from sink (note that "distance" here doesn't obey strict mathematical definition of distance function - many thanks to mf for pointing this out), and set heights of vertices to be nothing but obtained distances to sink, and set infinity to be (2*n-1) - got AC in 0.127 CPU,432-memory.
Still, it's 4 times as long as my Edmund-Karp (AC in 0.031 CPU), to say nothing of memory, so I think I've missed the crux.

I'll post here as soon as attain to something better.

Thank you.

P.S. It's a pity that mechmat should be having such unpleasant things thrust on it's head, in addition to that the Dean of that Holy Place had passed away.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
pls tell me why i m getin WA on this problem. any test case will be appreciated.

Code: Select all

``````#include<stdio.h>
#include<queue>

using namespace std;

int cap,flow,n,m,s,t,cp;
int total;

void init()
{
int i,j;

for(i=0;i<=n;i++) total[i]=0;

for(i=0;i<t;i++){
for(j=0;j<t;j++){
cap[i][j]=flow[i][j]=0;
}
}

for(i=n+1;i<t;i++) {cap[i][t]=1;flow[i][t]=0;}
}

int max_flow()
{
int i,p,now,before;
bool visited;
queue<int> Q;

for(i=0;i<=t;i++){
visited[i]=false;
p[i]=-1;
}

Q.push(s);
p[s]=-1;
visited[s]=true;

while(!Q.empty()){
now=Q.front();
Q.pop();

for(i=1;i<=t;i++){
if((cap[now][i]-flow[now][i])>0 && visited[i]==false){

Q.push(i);
visited[i]=true;
p[i]=now;

}
}
if(visited[t]==true) break;
}

if(visited[t]==false) return 0;

now=t;

while(p[now]!=-1){
before=p[now];
if(now>n && now<t && before>=1 && before<=n) {
cp[before][total[before]++]=now;
}
flow[before][now]++;
flow[now][before]--;
now=before;
}

return 1;
}

int main()
{
int i,j,k,cn,capacity,count;

while(true){
scanf("%d %d",&n,&m);
if(!n && !m) break;
s=capacity=0;
t=n+m+1;
init();

for(i=1;i<=n;i++) {
scanf("%d",&cap[s][i]);
capacity+=cap[s][i];
}

for(i=n+1;i<t;i++){
scanf("%d",&k);
for(j=0;j<k;j++){
scanf("%d",&cn);
cap[cn][i]=1;

}
}

count=0;
while(max_flow() ) count++;

if(count<capacity) printf("0\n");
else {
printf("1\n");
for(i=1;i<=n;i++){
for(j=0;j<total[i];j++) {
if(j) printf(" ");
printf("%d",cp[i][j]-n);
}
printf("\n");
}

}

}
return 0;
}``````

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
I am getting WA !!

can anyone give my some critical input and output to check my code ??

Code: Select all

``````solution changed ....
``````
Last edited by Kallol on Mon Sep 03, 2007 4:45 pm, edited 1 time in total.
Syed Ishtiaque Ahmed Kallol
CSE,BUET

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
My idea was very simple. I connected every problem with the source with capacity 1. I connected every problem with corresponding catagories with capacity 1. Then split every catagory into 2 nodes and the capacity between them in the allowed capacity for that catagory. Finally I connected the dummy catagories to the sink with infinite capacity.

I used Dinics algorithm which run O(n^3).

I am getting WA . Is there anything wrong with my idea ?? Any tricky case where my code makes wrong answer?? Would you please help me ??
Syed Ishtiaque Ahmed Kallol
CSE,BUET

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
here I tried it with DFS ...but still WA Code: Select all

``````#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>

#define SIZE 1010

using namespace std;

//globals
int cap;
int filled;
int NK,NP;
bool seen[SIZE];
int leftM;
int rightM[SIZE];

bool bpm(int u)
{
int j;
bool flag=true;
while(filled[u]<cap[u] && flag)
{
flag=false;
{
if(seen[j])continue;
else seen[j]=true;

if(rightM[j]<0)
{
rightM[j]=u;
filled[u]++;
leftM[u][filled[u]]=j;
flag=true;
break;
}

int x=rightM[j];
filled[x]--;
if(bpm(x))
{
rightM[j]=u;
filled[u]++;
leftM[u][filled[u]]=j;
flag=true;
break;
}
else
{
filled[x]++;
}
}

}

if(filled[u]==cap[u])
return true;
return false;
}

int main(void)
{
int i,j,n,p;
while(true)
{
scanf("%d%d",&NK,&NP);
if(NP==0 && NK==0)
break;

//input
for(i=1;i<=NK;i++)
scanf("%d",&cap[i]);
for(i=1;i<=NP;i++)
{
scanf("%d",&n);
for(j=1;j<=n;j++)
{
scanf("%d",&p);
}
}

memset(filled,0,sizeof(filled));
memset(leftM,-1,sizeof(leftM));
memset(rightM,-1,sizeof(rightM));

bool flag =true;
for(i=1;i<=NK && flag;i++)
{
memset(seen,false,sizeof(seen));
if(!bpm(i))
flag=false;
}

if(!flag)
printf("0\n");
else
{
printf("1\n");
for(i=1;i<=NK;i++)
{
bool start=true;
for(j=1;j<=cap[i];j++)
{
if(start)
start=!start;
else
printf(" ");
printf("%d",leftM[i][j]);
}
printf("\n");
}
}
}
return 0;
}
``````
counter case plzzzzzzzzz......
Syed Ishtiaque Ahmed Kallol
CSE,BUET

DP
Learning poster
Posts: 62
Joined: Sun Aug 13, 2006 9:15 am
Contact:
Kallol wrote:here I tried it with DFS ...but still WA ......
counter case plzzzzzzzzz......
No.
Why are you crying?

Check this code(bpm part) with
http://acm.uva.es/p/v100/10080.html
If correct then generate some random Test Cases by yourself.

Then post the I/O here, it'll be easier to find out bug for other coders.

Btw, HBD(late)!

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
Thanks for wishing ...
and I solved Gopher problem (10080) with same bpm function.

actually I have been trying this problm for past few days ...tried with every input I got in the forum and also checked with my testing input and got the rigth answer . Thats why I was a bit upset . The problem looks straight forward .... I must have made some stupid mess up Syed Ishtiaque Ahmed Kallol
CSE,BUET

jj_99
New poster
Posts: 2
Joined: Fri Nov 23, 2007 7:48 pm
what's worng of my code
can you give me some input to check it

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>

#define MAXV 100 /* maximum number of vertices */
#define MAXDEGREE 50 /* maximum outdegree of a vertex */

#define QUEUESIZE 1000

#define X 0 /* x-coordinate index */
#define Y 1 /* y-coordinate index */

#define TRUE 1
#define FALSE 0
typedef int bool;

typedef struct {
int q[QUEUESIZE+1]; /* body of queue */
int first; /* position of first element */
int last; /* position of last element */
int count; /* number of queue elements */
} queue;

typedef struct {
int edges[MAXV+1][MAXDEGREE]; /* adjacency info */
int degree[MAXV+1]; /* outdegree of each vertex */
int nvertices; /* number of vertices in the graph */
int nedges; /* number of edges in the graph */
} graph;

typedef struct {
int v; /* neighboring vertex */
int capacity; /* capacity of edge */
int flow; /* flow through edge */
int residual; /* residual capacity of edge */
} edge;

typedef struct {
edge edges[MAXV][MAXDEGREE]; /* adjacency info */
int degree[MAXV]; /* outdegree of each vertex */
int nvertices; /* number of vertices in the graph */
int nedges; /* number of edges in the graph */
} flow_graph;

int min (int a,int b){
if (a > b)
return b;
else
return a;
}

int init_queue(queue *q)
{
q->first = 0;
q->last = QUEUESIZE-1;
q->count = 0;
}

int enqueue(queue *q, int x)
{
if (q->count >= QUEUESIZE)
printf("Warning: queue overflow enqueue x=%d\n",x);
else {
q->last = (q->last+1) % QUEUESIZE;
q->q[ q->last ] = x;
q->count = q->count + 1;
}
}

int dequeue(queue *q)
{
int x;

if (q->count <= 0) printf("Warning: empty queue dequeue.\n");
else {
x = q->q[ q->first ];
q->first = (q->first+1) % QUEUESIZE;
q->count = q->count - 1;
}

return(x);
}

int empty(queue *q)
{
if (q->count <= 0) return (TRUE);
else return (FALSE);
}

int initialize_graph(flow_graph *g)
{
int i; /* counter */

g -> nvertices = 0;
g -> nedges = 0;

for (i=0; i<MAXV; i++) g->degree[i] = 0;
}

int insert_flow_edge(flow_graph *g, int x, int y,bool directed, int w)
{
if (g->degree[x] > MAXDEGREE)
printf("Warning: insertion(%d,%d) exceeds degree bound\n",x,y);

g->edges[x][g->degree[x]].v = y;
g->edges[x][g->degree[x]].capacity = w;
g->edges[x][g->degree[x]].flow = 0;
g->edges[x][g->degree[x]].residual = w;
g->degree[x] ++;

if (directed == FALSE)
insert_flow_edge(g,y,x,TRUE,w);
else
g->nedges ++;
}

int read_flow_graph(flow_graph *g,int directed,int c,int p)
{
int i,n; /* counter */
int m; /* number of edges */
int x,y,w; /* placeholder for edge and weight */
int count=0;
int sink;

sink=c+p+2;

initialize_graph(g);

for (i=1;i<=c;i++){
scanf("%d",&w);
insert_flow_edge(g,1,i+1,directed,w);
count++;
}

for (i=1; i<=p; i++) {
scanf("%d",&m);
if (m<=c&&m>0)
for(n=0;n<m;n++){
scanf("%d",&x);
if (x<=c&&x>0)
insert_flow_edge(g,x+1,c+i+1,directed,1);

}
insert_flow_edge(g,c+i+1,sink,directed,1);

}
g->nvertices=sink;
}

edge *find_edge(flow_graph *g, int x, int y)
{
int i; /* counter */

for (i=0; i<g->degree[x]; i++)
if (g->edges[x][i].v == y)
return( &g->edges[x][i] );

return(NULL);
}

{
int i,j; /* counters */

for (i=1; i<=g->nvertices; i++)
for (j=0; j<g->degree[i]; j++)
if (find_edge(g,g->edges[i][j].v,i) == NULL)
insert_flow_edge(g,g->edges[i][j].v,i,TRUE,0);
}

int print_flow_graph(flow_graph *g)
{
int i,j; /* counters */

for (i=1; i<=g->nvertices; i++) {
printf("%d: ",i);
for (j=0; j<g->degree[i]; j++)
printf(" %d(%d,%d,%d)",g->edges[i][j].v,
g->edges[i][j].capacity,
g->edges[i][j].flow,
g->edges[i][j].residual);
printf("\n");
}
}

bool processed[MAXV]; /* which vertices have been processed */
bool discovered[MAXV]; /* which vertices have been found */
int parent[MAXV]; /* discovery relation */

bool finished = FALSE; /* if true, cut off search immediately */

int initialize_search(flow_graph *g)
{
int i; /* counter */

for (i=1; i<=g->nvertices; i++) {
processed[i] = FALSE;
discovered[i] = FALSE;
parent[i] = -1;
}
}

int bfs(flow_graph *g, int start)
{
queue q; /* queue of vertices to visit */
int v; /* current vertex */
int i; /* counter */

init_queue(&q);
enqueue(&q,start);
discovered[start] = TRUE;

while (empty(&q) == FALSE) {
v = dequeue(&q);

for (i=0; i<g->degree[v]; i++)
if (valid_edge(g->edges[v][i]) == TRUE) {
if (discovered[g->edges[v][i].v] == FALSE) {
enqueue(&q,g->edges[v][i].v);
discovered[g->edges[v][i].v] = TRUE;
parent[g->edges[v][i].v] = v;
}

}
}
}

bool valid_edge(edge e)
{
if (e.residual > 0) return (TRUE);
else return(FALSE);
}

int find_path(int start,int end,int parents[])
{
if ((start == end) || (end == -1))
printf("\n%d",start);
else {
find_path(start,parents[end],parents);
printf(" %d",end);
}
}

int path_volume(flow_graph *g, int start, int end, int parents[])
{
edge *e; /* edge in question */
edge *find_edge();

if (parents[end] == -1) return(0);

e = find_edge(g,parents[end],end);

if (start == parents[end])
return(e->residual);
else
return( min(path_volume(g,start,parents[end],parents), e->residual) );
}

int augment_path(flow_graph *g, int start, int end, int parents[], int volume)
{
edge *e; /* edge in question */
edge *find_edge();

if (start == end) return;

e = find_edge(g,parents[end],end);
e->flow += volume;
e->residual -= volume;

e = find_edge(g,end,parents[end]);
e->residual += volume;

augment_path(g,start,parents[end],parents,volume);
}

int netflow(flow_graph *g, int source, int sink)
{
int volume; /* weight of the augmenting path */

initialize_search(g);
bfs(g,source);

volume = path_volume(g, source, sink, parent);

while (volume > 0) {
augment_path(g,source,sink,parent,volume);
initialize_search(g);
bfs(g,source);
volume = path_volume(g, source, sink, parent);
}
}

int main(void)
{
flow_graph g; /* graph to analyze */
int source, sink; /* source and sink vertices */
int flow; /* total flow */
int i,j,tmp; /* counter */
int c,p;

scanf("%d%d",&c,&p);
while (c != 0 && p != 0){

source=1;
sink=2+c+p;
netflow(&g,source,sink);

flow = 0;
for (j=0; j<g.degree[i+1]; j++){
if(g.edges[j].residual != 0){
flow=1;
}
}

if(flow == 0){
printf("1\n");
for (i=1;i<=c;i++){
for (j=0; j<g.degree[i+1]; j++){
if(g.edges[i+1][j].residual == 0){
tmp=g.edges[i+1][j].v;
tmp = tmp -c -1;
printf("%d ",tmp);
}
}
printf("\n");
}
}
else
printf("0\n");

scanf("%d%d",&c,&p);
}
//print_flow_graph(&g);
system("pause");
}``````

diego_engcomp
New poster
Posts: 9
Joined: Sat Jul 18, 2009 1:18 am

### Re: 10092 - The Problem with the Problem Setter

Hi, I solved the "UVA 10249 - The Grand Dinner" using a greddy algorithm and I think that this problem can be solved using a greddy algorithm too. I developed one and I can't see bugs on it. Can anybody tell me why my code fail or give me a test case where it fails? . Thanks and sorry for my English.

Code: Select all

``````#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef struct{
int id, quant;
}prob_cat;

typedef struct{
int id;
vector <int> cats;
}problem;

bool compare(prob_cat p1, prob_cat p2){
if (p1.quant<=p2.quant)
return true;
return false;
}

bool compare2(problem p1, problem p2){
if (p1.cats.size()<=p2.cats.size())
return true;
return false;
}

int main(){
int nk, np, i, j;
while(true){
cin>>nk>>np;
if(!nk && !np)
break;
vector< int > categories(nk);
vector< problem > problems(np);
vector< prob_cat > probs_cat(nk);
for(i=0; i<nk; i++){
probs_cat[i].id=i+1;
probs_cat[i].quant=0;
cin>>categories[i];
}
int n, cat;
for(i=0; i<np; i++){
cin>>n;
problems[i].id=i+1;
for(j=0; j<n; j++){
cin>>cat;
problems[i].cats.push_back(cat);
probs_cat[cat-1].quant++;
}
}
sort(probs_cat.begin(),probs_cat.end(),compare);
sort(problems.begin(),problems.end(),compare2);
/*for (i=0; i<np; i++){
cout<<problems[i].id<<" -- ";
for(j=0; j<problems[i].cats.size(); j++)
cout<<problems[i].cats[j]<<" ";
cout<<endl;
}*/
vector< vector <int> > result(nk,vector<int>());
int counter;
bool impossible=false;
for(i=0; i<nk; i++){
counter=0;
for(j=0; j<np; j++){
if(counter==categories[probs_cat[i].id-1])
break;
if(problems[j].id!=0){
if(find(problems[j].cats.begin(),problems[j].cats.end(),probs_cat[i].id)!=problems[j].cats.end()){
result[probs_cat[i].id-1].push_back(problems[j].id);
counter++;
problems[j].id=0;
}
}
}
if(counter!=categories[probs_cat[i].id-1]){
cout<<"0"<<endl;
impossible=true;
break;
}
}
if(!impossible){
cout<<"1"<<endl;
for(i=0; i<nk; i++){
for(j=0; j<result[i].size(); j++){
if(j>0)
cout<<" ";
cout<<result[i][j];
}
cout<<endl;
}
}
}
return 0;
}
``````