10044 - Erdos Numbers

[LittleJohn]

This problem is not so difficult, but the problem description about input format is not clear enough to me.
Could somebody give me some tricky input/output? My program failed to parse judge's input...

[LittleJohn]

What's the output of

Code: Select all

2
4 6
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.
Erdos, P.
Erdos,  P.
Reisig, W.
 
1 2
Smith, M.N. , Erdos, P.: Newtonian forms of prime factor matrices
Smith, M.N.
Smith, M.N.  

Thanks in advance.

[Per]

My AC program outputs:

Code: Select all

Scenario 1
Smith, M.N. 1
Hsueh, Z. infinity
Chen, X. 2
Erdos, P. 0
Erdos, P. 0
Reisig, W. 1
Scenario 2
Smith, M.N. infinity
Smith, M.N. infinity

The second case is clearly incorrect, so I don't think you have to worry about such input. My AC program parses names like this: first skip any leading whitespace, then consider the name to be everything up to the next ',' or ':'.

[LittleJohn]

Thank you, Per! But I still failed to parse the names.
There're some steps I followed (1st part of the input):
1. skip leading spaces
2. search for ',' (last name)
3. search for ',' or ':' (first name)
4. if not ':' repeat 1, 2, 3
5. read until '\n'
But I checked that I'll cross a new line('\n') in step 2, which is incorrect..
Can you help me?

[Per]

I read the entire line first using fgets, that way I don't have to worry about crossing a '\n'.

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 ':'.

I guess you could translate this to char-by-char reading by just replacing null by "'\n' or eof".

[LittleJohn]

It's Amazing! Finally I got AC. Thank you again for your great great help!

[titid_gede]

how is the upper limit for author name per test case? btw i use adjacent matrix and BFS for finding erdos number.. but keep getting WA

regards,
titid

[danielrocha]

I could really use some help with this problem, too. I'm using adjacent lists to find the Erdos Number, and ALL my ouput looks perfect, and yet I'm getting WA (got a lot of RE and TLE, but I'm past those)...

Could somebody send some trick input/output? I'm already very desperate, cause my program seems correct!!

---
Greets,
Daniel "Nazario" Rocha
Ci

[anupam]

how is the upper limit for author name per test case? btw i use adjacent matrix and BFS for finding erdos number.. but keep getting WA

regards,
titid

hello titid_gede,
the question is not new. I have created a thread before about the input & output limit of the problem.
I have tried it several times and being frustated deleted it and then after a rejudgement all of my submission got ac.
but i have not the src in my hand now.
I recode it but now it gets rte and mle.
so would any 1 got ac in the problem tell us abt the in & out limit??

[danielrocha]

I'm not sure if that is your problem, but I was getting Runtime Error because I was assuming that the first char of the author's name was always upper case. Apparently it can be upper, lower or can even be any other char...

I'm still looking for some input/outputs that my program can't handle...

-----
Greets,
Daniel "Naz

[czar]

Can anyone tell me what is wrong with my code?

[c]#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<iterator>
#include<algorithm>
#include<string>
#include<cstdio>

using namespace std;

string DEGREE0("Erdos, P.");
const int INITDEGREE = -1;

void split(string line, vector<string> &names) {

string::iterator upper = find(line.begin(), line.end(), ':');
string::iterator i = line.begin(), j = line.begin();
while(i < upper && j < upper) {

string name;
i = find(i, upper, ',');
++i;
i = find(i, upper, ',');

if(i == line.end())
copy(j, upper, back_inserter(name));
else
copy(j, i, back_inserter(name));

names.push_back(name);
j = i = i+2;
}
}

void process(string line, map<string, set<string> > &graph, map<string, int> &levels) {

vector<string> names;
vector<string>::iterator i, j;
split(line, names);

for(i = names.begin(); i < names.end(); i++) {
levels[*i] = INITDEGREE;

for(j = i-1; j >= names.begin(); j--)
if(j != i) {
graph[*i].insert(*j);
graph[*j].insert(*i);
}
}
}

void graphBFS(map<string, set<string> > &graph, map<string, int> &levels, string &deg0) {

map<string, int> visited;
queue<string> names;
string name;
int n = 0;
int count;

levels[deg0] = n;
names.push(deg0);
visited[deg0] = n;

while(!names.empty()) {
name = names.front();
names.pop();

set<string>::const_iterator si = graph[name].begin(), u = graph[name].end();
n = visited[name] + 1;
for(; si != u; ++si) {
if(visited.find(*si) == visited.end()) {
levels[*si] = n;
visited[*si] = n;
names.push(*si);

}
}
}
}

int main() {

int numCases;
cin>>numCases;
getchar();

for(int i = 0; i < numCases; i++) {
int numLines, numNames;
string line;
map<string, set<string> > graph;
map<string, int> levels;
string name;
vector<string> names;

cin>>numLines; getchar(); cin>>numNames; getchar();

for(int j = 0; j < numLines; j++) {
getline(cin, line);
process(line, graph, levels);
}

graphBFS(graph, levels, DEGREE0);

for(int j = 0; j < numNames; j++) {
getline(cin, name);
names.push_back(name);
}
int l;
cout<<"Scenerio "<<i+1<<"\n";
for(int j = 0; j < numNames; j++) {
cout<<names[j]<<" ";
if(levels.find(names[j]) == levels.end() || (l = levels[names[j]]) == -1)
cout<<"infinity\n";
else
cout<<l<<"\n";
}
}
return 0;
}[/c]

[anupam]

please dont create new threads when old thread exists.
chek the old thread, discuss there and delete this thread.
--
and also include problem name while creating new thread.
--
Anupam

[BiK]

When I get RTE usually this is because of segment violation. This time however the body of the RTE e-mail message said:

Your program has died with signal 6 (SIGABRT). Meaning:

Abort signal from abort()

Before crash, it ran during 4.111 seconds.

I tried to find any problem with the program but I couldn't. Could anyone tell me what causes the SIGABRT signal in general? I mean who called the abort() function.

My program tries to solve the 10044 (Erdoes Numbers) problem. It is making extensive use of STL. I've noticed in some messages on the board that [cpp]using namespace std[/cpp] is danerous. Could this be the reason? If not I would appreciate if somebody tells me the potential danger of using: [cpp]using namespace std[/cpp]

You could also notice that the program ran for more than 4 seconds. This is another problem I face with STL. I think that the library is implemented quite efficiently, but as a matter of fact I haven't had an ACCEPTED problem when using STL. And all problems I submitted got TLE answer. Could the reason for this also be the use of: [cpp]using namespace std[/cpp]

Thanks in advance.

[BiK]

This is the program that I wrote in order to solve the 10044 - Erdos Numbers problem. I'm sorry for posting a whole program, but since I use STL in my opinion the only possible errors could be TLE (if there is an infinite loop for example), WA (clear why) or MLE(if I don't use the containers sparingly). But from where could RTE error come. And even more misteriously the RTE is due to calling abort(). Please help me.

