259 - optimizing..

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

Moderator: Board moderators

259 - optimizing..

Postby jagadish » Fri Jul 02, 2004 8:47 pm

i got 0.5x sec for this one using dfs..cant see how people have got close to 0 sec ... all those who are above my rank have runnning times at least 10 times lesser than mine :(
can anyone of you give me some hints to speed up my code ?
if u can think of it .. u can do it in software.
jagadish
Learning poster
 
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Postby m_thimma » Thu May 11, 2006 7:03 am

i used the following alg:
0-9 indicates different computers
10-35 indicates applications
36 is source,37 destination
1)i constructed network with above conventions and the weights of edges between source and applications is the no of users bringing that application and all the othere edges weights are 1.
2)i used maxflow with bfs strategy...
whenever i find augmentation path...i saved the matching ...
it took around 0.033sec since it is only 38*38 size matrix only
Genius is a 2% inspiration and 98% perspiration
m_thimma
New poster
 
Posts: 3
Joined: Wed Feb 15, 2006 10:01 am
Location: iitg,india

WA

Postby baodog » Wed Aug 01, 2007 2:53 am

I keep getting WA ... I checked with many inputs, and I get
right answer. I'm using very simply bakctracking/brute force.
Are there any extremely tricky cases? Thanks.
Really appreciate it.

Here is my code for reference:

Code: Select all
ACC...  Thank you, Rio!
Can't believe I missed that ...
None of my test cases tested it ... 
Last edited by baodog on Fri Aug 03, 2007 11:14 pm, edited 1 time in total.
baodog
Experienced poster
 
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Postby rio » Fri Aug 03, 2007 10:57 am

I found where to fix, but can't create the critical test cases.
And I'm not sure even such critical cases can actually occur.

Anyway, insert
Code: Select all
computer[n] = 0;

before
Code: Select all
return Solve(n+1);

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

Postby Kallol » Tue Aug 14, 2007 8:51 pm

well

I tried here bipartite matching .... my code ran well for all the input I gave . But i dont know why it is gettin RUNTIME ERROR(invalid memory reference) in UVA judge :(

can anyone help me ??

here is my code ..

Code: Select all
#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;


int a[300][300];
int task[300];
bool alpha[300];
char alloc[500];
bool seen[500];

bool bpm(int i)
{
   int j;
   for(j=0;j<10;j++)
      if(a[i][j] && alloc[j]=='_')
      {
         alloc[j]=i+'A';
         return true;
      }
   
   seen[i]=true;
   for(j=0;j<10;j++)if(a[i][j] && (alloc[j]-'A')!=i && !seen[j])
   {
      if(bpm(alloc[j]-'A'))
      {
         alloc[j]=i+'A';
         return true;
      }
   }
   return false;
}


int main(void)
{
   //freopen("259in.txt","r",stdin);
   char s[1000];
   int i,j,q;
   while(gets(s))
   {

      memset(a,0,sizeof(a));
      memset(alpha,false,sizeof(alpha));
      memset(alloc,'_',sizeof(alloc));
      
      if(strcmp(s,"")==0)
      {
         for(i=0;i<10;i++)
         {
            printf("%c",alloc[i]);
         }
         printf("\n");
         continue;
      }
      int p=s[0]-'A';
      task[p]=s[1]-'0';
      alpha[p]=true;
      for(i=3;s[i]!=';';i++)
      {
         q = s[i]-'0';
         a[p][q]=1;
      }

      while(1)
      {
         if(!gets(s))
            break;
         if(strcmp(s,"")==0)
            break;
         p=s[0]-'A';
         task[p]=s[1]-'0';
         alpha[p]=true;
         for(i=3;s[i]!=';';i++)
         {
            q=s[i]-'0';
            a[p][q]=1;
         }
      }

      int cnt=0;
      int flag=1;
      for(i=0;i<26;i++)if(alpha[i])
      {
         for(j=0;j<task[i];j++)
         {
            memset(seen,false,sizeof(seen));
            if(!bpm(i))
            {
               flag=0;
               break;
            }
         }
         if(!flag)
            break;
      }

      if(!flag)
      {
         printf("!\n");
      }
      else
      {
         for(i=0;i<10;i++)
         {
            printf("%c",alloc[i]);
         }
         printf("\n");
      }
   }
   return 0;
}

Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh
User avatar
Kallol
Learning poster
 
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Postby Jan » Tue Aug 14, 2007 10:34 pm

I dont know why you are getting RTE. But I can tell you that your code is not fully correct. Try the case below:

Input:
Code: Select all
A1 13579;
B1 02468;
C1 01;
D1 02;
E1 1;
F1 3;
P1 4;
Q1 5;
Z1 7;

Output:
Code: Select all
CEDFPQBZ_A

Hope it helps.
Ami ekhono shopno dekhi...
HomePage
Jan
Guru
 
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh

Runtime Error

Postby Akter_Sust » Thu Oct 18, 2007 8:23 am

Any one can get runtime error because input may be like

A1 13579;
B1 a-123;

Handle this i got accepted other wise i got runtime error.
Akter_Sust
New poster
 
Posts: 4
Joined: Sat Sep 16, 2006 9:55 am

Re: 259 - optimizing..

Postby RenatoAlmeida » Mon Nov 09, 2009 2:18 am

EDIT: I think I found the error. I Will look this, thanks!
EDIT2: Sorry for post, I solved my problem. :)


