10044 - Erdos Numbers

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

TimeString
New poster
Posts: 26
Joined: Mon Nov 13, 2006 3:53 am

Post by TimeString » Tue Jul 24, 2007 3:38 pm

Thanks Maniac. I simply followed what you said and got AC. The limit you gave is helpful.

Let me try to say the input format again(for each case):

Code: Select all

P N
paper database 1
paper database 2
...
paper database P
author 1
author 2
...
author N
For each line of paper database, like Maniac said, there are two formats, one of these is:

Code: Select all

FirstName1, LastName1, FirstName2, LastName2, ... FirstNameX, LastNameX: <the rest is not important, just ignore it>
Then this paper contains X authors.

Or another kind:

Code: Select all

FirstName1, LastName1, FirstName2, LastName2, ... FirstNameX, LastNameX, FirstNameY: <the rest is not important, just ignore it>
This is also contains X authors. Ignore FirstNameY.

Finally, the format of name lines is:

Code: Select all

FirstName1, LastName1
Note that the format of all available names, i.e., excluding like FirstNameY:, in the input is:

Code: Select all

FirstName, LastName
(FirstName, follows a comma, follows at least one whitespace, follows LastName)
So I assure Alexis Blaze that the input you post would not appear in judge data.

User avatar
TripShock
New poster
Posts: 14
Joined: Tue Jun 20, 2006 9:33 am

Runtime Error - Invalid Memory Reference

Post by TripShock » Thu Aug 02, 2007 1:57 pm

My program gives Runtime Error - Invalid Memory Reference. I understand this could be because my arrays are going out of bounds some place but I can't spot anything. Someone help please...

Code: Select all

#include <iostream>
#include <cstring>
#include <cctype>

using namespace std;

const int MAX = 6000;
char Connections[MAX][MAX] = { 0 };
char Authors[MAX][1024] = { 0 };
int NumAuthors = 0;
char NewAuthors[MAX][1024] = { 0 };
int NumNewAuthors = 0;
int ErdosNumber[MAX] = { 0 };

void DoErdos(int Source)
{
	int Number = ErdosNumber[Source] + 1;

	for (int i = 0; i < NumAuthors; i++)
	{
		if ((i != Source) && Connections[Source][i] && ((Number < ErdosNumber[i]) || (ErdosNumber[i] == -1)))
		{
			if (Number)
				ErdosNumber[i] = Number;
			DoErdos(i);
		}
	}
}

