## 10044 - Erdos Numbers

Moderator: Board moderators

fresher96
New poster
Posts: 25
Joined: Wed Sep 03, 2014 8:50 am

### Re: 10044 - Erdos Numbers TL

.
Last edited by fresher96 on Fri Sep 19, 2014 12:51 am, edited 1 time in total.

fresher96
New poster
Posts: 25
Joined: Wed Sep 03, 2014 8:50 am

### Re: 10044 - Erdos Numbers

hey guys i spent a whole day solving this problem
and finally got it right and want to revenge
it's not really that hard but it's kind of a mystery
for you who gave up here's my incompetence approach if you wish for
it's very simple by the way
hope to be useful

Code: Select all

``````#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <map>
using namespace std;

//
map <string , int> val;
#define infinty 999999
#define max_names_per_line 101
//

// returns the minimum "erdos number" in a paper
int minimum(string **names , int i)
{
int min = val[names[i][0]];
for(int j = 1; j<max_names_per_line && names[i][j] != ""; j++)
{
min = (min > val[names[i][j]])? val[names[i][j]] : min;
}
return min;
}
// if you want to view the names with their "erdos numbers"
void view(string **names , int p)
{
cout<<"..........................................................\n";
for(int i = 0; i<p; i++)
{
for(int j=0;j<max_names_per_line && names[i][j] != ""; j++)
{
cout<<names[i][j]<<":"<<val[names[i][j]]<<"   ";
}
cout<<endl;
}
cout<<"..........................................................\n";
}
// checks if we are done meaning that there is no more operations to do
// and every name is with his correct "erdos number"
bool finished(string **names, int p)
{
for(int i = 0; i<p; i++)
{
int x = minimum(names,i);
for(int j = 0; j<max_names_per_line && names[i][j] != ""; j++)
{
if(val[names[i][j]] != x && val[names[i][j]] != x+1)
return 0;
}
}
return 1;
}
//

int main()
{
int T;
string line;
int Scenario = 1;
cin>>T;

while(T--)
{
int p,n;
cin>>p>>n;
string **names = new string *[p];

// reding the papers and implinting the names in 2D array
for(int i = 0; i<p; i++)
{
bool b = 0;
names[i] = new string [max_names_per_line];
int na = 0;
char ch;

while(cin >> ch && ch != ':')
{
if(ch == ',')
{
if(b == 0)
{
b = 1;
names[i][na] += ", ";
}
else
{
val[names[i][na]] = infinty;
na++;
b = 0;
}
}
else
names[i][na]+=ch;
}

val[names[i][na]] = infinty;
getline(cin,line);
}

val[""] = infinty;
val["Erdos, P."] = 0;

// scanning the array and giving erdos number to each name in O(n^2) i think, but didn't pass the time limit
/*
int pp = p;
while(pp--)
{
for(int i = 0; i<p; i++)
{
int min = minimum(names , i);
for(int k=0;k<max_names_per_line && names[i][k] != "";k++)
{
if(val[names[i][k]] > min)
val[names[i][k]] = min+1;
}
}
}
*/

// scanning the array and giving erdos number to each name in O(n) i think, and passed within 2.185
while(1)
{
for(int i = 0; i<p; i++)
{
int min = minimum(names , i);
for(int k=0;k<max_names_per_line && names[i][k] != "";k++)
{
if(val[names[i][k]] > min)
val[names[i][k]] = min+1;
}
}
if(finished(names,p))
break;
}

// printing the results
cout<<"Scenario "<<Scenario++<<endl;
for(int i = 0; i<n; i++)
{
getline(cin,line);
cout<<line<<' ';
if(val[line] == infinty)
cout<<"infinity";
// expecting the judge to view the "erdos number" for a name that isn't mentioned in the papers
// and the judge does
else if(val[line] == 0 && line != "Erdos, P.")
cout<<"infinity";
else
cout<<val[line];
cout<<endl;
}
}
return 0;
}
``````

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10044 - Erdos Numbers

Input

Code: Select all

``````1
1 2
Erdos, P. , ghj, P.:fh
ghj,P.
ghj, P.
``````
Output (Imti and plamplam)

Code: Select all

``````Scenario 1
ghj,P. infinity
ghj, P. infinity``````
Why output for second author is not 1?
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10044 - Erdos Numbers

http://www.udebug.com/UVa/10044

Code: Select all

