10044 - Erdos Numbers

[Dominik Michniewski]

I think (but I don't know real input size) that best practice is to use vectors or dynamic structures ... It help us to save memory and time

Best regards
DM

[anupam]

Thanks Tahseen,
You have understood what i had neede. Thanks DM for your help.

[Tahseen Mohammad]

Anupam I wonder what you assumed to be the maximum length
of an author name. I used STL "string" class so I don't have a
clue what the size could be.

I agree with DM using of C++ features is a very good idea. It saves
time, solves a lot of problem. But I don't like the idea that a problem
forcing us to use STL. I mean this information should be clearly given
in problem specification (max author number, max name length).

And about the queue_size, my comment was not very wise.
Its a BFS, so if max author = 5000 that should also be the queue
size.

DM or any one else, I need some help regarding STL.
I often use map nowadays. It may be a very good implementation
of Red-Black tree but I feel sometimes it would be better if I could
use something like a hash-map. I know SGIs STL has a hash map
which is non-standard. Is there any simple way I can implement
a hash-map using standard STL.

As you can guess pretty easily by now, I'm not comfortable with the
idea of hashing.

[junbin]

It seems there is a lot of guessing going on about the input format.
Whether there is extra spaces before, after and within author names.


There is nothing like that. Input is precisely like that of sample.

So painful parsing is not necessary.

I agree.. I spent only 20 minutes coding the first program (the one that does not allow for extra/less spaces and/or commas) and then another 5 hours tweaking the parsing routine until it got accepted.

This is seriously ridiculous.. since I do not make use of STL (and I don't know how *grin*) I have to use arrays and "basic" data structures to handle my data. However, due to the large amount of data required to store in this program (around 5000 people and a lot of books), I was forced to allocated a huge chunk of memory and then do my own memory manager. As a result, an initially 1k+ code became over 4k+ in length.

ACM ICPC is about algorithm and efficiency and it disturbs me to see that many questions are "hard" not because they have difficult algorithm, but simply because we have to code "stupid AI" just to read the data input.

[technobug]

Hey there,

I was going through the exercices when I got to this one. Seem very simple to be implemented: just create the graph and look for the minimum line connecting two points... if they are not connected, leave it....

I did not want to use arrays (I wanna train my stl skills hehehe) so my code is using a base Pessoa (person) class to represent a person...

Unfortunately I get a Timeout.... on the method findPessoa.... in the for where it looks for a person.... I cant see the reason why it would hang.... anyone?

Thanks

Guilherme Silveira


[cpp]#include <iostream>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <string>
#include <map>

using namespace std;

class Pessoa {

public:

vector<Pessoa *> links;

string nome;
bool ehEle;
int level;

void link(Pessoa *p) {
// se ja contem, ignora
if(p!=this && find(links.begin(),links.end(),p)==links.end()) {
links.push_back(p);
}
}

};

void tokenize(const string& str,
vector<string>& tokens,
const string& delimiters = ",")
{
// Skip delimiters at beginning.
string::size_type lastPos = str.find_first_not_of(delimiters, 0);
// Find first "non-delimiter".
string::size_type pos = str.find_first_of(delimiters, lastPos);

while (string::npos != pos || string::npos != lastPos)
{
// Found a token, add it to the vector.
tokens.push_back(str.substr(lastPos, pos - lastPos));
// Skip delimiters. Note the "not_of"
lastPos = str.find_first_not_of(delimiters, pos);
// Find next "non-delimiter"
pos = str.find_first_of(delimiters, lastPos);
}

}

vector<Pessoa *> pessoas;

Pessoa *findPessoa(string nome) {

// tries to find this person
int total = pessoas.size();
for(int i=0;i!=total;i++) {
if(pessoas->nome==nome) {
return pessoas;
}
}

Pessoa *pes = new Pessoa;
pes->nome = nome;
pes->ehEle = (nome=="Erdos, P.");
pessoas.push_back(pes);
return pes;

}

int main(char **argv,int argc) {

int casos;
cin >> casos;

for(int caso=1;caso<=casos;caso++) {

int m,n;
scanf("%d %d\n",&m,&n);
pessoas.clear();
cout << "Scenario " << caso << endl;

string line;

for(int zi=0;zi!=m;zi++) {
getline(cin,line);
string autores = line.substr(0,line.find(':'));
vector<string> tokens;
tokenize(autores,tokens,", ");

// vai adicionando todos os usuarios
for(int i=0;i<tokens.size();i+=2) {
Pessoa *p = findPessoa(tokens + ", " + tokens[i+1]);
for(int i2=0;i2<tokens.size();i2+=2) {
p->link(findPessoa(tokens[i2] + ", " + tokens[i2+1]));
}
}

}

for(int zi=0;zi!=n;) {
getline(cin,line);


// pega o usuario
vector<Pessoa *> fila;
vector<Pessoa *> passado;
Pessoa *p = findPessoa(line);
p->level = 0;
passado.push_back(p);
fila.push_back(p);
while(fila.size()!=0) {
p = fila[0];
fila.erase(fila.begin());
if(p->ehEle) {
cout << line << " " << p->level << endl;
goto proximo;
}
// adiciona os filhos se possivel
if(p->links.size()!=0) {
for(int z=0;z!=p->links.size();z++) {
if(find(passado.begin(),passado.end(),p->links[z])==passado.end()) {
p->links[z]->level=p->level+1;
passado.push_back(p->links[z]);
fila.push_back(p->links[z]);
}
}
}
}
// nao achou
cout << line << " infinity" << endl;
proximo:
zi++;
}

}

return 0;

}
[/cpp]

[mooseelkdog]

I can't see how I might optimize this, can anyone help?

Thanks

[cpp]
#include <iostream>
#include <iterator>
#include <cstring>
#include <list>

using namespace std;

const char * FIRST = "P.", * LAST = "Erdos";

typedef struct
{
char *Name, *Init;
int Num;

} Erdi;

list < list <Erdi> > values;
list < Erdi > fList;

int P, N, C = 0;
char **papers, **names;

char * StrDup (const char *);
void findNums();
ostream &operator<< (ostream &out, const Erdi &C);

char * StrDup (const char * In)
{
//string allocation and copying
char * Copy = NULL;

Copy = new char [1 + strlen(In)];
assert (Copy != NULL);
strcpy (Copy, In);

return Copy;

} //end StrDup() function

void findNums()
{
char *str, *name, *ini, *temp;
Erdi addend, addend1;
list <Erdi> tmplist;

cout << "Scenario " << ++C << endl;

for(int x = 0; x < P; x++)
{
temp = papers[x];
str = strtok(temp, ":");
name = strtok(str, ", ");
while(ini = strtok(NULL, ", "))
{
addend.Name = StrDup(name);
addend.Init = StrDup(ini);
addend.Num = -1;
tmplist.push_back(addend);
name = strtok(NULL, ", ");

} // end while

values.push_back(tmplist);
tmplist.clear();

} // end for

for(int x = 0; x < values.size(); x++)
{
tmplist = values.front();
for(int y = 0; y < tmplist.size(); y++)
{
addend = tmplist.front();
if(strcmp(addend.Name, LAST) == 0 &&
strcmp(addend.Init, FIRST) == 0)
{
tmplist.pop_front();
int count = tmplist.size();
for(int z = 0; z < count; z++)
{
tmplist.front().Num = 1;
fList.push_back(tmplist.front());
tmplist.pop_front();

} // end for

tmplist.clear();

} // end if
tmplist.pop_front();
tmplist.push_back(addend);

} // end for
values.pop_front();
if(!tmplist.empty())
values.push_back(tmplist);

} // end for

tmplist.clear();

for(int x = 0; x < values.size() && !values.empty(); x++)
{
tmplist = values.front();

int count = tmplist.size();
for(int y = 0; y < count; y++)
{
for(int z = 0; z < fList.size(); z++)
{
addend = fList.front();
if(strcmp(tmplist.front().Name, addend.Name) == 0
&& strcmp(tmplist.front().Init, addend.Init) == 0)
{
tmplist.pop_front();
while(!tmplist.empty())
{
tmplist.front().Num = addend.Num + 1;
fList.push_back(tmplist.front());
tmplist.pop_front();

} // end while

values.pop_front();
tmplist = values.front();
z = fList.size();

} // end if
else
{
fList.pop_front();
fList.push_back(addend);

} // end else

} // end for

addend1 = tmplist.front();
tmplist.pop_front();
tmplist.push_back(addend1);

} // end for
values.pop_front();
if(!tmplist.empty())
values.push_back(tmplist);

} // end for

if(!values.empty())
{
while(!values.empty())
{
list<Erdi> temp = values.front();
while(!temp.empty())
{
fList.push_back(temp.front());
temp.pop_front();

} // end while
values.pop_front();

} // end while

} // end if

for(int x = 0; x < N; x++)
{
temp = names[x];
name = strtok(temp, ", ");
ini = strtok(NULL, ", ");
for(int y = 0; y < fList.size(); y++)
{
Erdi temp = fList.front();
if(strcmp(temp.Name, name) == 0
&& strcmp(temp.Init, ini) == 0)
{
cout << temp;
y = fList.size();

} // end if

fList.pop_front();
fList.push_back(temp);

} // end for

} // end for

} // end findNums()

ostream &operator<< (ostream &out, const Erdi &C)
{
out << C.Name << ", "
<< C.Init << " ";
(C.Num > 0) ? out << C.Num << endl : out << "infinity\n";

return out;

} // end ostream &operator<<() overload

int main()
{
int sce;
char temp[255];

cin >> sce;

while(sce-- > 0)
{
cin >> P >> N;
cin.get();
papers = new char *[P];
names = new char *[N];
for(int x = 0; x < P; x++)
{
cin.getline(temp, 255);
papers[x] = StrDup(temp);

} // end for

for(int x = 0; x < N; x++)
{
cin.getline(temp, 255);
names[x] = StrDup(temp);

} // end for

findNums();

for(int x = 0; x < P; x++)
delete [] papers[x];
for(int x = 0; x < N; x++)
delete [] names[x];

delete [] papers;
delete [] names;

papers = names = NULL;

} // end while

return 0;

} // end main()
[/cpp]

[shamim]

Both of your codes are far too long.

Well one think I can tell you there would be approximately 5000 athors. so keep this in mind.

I have not checked your algo, but if you are running O(n2) algorithm, you will get TLE.

[Amir Aavani]

Dear Shamim
As I know there is n't any polynominal time alg for graph vertex coloring,
and this problem could be converted to a vertex coloring problem!!
I cant understand what do you mean by an alg les than O (n2).

[CDiMa]

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".

What does "whitespace" mean for you? isspace() from <ctype.h> ?
and what does it mean "add until null"? That if the line ends you continue reading next line for the name?

Ciao!!!

Claudio

[alu_mathics]

Thanks PER.
My first solution gave me W.A.
After a long period of time (may be 6 months ) i just read your message (the input section) and finally got A.C. without using STL.
To CDiMa i consider whitespace as ' ' , '\t' && '\r'.
hope this will help you.

[CDiMa]

Thanks PER.
My first solution gave me W.A.
After a long period of time (may be 6 months ) i just read your message (the input section) and finally got A.C. without using STL.
To CDiMa i consider whitespace as ' ' , '\t' && '\r'.
hope this will help you.

I had it already ACepted but with a version where I copy strings around a lot. This is too slow for my liking. I have a faster one that always gives WA and I don't understand why.

Thanks for pointing out what you consider whitespace!

Ciao!!!

Claudio

[alu_mathics]

I have a faster one that always gives WA and I don't understand why.

You can send me that part.i will try to figure out.

[mum_and_dady]

I had a lot of problems to get AC, so I wrote a little test program to see, if judge input is correct.
I found some paper description with an even (non-zero) number of ',' before the first ':'.
In the final version of my solution I ignored the last name (because it did not contain a first name) in the wrong line(s) and got AC.

Here is my program:
[java]
import java.util.*;
import java.lang.*;
import java.io.*;

class Main{

// Raise time limit exception.
static void tle()
{
while (true)
{
int i = 0;
i++;
i--;
}
}

// Raise memory limit exceeded.
static void mle()
{
int n[] = new int[100000000];
n[2345] = 743;
}

// Raise output limit exception.
static void ole()
{
while (true)
{
System.out.println("blablabla");
}
}

// Read single character from stdin.
static char read() throws IOException
{
return (char)System.in.read();
}

// Read whole line terminated by '\n' from stdin.
static String readLine() throws IOException
{
StringBuffer sb = new StringBuffer("");
char c = read();
while (c != '\n')
{
sb.append(c);
c = read();
}
return sb.toString();
}

public static void main(String[] args)
{
StringTokenizer st;
String s;
try {
// Read number of cases.
st = new StringTokenizer(readLine());

// Assert that there is exactly one number in the first line.
if (st.countTokens() != 1)
{
tle();
}
int cases = (new Integer(st.nextToken())).intValue();

// There has to be a non-negativ number of cases.
if (cases <= 0)
{
tle();
}

for (int count = 1; count <= cases; count++)
{
// Read p and n.
st = new StringTokenizer(readLine());

// There have to be exactly to numbers.
if (st.countTokens() != 2)
{
tle();
}
int p = (new Integer(st.nextToken())).intValue();
int n = (new Integer(st.nextToken())).intValue();

// p and n have to be non-negativ.
if (p < 0 || n < 0)
{
tle();
}
for (int i = 0; i < p; i++)
{
// Read the next paper description.
s = readLine();

int j = s.indexOf(':');
// Test, if there is a number differnt from 1 of ':'.
if (s.indexOf(':', j+1) != -1)
{
tle();
}

// Cut the non-relevant part of the description.
s = s.substring(0, j);

// Test, if there is not any ','.
j = s.indexOf(',');
if (j == -1)
tle();

// Count number of ',' in anzKom.
int anzKom = 0;
while (j != -1)
{
j = s.indexOf(',', j+1);
anzKom++;
}

// Raise ole() if the number of ',' is even.
if (anzKom % 2 != 1)
ole();
}
for (int i = 0; i < n; i++)
{
// Read next author name.
s = readLine();

// There has to be exactly one ','.
int j = s.indexOf(',');
if (s.indexOf(',', j+1) != -1)
{
tle();
}
}
}
// There must not be input left.
char c = read();
if (c != 65535)
{
tle();
}
} catch (IOException e)
{
tle();
}
}
}
[/java]

[Maniac]

after finally getting this problem AC, here's some information that could be useful:

- maximal number of different persons in all papers together of one scenario is less than 5001
- maximal length of input lines is less than 10001
- maximal length of person names is less than 101
- maximal number of links from one person to others is less than 501

The Judge input is correct except that there are person names with no initials! These persons always appear at the end of the list of authors and can be ignored. For example:

Code: Select all

Smith, M.N., Chen, X., Johnson: Introduction to Algorithms

Ignore Johnson in this case.

Code: Select all

Smith, M.N., Chen, X., Johnson, I.R.: Introduction to Algorithms

Don't ignore Johnson, I.R. !

Good luck! Erik

[kenneth]

Hi

The following is my code for this question. However, I keep getting the following message in my email reply:

Your program has died with signal 11 (SIGSEGV).

Would anyone be able to suggest why is that the case?

Thanks

#include <iostream>
#include <string>
#include <vector>
#include <pair.h>
#include <map>
#include <stdio.h>
using namespace std;

void erdos()
{
int p, n;
string line; // To store the rest of the line. Ie the tile of the book.
bool end = false; // Determine whether we have reached the end of the line.
string lastname, initials, fullname;
map <string, int> authorsList; // The mapping of the authors with their node number in the graph.
int count = 1; // The node number of the next node to be inserted into the graph.

cin >> p >> n;

vector <string> authorsForPaper[p]; // Stores the authors for each paper to generate the graph later on.
string authors[n]; // The list of authors need to be printed.

// Make Erodos node number 0 all the time.
authorsList["Erdos, P."] = 0;

// Extra information for each paper.
for (int i = 0; i < p; i++)
{
do
{
// Reset end.
end = false;

cin >> lastname >> initials;

// No more authors for the paper.
if (initials.at(initials.length() - 1) == ':')
{
getline(cin, line);
end = true;
}

// Get rid of comma or colin at the end of the names.
initials = initials.substr(0, initials.length() - 1);

fullname = lastname + " " + initials;

// If author does not exists in the list, add it to the list and increment the node number by 1.
if (authorsList.find(fullname) == authorsList.end())
{
authorsList[fullname] = count;
count++;
}

authorsForPaper.push_back(fullname);
} while (!end);
}

int size = authorsList.size();

// Get the names of the authors to be printed.
for (int i = 0; i < n; i++)
{
cin >> lastname >> initials;
fullname = lastname + " " + initials;
authors = fullname;
}

int graph[size][size + 1]; // The graph for determining Erdos number. Two nodes are connected
// if the authors have a joint paper. Note that last column is used
// to store the Erdos number.

// Reset the graph.
for (int i = 0; i < size; i++)
for (int j = 0; j < size - 1; j++)
graph[j] = -1;

for (int i = 0; i < size; i++)
graph[size - 1] = 0;

// Erdos number for Erdos is 0.
graph[0][size] = 0;

// Set the Erdos number for the rest to be -1 (infinity) to start off with.
for (int i = 1; i < size; i++)
graph[size] = -1;

// Connect the nodes for authors within each paper.
for (int i = 0; i < p; i++)
{
for (int j = 0; j < authorsForPaper.size() - 1; j++)
{
for (int k = j + 1; k < authorsForPaper.size(); k++)
{
int a = authorsList[authorsForPaper[j]];
int b = authorsList[authorsForPaper[k]];

graph[a][graph[a][size - 1]] = b;
graph[a][size - 1]++;
graph[graph[size - 1]] = a;
graph[size - 1]++;
}
}
}

int number = 0; // The current Erdos number we are working with.
bool flag = true; // True if there is more nodes to be visited.

while (flag)
{
// Reset the flag.
flag = false;

for (int i = 0; i < size; i++)
{
// For every node has the same Erdos number we are working with, try to go to unvisited
// adjacent nodes and set Erdoes number for those nodes to be 1 more than the current Erdos number.
if (graph[size] == number)
{
for (int j = 0; j < graph[i][size - 1]; j++)
{
// graph[j][size] == -1 indicates the node has not been visited before.
if (graph[i][j] > -1 && graph[graph[i][j]][size] == -1)
{
graph[graph[i][j]][size] = number + 1;
flag = true;
}
}
}
}

number++;
}

// Print out Erdos number for the authors.
for (int i = 0; i < n; i++)
{
cout << authors[i] << " ";

if (authorsList.find(authors[i]) == authorsList.end())
printf("infinity\n");
else if (graph[authorsList[authors[i]]][size] == -1)
printf("infinity\n");
else
printf("%d\n", graph[authorsList[authors[i]]][size]);
}

authorsList.clear();

for (int i = 0; i < p; i++)
authorsForPaper[i].clear();
}

int main()
{
int cases;

cin >> cases;

for (int i = 1; i <= cases; i++)
{
printf("Scenario %d\n", i);
erdos();
}

return 0;
}