10044 - Erdos Numbers

[davidbak]

For me the keys to this problem were revealed by this forum thread, thank you!

1) Maximum input line length was longer than I assumed.
2) I wasn't handling the case where names didn't have the "first name initials" part.

Thanks to you also, on this thread, for learning the trick on how to get the judge to return useful debugging information by forcing a TLE, too much output, etc. etc. I'm sure that'll come in handy in the future!

BTW, for those of you wrestling with problem size limits - needing to know problem sizes so you can allocate arrays and such in advance - one of the principal advances in programming languages in the past 20 years has been the widespread acceptance of languages that include data structures that can be sized at run time (to the limits of available memory), not compile time. We're not programming in Fortran or COBOL here: use the features of the language to make your life easier.

[Imti]

I got it accepted after lot of WA.The mistake I did was in input parsing.Really,input parsing of this problem is quite embarrassing.However,in this thread,some tricks U may get ,which works but unnecessary.Just strictly follow sample format given problem statement to parse the input.I'm giving some tricky cases here,Try to get it from there:
Input:

Code: Select all

5
1 2
Erdos, P. , ghj, P.:fh
ghj,P.
ghj, P.
1 2
Erdos, P., ghj, P.:fh
ghj,P.
ghj, P.
1 2
Erdos, P.,  ghj, P.:fh
ghj,P.
ghj, P.
1 2
Erdos, P.,  ghj,P.:fh
ghj,P.
ghj, P.


Output:

Code: Select all

Scenario 1
ghj,P. infinity
ghj, P. infinity
Scenario 2
ghj,P. infinity
ghj, P. 1
Scenario 3
ghj,P. infinity
ghj, P. 1
Scenario 4
ghj,P. 1
ghj, P. infinity


[danieldonadon]

The lack of information in this problem is quite annoying, taking you a long time trying to figure out what's the best approach without using dynamic structures, and if they are fast and not too much memory consuming.
Here is an "update" of what Maniac has already discovered about the input data size years ago, along with my own observations:

- maximal number of different persons in all papers together of one scenario is less than 5001

Checked, I use some 5,000 pre-allocated memory vectors and a 5,000 x 5,000 matrix with no ME.

- maximal length of input lines is less than 10001

Each line from the input data has actually less than 1024 characters.

- maximal length of person names is less than 101

Each person's full name (like "Erdos, P.") has less than 32 characters after removing extra spaces (it is, if there really are such spaces).

- maximal number of links from one person to others is less than 501

(I have not checked this.)

I hope this missing information may help other people as well.

[plamplam]

My accepted code produces different results on your input @Imti:

Code: Select all

Scenario  1
ghj,P. infinity
ghj, P. infinity
Scenario  2
ghj,P. infinity
ghj, P. 1
Scenario  3
ghj,P. infinity
ghj, P. 1
Scenario  4
ghj,P. 1
ghj, P. infinity
Scenario  5
ghj, P. infinity
ghj, P. infinity

You don't need to remove extra spaces, I just used the ',' character as separator. But input parsing is really annoying

[three0s]

Well, I think the best way to read input is to find ".," and ".:" instead of "," and ":" .
I am also sure that there is no extra blank spaces in each line of input. (Mine got AC)

[vpanait]

miserable problem statement, I got AC using a parse after {,} and {:}

it may happen that "erdos" is actually not in the list, so you cannot do BFS, or it may happen that a name from the author's list, is also not in the original nodes.
so if you use a hash to keep all names, just check if the "name" is in the hash or not.. before doing any computation..

[AhmadKhatar]

Hi!
Sorry! I got RE!
Here is my code:

Code: Select all

#include <iostream>
#include <map>
#include <cstring>
#include <string>
#include <queue>
#include <cctype>

using namespace std;

int p, n;
map<string,int> aut;
int mat [ 1000 ][ 1000 ];
int nameCnt;
int len [ 1000 ];
int color [ 1000 ];

void preprocess();
void process( string name );

int main()
{
   int tNo;
   char tLine [ 1000 ];
   string lineStr;
   string pStr [ 1000 ];
   int pCnt;

   cin >> tNo;
   for ( int i = 0; i < tNo; i++ )
   {
      nameCnt = 0;
      aut.clear();
      memset( mat, 0, sizeof(mat) );
      cin >> p >> n;
      cin.ignore();
      for ( int j = 0; j < p; j++ )
      {
         cin.getline( tLine, 1000, '\n' );
         lineStr = tLine;
         int comInd [ 1000 ];
         //
         int comCnt = 0;
         comInd[ comCnt++ ] = -2;
         for ( int k = 0; k < lineStr.length(); k++ )
         {
            if ( lineStr[ k ] == ',' || lineStr[ k ] == ':' )
            {
               comInd[ comCnt++ ] = k;
            }
         }
         
         pCnt = 0;
         for ( int k = 2; k < comCnt; k += 2 )
         {
            int stInd, endInd;
            stInd = comInd[ k - 2 ] + 2;
            endInd = comInd[ k ] - 1;
            pStr[ pCnt++ ] = lineStr.substr( stInd, endInd - stInd + 1 );
            if ( aut.find( lineStr.substr( stInd, endInd - stInd + 1 ) ) == aut.end() )
            {
               aut[ lineStr.substr( stInd, endInd - stInd + 1 ) ] = nameCnt++;
            }
         }
         //

         for ( int i = 0; i < pCnt; i++ )
         {
            for ( int j = i + 1; j < pCnt; j++ )
            {
               mat[ aut[ pStr[ i ] ] ][ aut[ pStr[ j ] ] ] = mat[ aut[ pStr[ j ] ] ][ aut[ pStr[ i ] ] ] = 1;
            }
         }
      }
   
      preprocess();
      cout << "Scenario " << i + 1 << endl;
      for ( int k = 0; k < n; k++ )
      {
         cin.getline( tLine, 1000, '\n' );
         lineStr = tLine;
         process( lineStr );
      }
   }

   return 0;
}

void process( string name )
{
   cout << name << " ";
   if ( aut.find( name ) == aut.end() )
   {
      cout << "infinity" << endl;
   }
   else
   {
      if ( len[ aut[ name ] ] == -1 )
      {
         cout << "infinity" << endl;
      }
      else
      {
         cout << len[ aut[ name ] ] << endl;
      }
   }
}

void preprocess()
{
   for ( int i = 0; i < nameCnt; i++ )
   {
      len[ i ] = -1;
   }

   if ( aut.find("Erdos, P.") != aut.end() )
   {
      // bfs
      queue<int> q;
      memset( color, 0, sizeof(color) );

      q.push( aut[ "Erdos, P." ] );
      color[ aut[ "Erdos, P." ] ] = 1;
      len[ aut[ "Erdos, P." ] ] = 0;

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

         for ( int i = 0; i < nameCnt; i++ )
         {
            if ( mat[ u ][ i ] == 1 && color[ i ] == 0 )
            {
               q.push( i );
               color[ i ] = 1;
               len[ i ] = len[ u ] + 1;
            }
         }
      }
   }
}

Please help and Thanks in advance!

[brianfry713]

You can see the reason for your compile error by clicking My Submissions, however, your code is producing a Runtime Error.

Try the I/O in this thread.

[brianfry713]

Try the I/O in this thread. See what plamplam and Imti posted recently.

[AhmadKhatar]

Hi!
Thanks for your help!
But after removing leading spaces I still get RE!