``````Scenario 1
ghj,P. 1
ghj, P. 1
``````
Check input and AC output for thousands of problems on uDebug!

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10044 - Erdos Numbers

Finally, got accepted.

Problem description is not clear. Some posts in this thread contains invalid inputs.

- maximal number of papers is <= 32000
- maximal number of different persons in papers of one scenario is <= 4100
- maximal number of persons in one paper is <= 15
- maximal number of persons asked for calculating Erdos numbers in one scenario is <= 2100
- maximal length of paper is <= 210
- maximal length of person name without spaces is <= 20

Fresher, you could use BFS. I accepted in 0.279.
Last edited by lighted on Sun Dec 14, 2014 8:09 am, edited 1 time in total.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10044 - Erdos Numbers

Input parsing of this problem becomes annoying because of lack of input format's details.

I considered format of paper as follows: Author names in paper are separated by commas followed by one or more spaces, where symbol _ means one or more spaces.

Name1,_Name2,_Name3,_...Namek: Papername

I read paper by char skipping all spaces in paper. So i can't say if spaces exist inside author names (except one space after first comma), in any case i skip them.

Author names asked for calculating Erdos numbers as follows: Each name is on one line without leading or trailing spaces. So getline works ok. Also there won't be author's name "Erdos, P." among this names.

Author's names both in paper and in queries for Erdos numbers contains one space after first comma. Name = Firstname,spaceInitial

Both Firstname and Initial part will always be present.
Last edited by lighted on Fri Sep 25, 2015 4:10 pm, edited 1 time in total.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10044 - Erdos Numbers

I modified incorrect inputs in this thread.

Input (LittleJohn)

Code: Select all

``````2
4 4
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.
Reisig, W.

1 2
Smith, M.N. , Erdos, P.: Newtonian forms of prime factor matrices
Smith, M.N.
Smith, M.N.``````
Acc Output

Code: Select all

``````Scenario 1
Smith, M.N. 1
Hsueh, Z. infinity
Chen, X. 2
Reisig, W. 1
Scenario 2
Smith, M.N. 1
Smith, M.N. 1
``````
Input (Alexis Blaze)

Code: Select all

``````1
3 5
Smith, T.H., Martin, G., Erdos, P.: Newtonian forms of prime factors
a, e., b, f., c, g., d, h., Smith, T.H.: Something
Smith, T.H., Chen, X.: First order derivates in structured programming
Smith, T.H.
a, e.
a, f.
Chen, X.
Chen, X
``````
Acc Output

Code: Select all

``````Scenario 1
Smith, T.H. 1
a, e. 2
a, f. infinity
Chen, X. 2
Chen, X infinity
``````
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 10044 - Erdos Numbers

Input (Ion2Atom)

Code: Select all

``````1
12 15
Erdos, P., C, C: asdf
Erdos, P., B, B: asdf
Erdos, P., A, A: asdfa
B, B, G, G: asdf
A, A, H, H: asdf
H, H, I, I: asdf
I, I, J, J, K, K: asdf
J, J, L, L: asdf
L, L, F, F: asdf
F, F, D, D, E, E: asdf
M, M, N, N, O, O: asdf
A, A
B, B
C, C
D, D
E, E
F, F
G, G
H, H
I, I
J, J
K, K
L, L
M, M
N, N
O, O``````
Acc Output

Code: Select all

``````Scenario 1
A, A 1
B, B 1
C, C 1
D, D 3
E, E 3
F, F 2
G, G 2
H, H 2
I, I 3
J, J 4
K, K 4
L, L 3
M, M infinity
N, N infinity
O, O infinity
``````
Input (Ivan Goroun)

Code: Select all

`````` 2
4    3
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.
12 18
Erdos, P., C, C., FUFAIL, F: asdf
Erdos, P., B, B.: asdf
Erdos, P., A, A.: asdfa
B, B., G, G.: asdf
A, A., H, H.: asdf
H, H., I, I.: asdf
I, I., J, J., K, K.: asdf
J, J., L, L.: asdf
L, L., F, F.: asdf
F, F., D, D., E, E.: asdf
M, M., N, N., O, O.: asdf
A, A.
B, B.
C, C.
D, D.
E, E.
F, F.
G, G.
H, H.
I, I.
J, J.
K, K.
L, L.
M, M.
N, N.
O, O.
WTF, F.
WTF., F
WTF, U.``````
Acc Output

