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

Post Reply
LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

10044 - Erdos Numbers

Post by LittleJohn » Sun May 11, 2003 6:20 am

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

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Tue Jul 22, 2003 5:30 pm

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Tue Jul 22, 2003 7:44 pm

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
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Wed Jul 23, 2003 2:44 am

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Wed Jul 23, 2003 2:14 pm

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
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post by LittleJohn » Wed Jul 23, 2003 3:24 pm

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

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

10044 - erdos

Post by titid_gede » Sat Sep 06, 2003 8:11 am

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
Kalo mau kaya, buat apa sekolah?

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Need some help (input/output)

Post by danielrocha » Sat Sep 06, 2003 7:07 pm

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!! :cry:

---
Greets,
Daniel "Nazario" Rocha
Ci

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Re: 10044 - erdos

Post by anupam » Sun Sep 07, 2003 7:19 am

titid_gede wrote: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??
"Everything should be made simple, but not always simpler"

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Re: 10044 - erdos

Post by danielrocha » Sun Sep 07, 2003 1:33 pm

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

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

-----
Greets,
Daniel "Naz

czar
New poster
Posts: 15
Joined: Tue Jun 10, 2003 7:30 pm

10044

Post by czar » Sun Sep 07, 2003 9:29 pm

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
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Mon Sep 08, 2003 7:43 am

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
"Everything should be made simple, but not always simpler"

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

Strange RTE

Post by BiK » Mon Oct 06, 2003 3:23 am

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
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm

Post by BiK » Tue Oct 07, 2003 2:58 am

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]

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Tue Oct 07, 2003 4:31 am

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

Post Reply

Return to “Volume 100 (10000-10099)”