I'm getting WA on this problem, can anyone help me with more elaborated test cases or look my code?

My graph:

0 - source
1 - sink
2...11 - computers
12+ - applications

There are a edge "SOURCE -> APPLICATION", for each application described, with capacity equal to the number of users for this application.
There are a edge "APPLICATION -> COMPUTER", with capacity 1, if the application can run on this computer.
There are ten edges "COMPUTER -> SINK", with capacity 1.

Then I run maxFlow algorithm, and if I can't match all users with your applications on the ten computers, print "!",

Else, I look on the flow matrix, for each edge APPLICATION -> COMPUTER, if the flow on this edge is 1, the application on this computer "COMPUTER" will be "APPLICATION".

My code works on the tests in this thread and others, I can't find the error.

Here the code:

Code: Select all
Accepted!
I was forget the flow on v->u , fnet on COMPUTER -> APPLICATION
Thanks.


PS: for the max flow, I use the ford fulkerson algorithm of shygypsy library.


Thanks!
RenatoAlmeida
New poster
 
Posts: 3
Joined: Sun Jul 12, 2009 6:22 am

Re: Runtime Error

Postby K0stIa » Fri Sep 24, 2010 9:42 am

Akter_Sust wrote:Any one can get runtime error because input may be like

A1 13579;
B1 a-123;

Handle this i got accepted other wise i got runtime error.



hello, guys.

I tired to submit problems on this site. I think i solved this problem and have problems with I/O. Can anybody see on my code below ? If u can give me some advises how to write I/O for the problem on this site i'll be very thankful for u, coz i like problems on this site and dislike the format input data on it.

Code: Select all
#include <iostream>
#include <sstream>
using namespace std;

const int N = 38;
int C[N][N];
int F[N][N];

void clear()
{
   memset(C,0,sizeof(C));
   memset(F,0,sizeof(F));
}

const int s = 36;
const int t = 37;
const int inf = 1<<30;

