10092 - The Problem with the Problem Setter

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

Moderator: Board moderators

anup10000
New poster
Posts: 2
Joined: Fri Oct 18, 2002 11:28 am
Contact:

10092 plz help(is it a max flow problem by any chance?)

Post by anup10000 » Sat Nov 29, 2003 9:43 pm

is it really a max flow problem? though i m not convinced about that, i tried doing it by ford fulkerson but could only get TLE. but i m not yet convinced abt the problem being a max flow problem. can anybobdy plz give share the algo and a brief explanation for the problem[/b]

anup10000
New poster
Posts: 2
Joined: Fri Oct 18, 2002 11:28 am
Contact:

10092 - The Problem with the Problem Setter

Post by anup10000 » Sat Nov 29, 2003 9:44 pm

is it really a max flow problem?
though i m not convinced about that, i tried doing it by ford fulkerson but could only get TLE. but i m not yet convinced abt the problem being a max flow problem.
can anybobdy plz give share the algo and a brief explanation for the problem

thanx in advance.

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Sun Nov 30, 2003 8:29 am

You can solve this problem by modifying the bipartite matching algorithm. But my friend also managed to solve this as max-flow, so perhaps you could optimise your ford fulkerson slightly to pass the time limit?

Both are quite slow though, modified bipartite matching used 0:03.096, 560 memory. Max-flow used 0:05.525, 12632 memory. You can even solve this faster by using hopcraft karp.

Hope this helps.

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

10092 Why this code gives w.a.

Post by harry » Sat Sep 18, 2004 8:06 am

i have solved several problems of bm using my modified ford fulkerson
algorithm.
but why the following code gives w.a.
plz help.thanks in advance.

Code: Select all

Code removed .Got A.C. :lol: 
Last edited by harry on Fri Sep 24, 2004 7:18 pm, edited 1 time in total.

User avatar
alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Post by alu_mathics » Fri Sep 24, 2004 7:14 pm

i thing you should not do that

list[s][count[s]++] = i;
//list[count++] = s;

change it to
list[s][count[s]++] = i;
list[count++] = s;

Hope you will get ac for that.Oh one thing , set max = 1022
cuii e

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

Post by harry » Fri Sep 24, 2004 7:17 pm

Thanks a lot. :wink:
Finally i got A.C. :lol:

qndel
New poster
Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole

10092

Post by qndel » Wed Feb 15, 2006 10:53 pm

I'm trying to solve problem 10092 but I'm getting WA. I'm buildig graph like this:

conect every category with sink (capicty= numbers of problems for this category).
if problem i is in category j I conect (j,i) (capicty=1) and fianlly I conect evry problem with the sink (capicty=1).


and find max flow using Ford Fulkerson method.

This is my code:

Code: Select all

#include <stdio.h>
#include <vector>

using namespace std;


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



int p,k,i,t,temp,j;
vector<int> graf[1100];
int f[1100][1100],obj[1100][1100];
bool byl[1100];


int dfs(int co,int juz)
    {
    byl[co]=true;
    int t,temp,t2;
    if (co==(p+k+1))
       return juz;
    for (i=0;i<graf[co].size();i++)
        if (byl[graf[co][i]]==false)
        {
        t=graf[co][i];
        temp=min(juz,obj[co][t]-f[co][t]+f[t][co]);
        if (temp<=0)
           continue;
        t2=dfs(t,temp);
        if (t2>0)
           {
           temp=min(t2,f[t][co]);
           f[t][co]-=temp;
           f[co][t]+=t2-temp;
           return t2;
           }
        }
    return 0;
    }