int main()
{
	int Scenarios = 0;
	int Papers = 0;
	int Names = 0;

	cin >> Scenarios;
	for (int i = 1; i <= Scenarios; i++)
	{
		cin >> Papers;
		cin >> Names;
		cin.get();

		memset(Connections, 0, MAX * MAX);

		for (int j = 1; j <= Papers; j++)
		{
			char FirstName[1024] = { 0 };
			char LastName[1024] = { 0 };

			char Input = 0;
			int Pos = 0;

			NumNewAuthors = 0;
			while (Input != ':')
			{
				Input = 0;
				Pos = 0;
				while ((Input = cin.get()) == ' ');
				do
				{
					FirstName[Pos++] = tolower(Input);
					Input = cin.get();
				} while ((Input != ',') && (Input != ':'));
				FirstName[Pos] = 0;

				if (Input != ':')
				{
					Input = 0;
					Pos = 0;
					while ((Input = cin.get()) == ' ');
					do
					{
						LastName[Pos++] = tolower(Input);
						Input = cin.get();
					} while ((Input != ',') && (Input != ':'));
					LastName[Pos] = 0;

					strcat(FirstName, ",");
					strcat(FirstName, LastName);
					strcpy(NewAuthors[NumNewAuthors++], FirstName);
					bool Duplicate = false;
					for (int k = 0; k < NumAuthors; k++)
					{
						if (!strcmp(Authors[k], FirstName))
						{
							Duplicate = true;
							break;
						}
					}
					if (!Duplicate)
						strcpy(Authors[NumAuthors++], FirstName);
				}
			}
			while (cin.get() != '\n');

			for (int k = 0; k < NumNewAuthors; k++)
			{
				for (int l = 0; l < NumNewAuthors; l++)
				{
					int Index1 = 0;
					int Index2 = 0;
					for (Index1 = 0; strcmp(Authors[Index1], NewAuthors[k]); Index1++);
					for (Index2 = 0; strcmp(Authors[Index2], NewAuthors[l]); Index2++);
					Connections[Index1][Index2] = 1;
					Connections[Index2][Index1] = 1;
				}
			}
		}

		for (int j = 0; j < NumAuthors; j++)
			ErdosNumber[j] = -1;

		int ErdosIndex = 0;
		for (ErdosIndex = 0; (ErdosIndex < NumAuthors) && strcmp(Authors[ErdosIndex], "erdos,p."); ErdosIndex++);

		if (ErdosIndex < NumAuthors)
		{
			ErdosNumber[ErdosIndex] = 0;
			DoErdos(ErdosIndex);
		}

		cout << "Scenario " << i << endl;
		for (int j = 1; j <= Names; j++)
		{
			char Name1[1024] = { 0 };
			char Name2[1024] = { 0 };

			cin.getline(Name1, 1024);
			int l = 0;
			for (int k = 0; Name1[k]; k++)
			{
				if (Name1[k] != ' ')
					Name2[l++] = tolower(Name1[k]);
			}
			Name2[l] = 0;

			int Index = 0;
			for (Index = 0; strcmp(Authors[Index], Name2); Index++);

			cout << Name1 << " ";
			if (ErdosNumber[Index] != -1)
				cout << ErdosNumber[Index];
			else
				cout << "infinity";

			cout << endl;
		}
	}

	return 0;
}

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft » Thu Aug 09, 2007 4:57 pm

Hi ppl!
Can anyone with AC solution please provide me some tricky testcases for that problem. I don't want to post source as it might be hard to read for you, so I'd like to get the cases instead.
I have array [1..1002][1..5001] for the Graph and I know it's enough, and I have a queue with 50000 elements, the queue is (dunno in English...) "looped".

Thanx!
Now I lay me down to sleep...
my profile

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Thu Aug 09, 2007 5:16 pm

My AC program can take maximum 10000 authors..
I don't know how many authors there would be..
But, I'm sure it'll be more than 5000 ...

zero_cool
New poster
Posts: 27
Joined: Fri Sep 02, 2005 6:33 am

weird memory limit exceeded

Post by zero_cool » Wed Aug 22, 2007 1:11 pm

Hi guys,
I got the message memory limit exceeded which I don't understand why. Can you guys please help me out? Thanks.

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;

const int MAX=6000;
const int MAXC=200;

int connection[MAX][MAX];
char authors[MAX][MAXC];
int numAuthors;
char newAuthors[MAX][MAXC];
int numNewAuthors;
int erdosNumber[MAX];

int main() {
int tc;
int P,N;

char input;
int pos;
int index1,index2;
char firstName[MAXC];
char lastName[MAXC];

cin >> tc;
for (int h=0;h<tc;h++) {
cin >> P >> N;
cin.ignore(1000,10);

// Initialize
numAuthors=1;
strcpy(authors[0],"ERDOS,P.");
erdosNumber[0]=0;
for (int i=0;i<MAX;i++)
for (int j=0;j<MAX;j++)
connection[j]=0;

for (int i=0;i<P;++i) {
input=0;
numNewAuthors=0;
while (input!=':') {
input=cin.get();
while (input==' ' || input=='\t' || input=='\r') input=cin.get();
pos=0;
while (input!=',') {
firstName[pos++]=toupper(input);
input=cin.get();
}
firstName[pos]=0;

input=cin.get();
while (input==' ' || input=='\t' || input=='\r') input=cin.get();
pos=0;
while (input!=',' && input!=':' && input!='\n' && input!=EOF) {
//cout << input;
lastName[pos++]=toupper(input);
input=cin.get();
}
lastName[pos]=0;

strcat(firstName,",");
strcat(firstName,lastName);
strcpy(newAuthors[numNewAuthors++],firstName);
bool duplicate = false;
for (int k = 0; k < numAuthors; k++) {
if (strcmp(authors[k], firstName)==0) {
duplicate = true;
break;
}
}
if (!duplicate)
strcpy(authors[numAuthors++], firstName);
}
cin.ignore(1000,10);

/* Debugging
for (int j=0;j<numNewAuthors;j++)
cout << newAuthors[j] << ' ';
cout << endl;
*/

for (int j=0;j<numNewAuthors;j++) {
index1=0;
while (index1<numAuthors && strcmp(newAuthors[j],authors[index1])!=0) index1++;
for (int k=j+1;k<numNewAuthors;k++) {
index2=0;
while (index2<numAuthors && strcmp(newAuthors[k],authors[index2])!=0) index2++;
connection[index1][index2]=1;
connection[index2][index1]=1;
}
}


}

/* Debugging
for (int j=0;j<numAuthors;++j)
cout << authors[j] << ' ';
cout << endl;
*/

cout << "Scenario " << h+1 << endl;
for (int i=0;i<N;++i) {
cin.getline(firstName,1000);
cout << firstName << endl;
}
}

return 0;
}

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