Code: Select all

``````Scenario 1
Smith, M.N. 1
Hsueh, Z. infinity
Chen, X. 2
Scenario 2
A, A. 1
B, B. 1
C, C. 1
D, D. 3
E, E. 3
F, F. 2
G, G. 2
H, H. 2
I, I. 3
J, J. 4
K, K. 4
L, L. 3
M, M. infinity
N, N. infinity
O, O. infinity
WTF, F. infinity
WTF., F infinity
WTF, U. infinity
``````
Input (Imti)

Code: Select all

``````4
1 1
Erdos, P. , ghj, P.:fh
ghj, P.
1 1
Erdos, P., ghj, P.:fh
ghj, P.
1 1
Erdos, P.,  ghj, P.:fh
ghj, P.
1 1
Erdos, P.,  ghj,P.:fh
ghj, P.``````
Acc Output

Code: Select all

``````Scenario 1
ghj, P. 1
Scenario 2
ghj, P. 1
Scenario 3
ghj, P. 1
Scenario 4
ghj, P. 1
``````
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

s0mbra
New poster
Posts: 4
Joined: Thu Dec 11, 2014 9:30 pm

### Re: 10044 - Erdos Numbers

Can someone help me with this problem? I'm pretty sure that the problem is in the parsing. I've already spent a thousand hours searching for errors, testing every critical input here (and getting identical answers) but the judge still gives me WA.

In the parsing I skip every extra space to get the name in the form A,_B. (where _ means space) and also I ignore the last author when it doesn't have a surname...

Code: Select all

``````//___A,___B -> A,_B

#include <algorithm>
#include <iostream>
#include <numeric>
#include <sstream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>

using namespace std;

typedef map<string, int> index;
typedef map<int, set<int>> graph;

const int infinity = 1000000;

string transformInValid(string name){
string newName = "";

for (int l = 0; l < name.length(); l++){
if (name[l] != ' '){
newName += name[l];

if (name[l] == ',')
newName += ' ';
}
}

//cout << "\$\$" << name << ">>>" << newName << "<<<\n";
return newName;
}

void newAuthors(index &ind, graph &g, string paper, int &newId){

bool isStage3 = false;
string name;
vector<int> newAuthors;

//Possiveis formas do nome do autor:

for (char s : paper){
if (s == ' ') continue;

if (s == ':'){
if (isStage3){
auto p = ind.insert(make_pair(name, newId));
g.insert(make_pair(newId, set<int>()));

//if the author already exists, there is no need to create a new id
if (p.second)
newId++;

newAuthors.push_back(p.first->second);
}
}
else{
if (s == ','){
if (isStage3){
auto p = ind.insert(make_pair(name, newId));
g.insert(make_pair(newId, set<int>()));

//if the author already exists, there is no need to create a new id
if (p.second)
newId++;

newAuthors.push_back(p.first->second);

isStage3 = false;
name.clear();
}
else{
isStage3 = true;
name += ", ";
}
}
else
name += s;
}
}

for (int author : newAuthors){
for (int coAuthor = 0; coAuthor < newAuthors.size(); coAuthor++){
if (newAuthors[coAuthor] == author) continue;

g[author].insert(newAuthors[coAuthor]);
//cout << "Inserting ID " << newAuthors[coAuthor] << "in " << author << endl;
}
}

}