int main()
{
while (1)
      {
      scanf("%d %d",&k,&p);
      if (k==0 && p==0)
         break;
      for (i=0;i<=k+p+1;i++)
          graf[i].clear();
      memset(&obj,0,1100*1100*sizeof(int));
      memset(&f,0,1100*1100*sizeof(int));
      for (i=1;i<=k;i++)
          {
          scanf("%d",&t);
          graf[0].push_back(i);
          obj[0][i]=t;
          }
      for (i=1;i<=p;i++)
          {
          scanf("%d",&t);
          graf[k+i].push_back(k+p+1);
          obj[k+i][k+p+1]=1;
          for (j=1;j<=t;j++)
              {
              scanf("%d",&temp);
              graf[k+i].push_back(temp);
              graf[temp].push_back(k+i);
              obj[temp][k+i]=1;
              }
          }
      memset(&byl,0,1100*sizeof(bool));
      while (dfs(0,10000))
            memset(&byl,0,1100*sizeof(bool));
	  bool bb=false;
      for (i=1;i<=k;i++)
          if (f[0][i]<obj[0][i])
             {
             printf("0\n");
             bb=true;
			 break;
             }
	  if (bb) 
			continue;
	  printf("1\n");
      for (i=1;i<=k;i++)
          {
          bool b=false;
          for (j=1;j<=p;j++)
              if (f[i][k+j]>0)
                 {
                 if (b)
                    printf(" ");
                 b=true;
                 printf("%d",j);
                 }
          printf("\n");
          }
      }
return 0;
}

If anybody see any mistake please help me.
NOthing special

qndel
New poster
Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole

Post by qndel » Thu Feb 16, 2006 12:57 pm

Or maybe someone knows any tricky input???
NOthing special

qndel
New poster
Posts: 13
Joined: Tue Feb 03, 2004 11:00 am
Location: Opole

Post by qndel » Thu Feb 16, 2006 1:16 pm

What is correct output for:
8 20
1 3 3 4 5 1 3 3
6 1 2 3 4 5 6
5 1 2 3 4 5
8 1 2 3 4 5 6 7 8
2 1 2
1 1
1 1
7 1 2 3 4 5 6 7
1 1
6 1 2 3 4 5 6
2 1 2
2 1 2
1 1
4 1 2 3 4
2 1 2
6 1 2 3 4 5 6
2 1 2
6 1 2 3 4 5 6
6 1 2 3 4 5 6
3 1 2 3
7 1 2 3 4 5 6 7
2 5
3 5
2 1 2
1 1
1 1
2 1 2
2 1 2
9 18
3 5 4 1 2 4 1 3 3
4 1 2 3 4
3 1 2 3
9 1 2 3 4 5 6 7 8 9
3 1 2 3
6 1 2 3 4 5 6
7 1 2 3 4 5 6 7
6 1 2 3 4 5 6
1 1
6 1 2 3 4 5 6
8 1 2 3 4 5 6 7 8
4 1 2 3 4
9 1 2 3 4 5 6 7 8 9
3 1 2 3
4 1 2 3 4
7 1 2 3 4 5 6 7
7 1 2 3 4 5 6 7
7 1 2 3 4 5 6 7
8 1 2 3 4 5 6 7 8
1 8
3
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
4 19
2 3 4 1
4 1 2 3 4
1 1
4 1 2 3 4
1 1
4 1 2 3 4
1 1
2 1 2
1 1
3 1 2 3
3 1 2 3
4 1 2 3 4
1 1
1 1
3 1 2 3
1 1
3 1 2 3
2 1 2
4 1 2 3 4
1 1
10 19
2 1 5 1 1 2 1 3 1 5
5 1 2 3 4 5
9 1 2 3 4 5 6 7 8 9
6 1 2 3 4 5 6
10 1 2 3 4 5 6 7 8 9 10
10 1 2 3 4 5 6 7 8 9 10
8 1 2 3 4 5 6 7 8
5 1 2 3 4 5
8 1 2 3 4 5 6 7 8
10 1 2 3 4 5 6 7 8 9 10
7 1 2 3 4 5 6 7
4 1 2 3 4
3 1 2 3
4 1 2 3 4
3 1 2 3
7 1 2 3 4 5 6 7
7 1 2 3 4 5 6 7
10 1 2 3 4 5 6 7 8 9 10
6 1 2 3 4 5 6
9 1 2 3 4 5 6 7 8 9
8 14
4 4 1 3 3 5 3 1
3 1 2 3
1 1
3 1 2 3
8 1 2 3 4 5 6 7 8
2 1 2
5 1 2 3 4 5
3 1 2 3
5 1 2 3 4 5
5 1 2 3 4 5
7 1 2 3 4 5 6 7
7 1 2 3 4 5 6 7
3 1 2 3
2 1 2
4 1 2 3 4
2 7
4 2
1 1
1 1
2 1 2
1 1
2 1 2
1 1
1 1
3 11
4 4 4
3 1 2 3
2 1 2
3 1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
1 1
1 1
1 1
3 1 2 3
3 1 2 3
2 11
1 4
1 1
1 1
2 1 2
1 1
1 1
1 1
2 1 2
2 1 2
1 1
1 1
2 1 2
0 0

