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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

Edit: Got it accpeted

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

Post by <:3)~~ »

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)~~ »

is there any one who is free to reply?

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

Post by little joey »

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)”