Re: weird memory limit exceeded

Post by mf » Wed Aug 22, 2007 1:23 pm

And what did you expect?
"int connection[6000][6000];" is 6000^2*4 bytes = 137.3 Mb. Default memory limit is 32 Mb.

zero_cool
New poster
Posts: 27
Joined: Fri Sep 02, 2005 6:33 am

Post by zero_cool » Wed Aug 22, 2007 11:56 pm

Thanks for your reply. I try to delete all the code and just have the main method to return 0. It doesn't return memory limit exceeded that way. But, when I put some code, it returns memory limit exceeded. Can anyone explain to me why this is happening? Is the way the compiler work ignored unused declaration of array?

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

Post by mf » Thu Aug 23, 2007 2:54 am

If you see "Minimum" as memory usage, that means the judge couldn't determine your program's memory usage. This often happens for programs that terminate very quickly.

Ion2Atom
New poster
Posts: 3
Joined: Mon Sep 25, 2006 9:41 pm

WA/RTE

Post by Ion2Atom » Mon Sep 24, 2007 4:33 pm

I finally figured out how to get past the TLE. Unfortunately now I have WA on PC and RTE on UVA. Can anybody give out some test cases? I did a simple one like this:

Code: Select all

1
12 16
Erdos, P., C, C: asdf
Erdos, P., B, B: asdf
Erdos, P., A, A: asdfa
B, B, G, G: asdf
A, A, H, H: asdf
H, H, I, I: asdf
I, I, J, J, K, K: asdf
J, J, L, L: asdf
L, L, F, F: asdf
C, C, F, F: aadsf
F, F, D, D, E, E: asdf
M, M, N, N, O, O: asdf
Erdos, P.
A, A
B, B
C, C
D, D
E, E
F, F
G, G
H, H
I, I
J, J
K, K
L, L
M, M
N, N
O, O
which gives the output of:

Code: Select all

Scenario 1
Erdos, P. 0
A, A 1
B, B 1
C, C 1
D, D 3
E, E 3
F, F 2
G, G 2
H, H 2
I, I 3
J, J 4
K, K 4
L, L 3
M, M infinity
N, N infinity
O, O infinity
It also passes the sample input, and double sample input. I'm really stumped on why this is incorrect. Thanks for any help! (code following)

Note: I have tried removing all white space (/t, /r, ' ', & '.') like it says earlier in the thread, and it still doesn't work. So I think I must be doing something different wrong. :\

Code: Select all

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <list>
#include <queue>

//max links 500
//max person names length 100
//max input line length 10000
//max names 5000

std::vector<bool> T;
std::vector<int> mem;
std::vector<std::vector<bool> > matrix;

void solve(int from);
std::string removeWhite(std::string str);