int maxFlow()
{   
   int e[N], h[N];

   memset(e,0,sizeof(e));
   memset(h,0,sizeof(h));

   h[s] = N;

   for(int i = 0; i < N; ++i)
      if(i != s)
      {
         F[s][i] = C[s][i];
         F[i][s] = -F[s][i];
         e[i] = F[s][i];
      }
      
   for(int i = 0, j = 0, sz = 0, maxh[N]; ; )
   {
      if(!sz)
      {
         for(i=0; i < N; ++i)
            if(i != s && i != t && e[i])
            {
               if(!sz || h[i] > h[maxh[0]])
               {
                  sz = 0;
                  maxh[sz++] = i;
               }
               else if(h[i] == h[maxh[0]])
                     maxh[sz++]=i;
            }                        
      }

      if(!sz) break;

      while(sz > 0)
      {
         bool pushed = false;         
         i = maxh[sz-1];
         
         for(j=0; j < N; ++j)
            if(C[i][j] - F[i][j] > 0 && h[i]==h[j]+1)
            {
               pushed = true;
               int pf = min(C[i][j] - F[i][j], e[i]);
               F[i][j] += pf; F[j][i] = -F[i][j];
               e[i] -= pf; e[j] += pf;               
               if(e[i]==0)
               {
                  sz--;
                  break;
               }
            }

         if(!pushed)
         {
            h[i] = inf;
            for(j=0; j < N; ++j)
               if(C[i][j]-F[i][j] > 0 && h[j]+1 < h[i])
                  h[i] = h[j]+1;

            if(h[maxh[sz-1]] < h[i])
            {
               sz=0;
               break;
            }
         }            
      }
   }
   return e[t];
}

int main(int argv, char* arg[])
{
   #ifndef ONLINE_JUDGE
      freopen("in","r",stdin);      
   #endif   

   char buff[256];
   char comps[256];   
   int expected_flow = 0;

   clear();   
         
   while( 1 )
   {
      cin.getline( buff,256 );

      if(buff[0]=='\0')
      {
         bool cant = false;
         int flow = 0;
         
         if(expected_flow <= 10)
         {
            for(int i=0; i < 10; ++i)               
                  C[26+i][t] = 1;

            flow = maxFlow();
         }
         else
            cant = true;

         if(expected_flow != flow || cant)
         {
            cout << '!' << endl;
         }
         else
         {
            for(int i = 26; i < s; ++i)
            {
               char c = '_';
               if(F[i][t] > 0)
               {
                  for(int k = 0; k < 26; ++k)
                  {
                     if(F[k][i] > 0)
                     {
                        c = 'A' + k;
                        break;
                     }
                  }
               }
               cout << c;
            }                  
         }

         cout << endl;
         if(cin.eof()) return 0;                  
         
         clear();
         expected_flow = 0;
         continue;
      }
      
      istringstream iss(buff);
      string ss;

      iss >> ss;

      if(ss[0] < 'A' || ss[0] > 'Z') continue;      

      int job =  ss[0] - 'A';            
      int sz=0;
      char ch = ' ';
      while(1)
      {
         iss >> ch;

         if(ch >= '0' && ch <= '9')
         {   
            comps[sz++] = ch-'0'+26;
         }
         else
         {
            if(ch == ';')
            {
               for(int i=0;i<sz;++i)                   
                     C[job][comps[i]] = 1;   
               
               C[s][job] += ss[1] - '0';
               expected_flow += ss[1] - '0';
            }
            
            break;
         }
      }      
   }         

   return 0;
}


I'm new one in this.
Last edited by K0stIa on Sat Sep 25, 2010 8:11 am, edited 4 times in total.
K0stIa
New poster
 
Posts: 4
Joined: Thu Sep 23, 2010 10:20 pm

Re: Runtime Error

Postby helloneo » Fri Sep 24, 2010 4:11 pm

K0stIa wrote:hello, guys.

I tired to submit problems on this site. I think i solved this problem and have problems with I/O. Can anybody see on my code below ? If u can give me some advises how to write I/O for the problem on this site i'll be very thankful for u, coz i like problems on this site and dislike the format input data on it.

I'm new one in this.



My code takes input like this..

Code: Select all
while (gets(buf)) {
    ...
    ...
    sscanf(buf, "%s%s", str1, str2);
    ...
    ...
    while (gets(buf)) {
        if (strlen(buf) <= 0)
            break;
        sscanf(buf, "%s%s", str1, str2);
        ...
        ...
    }
    ...
    ...
}


I don't know C++, so I can't tell you how to do this with C++ iostream
helloneo
Guru
 
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: Runtime Error