my is
0
0
0
1
1 2 3
1
2 8
7 11 14
3 5 9 10
1
0
0
1
1 2 4 6
3 5
0
1
1
3 7 8 11
NOthing special

m_thimma
New poster
Posts: 3
Joined: Wed Feb 15, 2006 10:01 am
Location: iitg,india

Post by m_thimma » Thu May 11, 2006 11:03 am

i used edmond-karps algrorithm...
i got a timelimit of 0.033sec for software allocation...
i used same alg with little modifications to this problem....
but i am getting 2.5sec....
can anyone suggest some ways to reduce my running time
Genius is a 2% inspiration and 98% perspiration

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

Post by serur » Tue May 16, 2006 7:08 pm

Hi fellows!

I'm learning preflow-push as it is expounded in "Bible" :), and got AC the "touchstone" of network flow algoritms - q820 - "Internet Bandwidth". I applied preflow-push to 10092 (because Edmund-Karp gave TLE...), and I think found "official solution",for my outputs for sample inputs were the same as in problem description, but OJ says WA.
Fellows who solved 10092 with preflow-push - your comments will be greatly appreciated.

I attach my code. I think it's just what's written in pseudocode in CLR.
One comment: when solving this with Edmund-Karp I made links unidirectional, but here I was obliged to make them bidirectional. What do you think of it all?



Thank you.
Last edited by serur on Wed May 17, 2006 7:39 am, 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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue May 16, 2006 9:43 pm

here I was obliged to make them bidirectional. What do you think of it all?
Well, the maximum flow will be equal to max cardinality of matching anyway, but if edges are bidirectional you can't convert the flow to a matching in that way as you do now. The output may not be a matching.

Here's a simple test, your output (all 1's) is wrong.

Code: Select all

3 3
1 1 1
3 1 2 3
3 1 2 3
3 1 2 3
0 0

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

Post by serur » Tue May 16, 2006 10:15 pm

Thank you, mf.

Tomorrow I'll think of all you said thoroughly.
And tell you what came of it :)
But, you see, when I made them unidirectional, my program got into infinite loop for second sample test - I suppose my implementation of preflow-push is wrong? But the same code got AC in 820/...
Last edited by serur on Sat Apr 14, 2012 3:28 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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue May 16, 2006 10:54 pm

So why didn't you try to debug? Infinite loops definitely indicate some problem with code, and if you don't take the time to analyze what causes it, the bug may hit you again and again.

I see at least one bug: in init_preflow() you change flow along edges outgoing from source, but you don't update the residual capacity array.

(Actually, what's the point of having two separate arrays for flow and residual capacity? Just keep one array, say residual capacity; you can always find the flow by subtracting residual from initial capacity.)

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

Post by serur » Wed May 17, 2006 7:38 am

Well, mf, "Utro vechera mudrenee". I just got AC with 1.777 ( :( )
I changed this: made all the edges directed except edges between source and categories - so that is some category is overflowing it can send liquid to the source agin. It's complete biparite matching problem, yes?

Your last suggestion about arrays is sound,of course,
but I only wanted to make my code a bit less messy :) while I debug it.
Last edited by serur on Sat Apr 14, 2012 3:28 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

Post Reply

Return to “Volume 100 (10000-10099)”