int main(){
   
    int cases;
    int paper_count;
    int author_count;
    int count;
    int C;
    int B;
    
    std::string line;
    std::string temp;
    
    char A[1000];
    
    char *P;
    
    std::vector<std::vector<std::string> > papers;
    std::vector<std::string> S;
    std::map<std::string, int> authors;
    std::map<std::string, int>::iterator iter;
   
    std::cin >> cases;
   
    for(int i = 0; i < cases; i++){
        papers.resize(0);
        matrix.resize(0);
        T.resize(0);
        authors.erase(authors.begin(), authors.end());
       
        std::cin >> paper_count >> author_count;
        
        papers.resize(paper_count);
       
        count = 0;
        std::getline(std::cin, line); //garbage - whitespace
        for(int j = 0; j < paper_count; j++){
            line = ""; 
            std::getline(std::cin, line);

            strcpy(A, line.c_str());            
            P = strtok(&A[0], ",");
            while(P != NULL){
               temp = std::string(P); 
               papers[j].push_back(temp);
               P = strtok(NULL, ",");
            }
            
            line = papers[j][papers[j].size()-1];
            papers[j].pop_back();
            strcpy(A, line.c_str());
            
            P = strtok(&A[0], ":");
            temp = std::string(P);
            papers[j].push_back(temp);
            while(P != NULL){
               P = strtok(NULL, ":");
            }
            
            S.resize(0);
            for(int p = 0; p < papers[j].size(); p+=2){
                S.push_back(papers[j][p]+ "," + papers[j][p+1]);
            }
            papers[j] = S;
            
            //remove leading spaces
            for(int o = 0; o < papers[j].size(); o++){
               if(papers[j][o][0] == ' '){
                  papers[j][o] = papers[j][o].substr(1, papers[j][o].length()-1);
               }
               authors[papers[j][o]] = count++;
            }
        }
         
        //init matrix
        T.resize(count, false);
        matrix.resize(count, T);
        
        //adjacency matrix
        for(int pedro_for_president = 0; pedro_for_president < papers.size(); pedro_for_president++){
           for(int w = 0; w < papers[pedro_for_president].size(); w++){
              C = authors[papers[pedro_for_president][w]];
              for(int q = 0; q < papers[pedro_for_president].size(); q++){
                  B = authors[papers[pedro_for_president][q]];
                  if(C != B){
                     matrix[C][B] = true;
                     }
               }
           }
        }
        
        std::cout << "Scenario " << i+1 << "\n";
        
        mem.resize(0);
        mem.resize(matrix.size(), -1);
        
        solve(authors["Erdos, P."]);
        for(int k = 0; k < author_count; k++){
            std::getline(std::cin, line);
            
            //output
            std::cout << line << " ";
            if(mem[authors[line]] == -1){
               std::cout << "infinity";
            }
            else{
               std::cout << mem[authors[line]];
            }
            std::cout << "\n";
        }
    }
}

void solve(int from){
  std::vector<bool> visited;
    
  std::queue<int> Q;

  int jumps = 0;
  int to_pop;  
  
  visited.resize(0);
  visited.resize(matrix.size(), false);
    
  visited[from] = true;  
  Q.push(from);

  while(Q.empty() == false){
    to_pop = Q.size();
    
    for(int j = 0; j < to_pop; j++){
       mem[Q.front()] = jumps;      
        
       for(int i = 0; i < matrix.size(); i++){
          if((matrix[Q.front()][i]) &&
             (visited[i] == false)){
             visited[i] = true;
             Q.push(i);
          }
       }
       
       Q.pop();
    }
    jumps++;
  }  
}

std::string removeWhite(std::string str){
    
}
[/code][/list]

kason
New poster
Posts: 4
Joined: Sat Dec 01, 2007 12:44 pm

help

Post by kason » Sat Dec 01, 2007 12:58 pm

could someone tell me....

if the paper database is

___A,___B___,_C,_D_,_E,_F: Newtonian forms of prime factor matrices

the authors' name are still

A,_B
C,_D
E,_F

or

A,___B
C,_D
E,_F

or

something else ~"~?????


ps. _ mean a space

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: help

Post by helloneo » Sat Dec 01, 2007 1:14 pm