Postby K0stIa » Fri Sep 24, 2010 4:42 pm

What u can say about my approach ?
It's one of the usual approaches in such kind problems. We add source & sink nodes, first we connect with jobs, second with computers. Edges capacity from source to jobs nodes are equal to amount of jobs, capacities from computer node to sink are equal one. So, in such graph max flow goes throw the matching edges for jobs & computers as we want. If it's no hard for u, please see my code. there is simple implementation of preflow-push algorithm for max-flow problem.
I don't understand what's wrong with my code...

p.s. IO part looks like ur...

and I have one request more, can u give me some advices about IO data in this site, it seems to me there are many problems which are not difficult but have such kind of Input data which have the most general form which are not contradict with condition.

And what can u say about next test ?

A1 13579;
B1 a-123;

UVA toolkit returns "_A________"

does ur code provide this test ?
K0stIa
New poster
 
Posts: 4
Joined: Thu Sep 23, 2010 10:20 pm

Re: Runtime Error

Postby helloneo » Fri Sep 24, 2010 5:30 pm

K0stIa wrote:What u can say about my approach ?
It's one of the usual approaches in such kind problems. We add source & sink nodes, first we connect with jobs, second with computers. Edges capacity from source to jobs nodes are equal to amount of jobs, capacities from computer node to sink are equal one. So, in such graph max flow goes throw the matching edges for jobs & computers as we want. If it's no hard for u, please see my code. there is simple implementation of preflow-push algorithm for max-flow problem.
I don't understand what's wrong with my code...

p.s. IO part looks like ur...

and I have one request more, can u give me some advices about IO data in this site, it seems to me there are many problems which are not difficult but have such kind of Input data which have the most general form which are not contradict with condition.

And what can u say about next test ?


UVA toolkit returns "_A________"

does ur code provide this test ?




