259 - optimizing..

[jagadish]

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 ?

[m_thimma]

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

[baodog]

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 ... 


[rio]

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

[Kallol]

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;
}



[Jan]

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.

[Akter_Sust]

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.

[RenatoAlmeida]

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!

[K0stIa]

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.

[helloneo]

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

[K0stIa]

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 ?

[helloneo]

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 '!')

[K0stIa]

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 ?

[helloneo]

I PMed you..

Don't go deeper.. There are many other good problems..

[AhmadKhatar]

Hi!
Does any body know where my mistake is?
I spent a lot of time but I couldn't find it!
Thanks in advance!

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
}