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

bluebird
New poster
Posts: 12
Joined: Mon Oct 17, 2005 2:35 am
Location: Canada

10044 Erdos Number WA

Post by bluebird » Thu Oct 27, 2005 2:33 am

For some reason my program keeps getting WA. I've tried the test cases from the previous post, and my I/O does what the previous posts suggested:
Upon closer inspection of my name-reading routine, I see that it was slightly more complicated than I described yesterday. Here's a detailed description (for reading an entire author, first and last name):
1. Skip whitespace
2. Add until null or ',' (there's your first name)
3. If we stopped on a ',': skip past it.
4. Skip whitespace
5. Add until null or ',' or ':' or whitespace (there's your last name)
6. Repeat reading names this way until the last char was null or ':'.
But I'm still stuck!!!

Here's my code:

Code: Select all

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


using namespace std;

int main()
{
  int testcases, P, N, init, erdoNum, inputNamePtr;
  short scenario;
  bool noLastName;
  string * namesOrder;
  map<string, int> namesOrderMap;
  map<string, int>::iterator iterp;
  string line, curName, inputName;
  multimap<string, string> nameMap;
  queue<string> tempNames;
  set<string> visited;
  vector<string> databaseLine;
  vector<string>::iterator iteri, iterj;
  multimap<string, string>::iterator iterm, itern;

  cin >> testcases;

  scenario = 1;

  while (testcases>0) {

    cin >> P;
    cin >> N;
    cin.ignore(); // skip \n

    nameMap.clear();


    for (short i=0; i<P; i++) {
      getline(cin, line);
      databaseLine.clear();
      while ((init = line.find(".,")) != string::npos) {
	inputNamePtr = 0;
	inputName = "";
	while (line[inputNamePtr] == ' ' && inputNamePtr<line.length())  
	  inputNamePtr++;
	while (line[inputNamePtr] != ',' && inputNamePtr<line.length()) {
	  inputName += line[inputNamePtr];
	  inputNamePtr++;
	  
	}
	inputName += ", ";
	inputNamePtr++;
	while (line[inputNamePtr] == ' ' && inputNamePtr<line.length())  
	  inputNamePtr++;
	while (line[inputNamePtr] != ',' && inputNamePtr<line.length()) {
	  inputName += line[inputNamePtr];
	  inputNamePtr++;
	  
	}
	databaseLine.push_back(inputName);
	line = line.substr(init+3, line.length() - (init+3));
      }
      inputNamePtr = 0;
      inputName = "";
      while (line[inputNamePtr] == ' ' && inputNamePtr<line.length())  
	inputNamePtr++;
      while (line[inputNamePtr] != ',' && inputNamePtr<line.length()) {
	inputName += line[inputNamePtr];
	inputNamePtr++;
	
      }
      inputName += ", ";
      inputNamePtr++;
      noLastName = true;
      while (line[inputNamePtr] == ' ' && inputNamePtr<line.length())  
	inputNamePtr++;
      while (line[inputNamePtr] != ':' && inputNamePtr<line.length()) {
	inputName += line[inputNamePtr];
	noLastName=false;
	inputNamePtr++;
      }
      if (!noLastName) databaseLine.push_back(inputName);


      for (iteri=databaseLine.begin(); iteri != databaseLine.end(); ++iteri) {
	for(iterj=databaseLine.begin(); iterj != databaseLine.end(); ++iterj) {
	  if (iteri != iterj) 
	    nameMap.insert(make_pair(*iteri, *iterj));
	}
      }
    }

    namesOrderMap.clear();
    namesOrder = new string[N];
    for (short i=0; i<N; i++) {      
      getline(cin, line);
      inputNamePtr = 0;
      namesOrder[i] = "";
      while (line[inputNamePtr] == ' ' && inputNamePtr<line.length())  
	inputNamePtr++;
      while (line[inputNamePtr] != ',' && inputNamePtr<line.length()) {
	namesOrder[i] += line[inputNamePtr];
	inputNamePtr++;
      }
      namesOrder[i] += ", ";
      inputNamePtr++;
      while (line[inputNamePtr] == ' ' && inputNamePtr<line.length())  
	inputNamePtr++;

      while (line[inputNamePtr] != ' ' && inputNamePtr<line.length()) {
	  namesOrder[i] += line[inputNamePtr];
	  inputNamePtr++;	  
      }
    }

    // processing
    while (! tempNames.empty() ) tempNames.pop();
    visited.clear();
    erdoNum = 0;

    namesOrderMap["Erdos, P."] = 0;
    tempNames.push("Erdos, P.");
    visited.insert("Erdos, P.");

    while (! tempNames.empty() ) {
      curName = tempNames.front();
      tempNames.pop();
      erdoNum++;
 
      iterm = nameMap.find(curName);
      itern = nameMap.upper_bound(curName);

      while( iterm != itern) {

	if (visited.find(iterm->second) == visited.end()) {
	  tempNames.push(iterm->second);
	  visited.insert(iterm->second);
	  if ((iterp=namesOrderMap.find(iterm->second)) == namesOrderMap.end()) {
	    namesOrderMap[iterm->second] = erdoNum;
	  }
	  else {
	    if (erdoNum <= iterp->second) iterp->second = erdoNum;
	  }	
	}

	++iterm;
      }

    }
    
    // output
    cout << "Scenario " << scenario << "\n";
    scenario++;
    for (short i=0; i<N; i++) {
      if (namesOrderMap.find(namesOrder[i]) != namesOrderMap.end()) 
	cout<<namesOrder[i]<<" "<<namesOrderMap[namesOrder[i]] << "\n";
      else
	cout<<namesOrder[i]<<" "<<"infinity"<<"\n";
    }


    // clean up
    delete[] namesOrder;
    testcases--;
  }

  return 0;

}
 
[/code]

bluebird
New poster
Posts: 12
Joined: Mon Oct 17, 2005 2:35 am
Location: Canada

Acc

Post by bluebird » Tue Nov 01, 2005 2:04 am

Finally got AC!!!! Kinda surprised no one spotted my error.

sectroyer
New poster
Posts: 8
Joined: Mon Nov 28, 2005 4:55 pm

10044

Post by sectroyer » Fri Dec 02, 2005 3:42 am

Hi I have a trouble with task 10044, could you help me ?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue Dec 13, 2005 5:57 am

Ok, this one is PITA. Especially if you are trying to do it in Java 1.1 (!@#$).

Without this thread I wouldn't have got an AC, so it deserves a bump (everything you should know is in the posts above).

Btw, if someone could post a method to read (just to read!) the input file in less than 0.7 secs in Java I would really like to know it. I've used System.in.read(), reading one byte at the time (can't assume anything here, it seems) and that was the best I got.

Darko

devious
New poster
Posts: 13
Joined: Wed Feb 22, 2006 1:26 am

What am I doing wrong?

Post by devious » Tue Mar 21, 2006 11:02 am

Accepted
Last edited by devious on Fri Feb 09, 2007 6:22 am, edited 1 time in total.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Tue Mar 21, 2006 11:35 am

Oh, man... you are doing them in order, aren't you? Well, you'll hit Yahtzee soon, so that would be the end of that :)

I really have nothing else to add, it is painful to even look at that code (mine is even worse), all tricky stuff is mentioned in this thread.

Hard part is reading the file in, the rest is just finding the shortest path.

Darko

Alexis Blaze
New poster
Posts: 8
Joined: Thu Jul 13, 2006 8:36 am
Location: Indonesia
Contact:

Post by Alexis Blaze » Fri Jul 14, 2006 11:38 am

i don't really get it... i'm still confused with the input output....

what would be the output for input like this....
or is there no such input output?

Code: Select all

1
3 5
Smith, Martin, G., Erdos, P.: Newtonian forms of prime factors
a,b,c,d,Smith: Something
       Smith, Chen,     X.: First order derivates in structured programming
Smith
a
a,b
Chen, X.
Chen,     X.
Thanks in advance :D

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri Jul 14, 2006 4:08 pm

My AC program crashes on that input.

Alexis Blaze
New poster
Posts: 8
Joined: Thu Jul 13, 2006 8:36 am
Location: Indonesia
Contact:

Post by Alexis Blaze » Fri Jul 21, 2006 8:28 am

i use vector<string> for the authors data, stl queue for BFS buffer and adjacency matrix for the graph implementation, what would be the size of the matrix? is 1000*1000 enough??? i think the size should be maxauthor*maxauthor, but how much is the maximum number of author??

i got a RTE so i tought the size of the matrix is to small, but when i open the e-mail about the RTE, it said that the RTE is because of "Abort signal from abort()"... what is the meaning of this? can anyone help me?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri Jul 21, 2006 5:26 pm

I don't know, I just checked, I don't have any numbers hardcoded in my Java program.

But in this same thread someone mentioned 5000 authors, try going with that number? Although that doesn't leave you much room (unless you use bitmasks or something)

chaturvedi
New poster
Posts: 8
Joined: Mon Jul 10, 2006 9:31 am

10044 RE!! Help Me!!!

Post by chaturvedi » Sat Jul 22, 2006 3:59 pm

I am getting RE even after increasing my array size, as people in earlier threads have indicated... It gives correct output for the test cases given in earlier threads... Can anybody tell me that is the input case sensitive? and will the format of the input be the exactly the same as given in the Sample i/o?? Help me please!!! Here's my code:

#include <stdio.h>
#include <string.h>

void modify(char *detail);
char *token(char *s1, int *p);
void print(int);
struct details
{
char name[100];
int erdosno,start,end;
}elements[1000];


void main()
{

int n,i,l,j,k,a,b,m,count,length,senti,change,erdos,names[10000];
char *perdos="Erdos, P.",detail[10000];
char *tokenptr,*t=detail;

scanf("%d",&n);

for(i=1;i<=n;i++)
{
count=0;
change=0;

scanf("%d %d",&a,&b);
for(j=1;j<=a;j++)
{
senti=0;
fflush(stdin);
gets(detail);
fflush(stdin);
modify(detail);
t=detail;
tokenptr=token(t,&length);
t=t+length;
k=0;
do
{
elements[k+count].erdosno=0;
elements[k+count].start=count;
strcpy(elements[k+count].name,tokenptr);
tokenptr=token(t,&length);
t=t+length;
if(strcmp(elements[k+count].name,perdos)==0)
senti=1;
k++;
}while(tokenptr!=NULL);


if(senti==1)
{
for(l=0;l<k;l++)
{
elements[l+count].erdosno=1;
change++;
}
}

for(l=0;l<k;l++)
elements[l+count].end=count+k-1;

count=count+k;
}

for(erdos=1;erdos<=a;erdos++)
{
for(j=0;j<count;j++)
{
if(elements[j].erdosno==erdos && strcmp(elements[j].name,perdos)!=0)
{
for(k=0;k<count;k++)
{
if (j!=k && (strcmp(elements[k].name,elements[j].name)==0))
{
for(m=elements[k].start;m<=elements[k].end;m++)
{
if(elements[m].erdosno==0)
{elements[m].erdosno=erdos+1;change++;}
if(change==count)
{elements[k].erdosno=erdos;
goto bahar;}

}
elements[k].erdosno=erdos;

}
}
}
}

}
bahar:

for(j=1;j<=b;j++)
{
fflush(stdin);
gets(detail);
fflush(stdin);
for(m=0;m<count;m++)
{
if(strcmp(detail,elements[m].name)==0)
names[j-1]=m;
}
}

printf("\nScenario %d",i);

for(j=0;j<b;j++)
{
if(elements[names[j]].erdosno==0)
printf("\n%s infinity",elements[names[j]].name);
else
printf("\n%s %d",elements[names[j]].name,elements[names[j]].erdosno);
}

printf("\n");

}

}



char *token(char *s1, int *p)
{
char *c=s1;
int sentinal=0;
int i;

for (i=0;s1!=NULL;i++)
{
if (s1=='.' && s1[i+1]==',')
{
c[i+1]='\0';
*p=i+3;
sentinal=1;
break;
}
}



if (sentinal==0)
c=NULL;
return c;
}

void modify(char *detail)
{
char s[10000];
int i=strcspn(detail,":");
strncpy(s,detail,i);
s=',';
s[i+1]=' ';
s[i+2]='\0';
strcpy(detail,s);
}

devious
New poster
Posts: 13
Joined: Wed Feb 22, 2006 1:26 am

Post by devious » Wed Feb 07, 2007 8:31 am

Edit: Got it accpeted

<:3)~~
New poster
Posts: 16
Joined: Wed Dec 06, 2006 6:57 pm