Is that valid input..?
My AC code returns "_AB_______" :(

Anyway, your approach look correct..
But, your code is missing '\n' after the last case.. (when the output of the last case is not '!')
helloneo
Guru
 
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: Runtime Error

Postby K0stIa » Fri Sep 24, 2010 6:04 pm

helloneo wrote:
Is that valid input..?
My AC code returns "_AB_______" :(

Anyway, your approach look correct..
But, your code is missing '\n' after the last case.. (when the output of the last case is not '!')


So, it's still WA :( I'm very disappointed. Can u show me ur code ? I don't understand what wrong with it :(

And, if there multi answer allowed, what kind of case I should to choose for my answer ?

And, what do u think about next test?
A1 2;
C1 1;
B1 12;
B1 1234;

According to the UVA toolkit the answer must be equal to "_CABB_____";
now I'm going to research this test case more deeply.

User 1 comes to solve him one problem "A", he can to do it only on 2nd computer,
then user 2 has one problem "C" and he can solve it only on first computer,
user 3, have one problem B , and cans solve it only on first r second machine,
user 4, as user 3, also has the same "B", but he can solve it on 1,2,3,4 computers.

according to the uva toolkits answer user 3 can solves his problem on computer 3 & 4 also, it looks naturally if user 3 and 4 has problems identical "B".
Ok, lets try to look on the next two test cases:

A1 2;
C1 1;
V1 234;
B1 2345;
B1 3;

and

A1 2;
C1 1;
V1 23;
B1 2345;
B1 3;

Who can explain to me why first has answer "_CABVB____" and second has "_CAVBB____" according to the UVA toolkit?

Who has solved this damned PROBLEM ?

So, i'm interested in input data from the UVA server, how i can get it ?
K0stIa
New poster
 
Posts: 4
Joined: Thu Sep 23, 2010 10:20 pm

Re: 259 - optimizing..

Postby helloneo » Mon Sep 27, 2010 11:31 pm

I PMed you..

Don't go deeper.. There are many other good problems.. :)
helloneo
Guru
 
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 259 - optimizing..

Postby AhmadKhatar » Fri Jul 20, 2012 5:56 pm

Hi!
Does any body know where my mistake is?
I spent a lot of time but I couldn't find it! :(
Thanks in advance! :D
Code: Select all
#define SOURCE 36
#define SINK 37
#define FIRSTCMP 26

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

#include <queue>
using std::queue;

#include <string>
using std::string;

using std::min;

int f [ 38 ][ 38 ]; // 0..25 are chars, 26..35 are computers, 36 is source, 37 is sink,
int p [ 38 ];
int totalWorks;

void process();
int bfs();

int main()
{
   char tempL [ 15 ];

   // initialize
   for ( int i = 0; i < 38; i++ )
   {
      for ( int j = 0; j < 38; j++ )
      {
         f[ i ][ j ] = 0;
      }
   }

   totalWorks = 0;


   while ( cin.getline( tempL, 15, '\n' ) )
   {
      if ( tempL[ 0 ] == NULL )
      {
         process();

         // refresh
         for ( int i = 0; i < 38; i++ )
         {
            for ( int j = 0; j < 38; j++ )
            {
               f[ i ][ j ] = 0;
            }
         }

         totalWorks = 0;
      }
      else
      {
         totalWorks += tempL[ 1 ] - 48;
         int lastGoodInd = 3;
         for ( int i = 4; tempL[ i ] != ';'; i++ )
         {
            lastGoodInd++;
         }

         f[ SOURCE ][ ( tempL[ 0 ] - 65 ) ] = tempL[ 1 ] - 48;
         for ( int i = 3; i <= lastGoodInd; i++ )
         {
            f[ ( tempL[ 0 ] - 65 ) ][ FIRSTCMP + tempL[ i ] - 48 ] = tempL[ 1 ] - 48; // here we could assign to 1
            f[ FIRSTCMP + tempL[ i ] - 48 ][ SINK ] = 1;
         }
      }
   }

   return 0;
}

void process()
{
   string toOut = "__________";
   
   int maxFlow = 0;
   int incPath;
   while ( bfs() != 0 )
   {
      incPath = -1;
      for ( int i = SINK; i != SOURCE; i = p[ i ] )
      {
         if ( incPath == -1 )
         {
            incPath = f[ p[ i ] ][ i ];
         }
         else
         {
            incPath = min( incPath, f[ p[ i ] ][ i ] );
         }
      }

      for ( int i = SINK; i != SOURCE; i = p[ i ] )
      {
         f[ p[ i ] ][ i ] -= incPath;
         f[ i ][ p[ i ] ] += incPath;
      }

      maxFlow += incPath;
   }

   if ( maxFlow < totalWorks )
   {
      cout << "!" << endl;
   }
   else
   {
      for ( int i = 0; i <= 25; i++ )
      {
         for ( int j = 26; j <= 35; j++ )
         {
            if ( f[ j ][ i ] == 1 ) // NOTE THAT here f[ i ][ j ] == 0 doesn't work
            {
               toOut[ j - 26 ] = static_cast<char>( ( i % 26 ) + 65 );
            }
         }
      }

      cout << toOut << endl;
   }
}

int bfs() // returns sink plus the augmenting path
{
   int curNode;
   queue<int> q;
   int color[ 38 ];
   
   for ( int i = 0; i < 38; i++ )
   {
      color[ i ] = 0; // 0 is white, 1 is gray
      p[ i ] = -1;
   }

   q.push( SOURCE );
   color[ SOURCE ] = 1;

   while (!q.empty())
   {
      curNode = q.front();
      q.pop();

      for ( int i = 0; i < 38; i++ )
      {
         if ( f[ curNode ][ i ] > 0 && color[ i ] == 0 )
         {
            p[ i ] = curNode;
            color[ i ] = 1;
            if ( i == SINK )
            {
               return SINK; // a positive integer
            }
            q.push( i );
         }
      }
   }

   return 0; // because no vertex has value 0 (vertex numbers start from 1) no problem is with 0
}
AhmadKhatar
New poster
 
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Next

Return to Volume II

Who is online

Users browsing this forum: No registered users and 1 guest