Page 4 of 7
10044 Erdos Number WA
Posted: Thu Oct 27, 2005 2:33 am
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]
Acc
Posted: Tue Nov 01, 2005 2:04 am
by bluebird
Finally got AC!!!! Kinda surprised no one spotted my error.
10044
Posted: Fri Dec 02, 2005 3:42 am
by sectroyer
Hi I have a trouble with task 10044, could you help me ?
Posted: Tue Dec 13, 2005 5:57 am
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
What am I doing wrong?
Posted: Tue Mar 21, 2006 11:02 am
by devious
Accepted
Posted: Tue Mar 21, 2006 11:35 am
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
Posted: Fri Jul 14, 2006 11:38 am
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
Posted: Fri Jul 14, 2006 4:08 pm
by Darko
My AC program crashes on that input.
Posted: Fri Jul 21, 2006 8:28 am
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?
Posted: Fri Jul 21, 2006 5:26 pm
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)
10044 RE!! Help Me!!!
Posted: Sat Jul 22, 2006 3:59 pm
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);
}
Posted: Wed Feb 07, 2007 8:31 am
by devious
Edit: Got it accpeted
Posted: Sun May 27, 2007 3:54 pm
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;
Posted: Mon May 28, 2007 1:56 pm
by <:3)~~
is there any one who is free to reply?
Posted: Mon May 28, 2007 3:14 pm
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.