Post by <:3)~~ » Sun May 27, 2007 3:54 pm

can someone give some in/outputs for this problem.
i assumed the max authors per paper to be 1000 and max characters in author name to be 1000.
and erdos no. for Erdos itself to be 0.

my algo is as follows:

for( paper(i) ) // i goes from 1 to p
if(published by erdos)
erdos no.of all authors =1;
else
find min erdos no. among the authors;
erdos no.of other authors= min +1;

<:3)~~
New poster
Posts: 16
Joined: Wed Dec 06, 2006 6:57 pm

Post by <:3)~~ » Mon May 28, 2007 1:56 pm

is there any one who is free to reply?

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Mon May 28, 2007 3:14 pm

I used the same algo as you did, but you must repeat it until quiescence (no erdos number chaged during that pass), because an assignment in a later paper can change the erdos numbers of authors in an earlier paper.

If I remember correctly, there was some discussion on the board about spaces and punctuation in the name of an author (you might be able to find it somewhere on the board). This would mean that the same author could be spelled "Johnson, A. B.", Johnson, A.B.", "Johnson , AB", etc. at different places in the text. I don't know if that's true, but to be sure I remove all non alpha-numeric characters from the names before comparing them.

About the numbers: I use max. 10000 authors and max. 100000 titles, which is most likely a big over kill (but I get so frustrated from problems with no clear definition of their boundaries, that I tend to use the max. amount of memory in those cases). For author names I use standard Pascal strings, which have a length of 255 characters.

Hope it helps.
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

Post Reply

Return to “Volume 100 (10000-10099)”