[cpp]#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <utility>

using namespace std;

int p, n;
map< string, set<string> > db;
map<string, int> m;

void vectorToSet(int k, vector<string> &v, set<string> &s) {
for(int i = 0; i < v.size(); i++)
if (i != k)
s.insert(v);
}

void updateDB(string &s) {
vector<string> v;
int prev = 0, next = 0;
while(true) {
prev = next;
while(s[next++] != ' ')
;
while(s[next] != ',' && s[next] != ':')
next++;
v.push_back(s.substr(prev, next-prev));
if (s[next] == ':')
break;
next += 2; //jump over comma and interval
} // outmost while
for(int i = 0; i < v.size(); i++)
for(int j = 0; j < v.size(); j++) {
map< string, set<string> >::iterator it = db.find(v);
if (it == db.end()) {
set<string> s;
vectorToSet(i, v, s);
db.insert( make_pair(v, s) );
}
else
vectorToSet(i, v, it->second);
}
}

void buildMap() {
m.clear();
string erdos("Erdos, P.");
m.insert( make_pair(erdos, 0) );
queue<string> q;
q.push(erdos);
while(!q.empty()) {
string f = q.front();
int num = (m.find(f))->second;
map<string, set<string> >::iterator dbit = db.find(f);
for(set<string>::iterator sit = dbit->second.begin(); sit != dbit->second.end(); ++sit) {
map<string, int>::iterator mit = m.find( *sit );
if (mit != m.end())
continue;
q.push( *sit );
m.insert( make_pair(*sit, num+1) );
} // for
q.pop();
} // while
}

int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
cin.rdbuf( (new ifstream("inp.txt"))->rdbuf() );
cout.rdbuf( (new ofstream("out.txt"))->rdbuf() );
#endif

int scenarios;
cin >> scenarios;
for(int i = 1; i <= scenarios; i++) {
db.clear();
cin >> p >> n;
string s;
getline(cin, s); // get newline
//read database
for(int j = 0; j < p; j++) {
getline(cin, s);
updateDB(s);
} // inner for
buildMap();
//output begins
cout << "Scenario " << i << endl;
for(int j = 0; j < n; j++) {
getline(cin, s);
cout << s << " ";
map<string, int>::iterator it = m.find(s);
if (it == m.end())
cout << "infinity" << endl;
else
cout << it->second << endl;
} // inner for
} // outer for

//system("PAUSE");
return 0;
}[/cpp]

[UFP2161]

abort() is used inside the STL when something really goes haywire