10044 - Erdos Numbers
Moderator: Board moderators
Re: 10044 - Erdos Numbers TL
.
Last edited by fresher96 on Fri Sep 19, 2014 12:51 am, edited 1 time in total.
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
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;
}
Re: 10044 - Erdos Numbers
Input
Output (Imti and plamplam)
Why output for second author is not 1?
Code: Select all
1
1 2
Erdos, P. , ghj, P.:fh
ghj,P.
ghj, P.
Code: Select all
Scenario 1
ghj,P. infinity
ghj, P. infinity
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman
-
- 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
AC output for your input:
AC output for your input:
Code: Select all
Scenario 1
ghj,P. 1
ghj, P. 1
Check input and AC output for thousands of problems on uDebug!
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.
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
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.
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
Re: 10044 - Erdos Numbers
I modified incorrect inputs in this thread.
Input (LittleJohn)Acc Output
Input (Alexis Blaze)
Acc Output
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.
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
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
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
Re: 10044 - Erdos Numbers
Input (Ion2Atom)
Acc Output
Input (Ivan Goroun)
Acc Output
Input (Imti)
Acc Output
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
C, C, F, F: aadsf
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
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
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
C, C., F, F.: aadsf
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.
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
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.
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
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...
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;
}
}
//update the adjacent list
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;
}
-
- 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!
Re: 10044 - Erdos Numbers
I was doing that but still getting WAs.Always print a newline char at the end of the last line.
-
- 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.
Read P lines - loop to read each name:
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.
Read N lines.
Don't use cin.ignore() and count on it to be a newline char. On some problems there may be trailing whitespace.
Read number of test cases, P and N as tokens, read until the newline char after N.
Read P lines - loop to read each name:
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.
Read N lines.
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!
Re: 10044 - Erdos Numbers, WA. Please help...
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;
}