int main(){
int cases, p, n;

cin >> cases;
cin.ignore();

for (int scenario = 0; scenario < cases; scenario++){
int id = 1;         //erdos has the id = 0
bool first = true;
bool entrou = false;

string paper;
index table;
graph g;

//Erdos is the first element in the graph
g.insert(make_pair(0, set<int>()));
table.insert(make_pair("Erdos, P.", 0));

cin >> p >> n;
cin.ignore();

for (int i=0; i<p; i++){
getline(cin, paper);
newAuthors(table, g, paper, id);
}

/*
cout << "Current graph:\n";
for (auto itGraph = g.begin(); itGraph != g.end(); itGraph++){
cout << itGraph->first << ":\n";
for (auto itSet = itGraph->second.begin(); itSet != itGraph->second.end(); itSet++)
cout << *itSet << " ";
cout << endl;
}*/

vector<int> distances(table.size());
iota(distances.begin(), distances.end(), infinity);
distances[0] = 0;

for (int i=0; i<g.size(); i++){
for (int otherAuthor : g[i]){
if (distances[otherAuthor] > distances[i] + 1)
distances[otherAuthor] = distances[i] + 1;
}
}

//read the authors whom the erdos number must be found
cout << "Scenario " << scenario+1 << endl;
for (int i = 0; i < n; i++){
getline(cin, paper);

string name = transformInValid(paper);

string searchName = name;
//searchName.erase(remove(searchName.begin(),searchName.end(),' '),searchName.end());

if (!first)
cout << endl;
else
first = false;

auto result = table.find(searchName);
if (result == table.end())
cout << name << " infinity";
else{
int erdosNumber = distances[result->second];
if (erdosNumber < infinity)
cout << name << " " << erdosNumber;
else
cout << name << " infinity";
}

entrou = true;
}

if (entrou && scenario < cases-1)
cout << endl;
}

return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10044 - Erdos Numbers

Always print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

s0mbra
New poster
Posts: 4
Joined: Thu Dec 11, 2014 9:30 pm

### Re: 10044 - Erdos Numbers

Always print a newline char at the end of the last line.
I was doing that but still getting WAs.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10044 - Erdos Numbers

My AC parsing strategy:
Read number of test cases, P and N as tokens, read until the newline char after N.

Skip any leading spaces, Read until the first ',' or end of line, then read until the second ',' or ':' or end of line.
If there is not a second ',' then break the loop.

Don't use cin.ignore() and count on it to be a newline char. On some problems there may be trailing whitespace.
Check input and AC output for thousands of problems on uDebug!

garbage
New poster
Posts: 19
Joined: Thu Feb 21, 2013 5:46 am

Code: Select all

``````#include<iostream>
#include<cstdio>
#include<map>
#include<string>
#include<vector>
#include<queue>
#define sz 10005
#define inf 999999
using namespace std;

int main()
{
string str, S;
bool flag, vs[sz];
long f, id, ind, ln, P, N, T, erdos[sz];

scanf("%d", &T);

for(long i=1;i<=T;i++)
{
scanf("%d %d", &P, &N);
getchar();

id = 1;
map<string, long>myMap;
vector<long>v, myVec[sz];

for(long j=1;j<=P;j++)
{
getline(cin, str);

S = "";
ln = str.length();
for(int k=0, cnt=0;k<ln;k++)
{
if(str[k] == ',')
cnt++;

if(cnt == 2 || str[k]==':')
{
while(S[0] == ',' || S[0]==' '){
S.erase(0, 1);
}

if(myMap[S] == 0)
myMap[S] = id++;

v.push_back(myMap[S]);

//cout<<S<<endl;

S="";
cnt=0;

if(str[k] == ':')
break;
}
if(str[k] != ' ')
S.push_back(str[k]);
}

ln = v.size();

for(long k=0;k<ln;k++)
{
for(long l=0;l<ln;l++)
{
if(k != l)
myVec[v[k]].push_back(v[l]);
}
}

v.clear();
}

/*for(long j=1;j<=id;j++)
{
cout<<j<<"--->";
for(long k=0;k<myVec[j].size();k++)
cout<<myVec[j][k]<<" ";
cout<<endl;
}*/

for(long j=1;j<=id;j++)
{
erdos[j] = inf;
vs[j] = false;
}

queue<long>Q;

Q.push(myMap["Erdos,P."]);
erdos[myMap["Erdos,P."]] = 0;
vs[myMap["Erdos,P."]] = true;

while(!Q.empty())
{
f = Q.front();

ln = myVec[f].size();
for(long j=0;j<ln;j++)
{
ind = myVec[f][j];
if(!vs[ind])
{
Q.push(ind);
erdos[ind] = erdos[f] + 1;
vs[ind] = true;
}
}
Q.pop();
}

/*for(long j=1;j<=id;j++)
cout<<erdos[j]<< " ";
cout<<endl;*/

cout<<"Scenario "<<i<<endl;
for(long j=1;j<=N;j++)
{
getline(cin, str);

cout<<str<<" ";

S = "";
ln = str.length();
for(int k=0;k<ln;k++)
{
if(str[k] != ' ')
S.push_back(str[k]);
}

//cout<<S<<endl;

if(erdos[myMap[S]] == inf)
cout<<"infinity"<<endl;

else
cout<<erdos[myMap[S]]<<endl;
}
}
return 0;
}
``````