kason wrote:could someone tell me....

if the paper database is

___A,___B___,_C,_D_,_E,_F: Newtonian forms of prime factor matrices

the authors' name are still

A,_B
C,_D
E,_F

or

A,___B
C,_D
E,_F

or

something else ~"~?????


ps. _ mean a space

You should change it this way..

A,_B
C,_D
E,_F


Hope this help.. :-)

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Fri Mar 21, 2008 11:11 pm

can some give me some special input-output?
i got WA
I ALSO check all the input which is given in this board.
but i don't know whats my problem.
is it ok to get the input format?
or is it okk to run the loop until ':';

Code: Select all

for(j=1;j<=x;j++)
		{
			gets(string);
			count=0;
			s=0;
			d=0;
			ch='2';
			for(k=0;ch!=':';k++)
			{
....................................
....................................
ples tell me.
''I want to be most laziest person in the world''

rs17
New poster
Posts: 5
Joined: Tue Jul 03, 2007 5:49 am
Location: UNKNOWN
Contact:

Re: 10044 - Erdos Numbers

Post by rs17 » Mon Jul 14, 2008 2:45 pm

After lots of REs I realize that there must be some extra empty lines in the input file!!!(There's nothing about this in the problem statement.) I changed my program and got Accepted.
How did I fall in love with PERL?

AltCtrlDel
New poster
Posts: 3
Joined: Sun Jun 04, 2006 1:08 pm

Isn't that meaningless?!

Post by AltCtrlDel » Sat May 30, 2009 9:14 pm

I kept wondering about why I am getting RTE until I found on this forum a hint about a possible author name without first name initials and that it should be ignored! Now I got AC. But isn't it meaningless?! What skill does such trick measure?!! This is nonsensical!

Ivan Goroun
New poster
Posts: 10
Joined: Sun Dec 20, 2009 12:01 am

Re: 10044 - Erdos Numbers

Post by Ivan Goroun » Sun Jan 10, 2010 11:28 am

Well, this is one messed up problem. Here's the input/output pair which finally got my code accepted. Part of it was earlier in this thread, but it was not sufficient.

Input:

Code: Select all

 2
  4    3
    Smith,   M.N.,  Martin,    G.,    Erdos, P.: Newtonian forms of prime factor matrices 
Erdos,              P.,  Reisig, W.: Stuttering in petri nets
Smith, M.N., Chen, X.: First oder derivates in structured programming
Jablonski, T., Hsueh, Z.: Selfstabilizing data structures
 Smith,          M.N.
   Hsueh,    Z.
Chen, X.
12 19
Erdos, P., C, C., FUFAIL: asdf
Erdos, P., B, B.: asdf
Erdos, P., A, A.: asdfa
B, B., G, G.: asdf
A, A., H, H.: asdf
H, H., I, I.: asdf
I, I., J, J., K, K.: asdf
J, J., L, L.: asdf
L, L., F, F.: asdf
C, C., F, F.: aadsf
F, F., D, D., E, E.: asdf
M, M., N, N., O, O.: asdf
Erdos, P.
A, A.
B, B.
C, C.
D, D.
E, E.
F, F.
G, G.
H, H.
I, I.
J, J.
K, K.
L, L.
M, M.
N, N.
O, O.
WTF, F.
WTF.
WTF, U.
Output:

Code: Select all

Scenario 1
Smith, M.N. 1
Hsueh, Z. infinity
Chen, X. 2
Scenario 2
Erdos, P. 0
A, A. 1
B, B. 1
C, C. 1
D, D. 3
E, E. 3
F, F. 2
G, G. 2
H, H. 2
I, I. 3
J, J. 4
K, K. 4
L, L. 3
M, M. infinity
N, N. infinity
O, O. infinity
WTF, F. infinity
WTF. infinity
WTF, U. infinity
I'm sure there's some overkill here, but if your program handles this input it should be accepted. Oh, and that "FUFAIL" in the paper authors without an initial - you must handle that 100%. Same goes for "WTF" without the initial in the names list.

Post Reply

Return to “Volume 100 (10000-10099)”