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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Dec 22, 2003 2:02 pm

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

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

Post by anupam » Mon Dec 22, 2003 4:46 pm

Thanks Tahseen,
You have understood what i had neede. Thanks DM for your help.
"Everything should be made simple, but not always simpler"

Tahseen Mohammad
Learning poster
Posts: 54
Joined: Sun Oct 28, 2001 2:00 am
Location: Bangladesh

Post by Tahseen Mohammad » Tue Dec 23, 2003 9:48 am

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
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

Post by junbin » Mon Feb 02, 2004 11:40 am

Tahseen Mohammad wrote: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
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

10044

Post by technobug » Sat Feb 28, 2004 4:01 am

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
New poster
Posts: 18
Joined: Fri Oct 10, 2003 8:46 am
Location: Airway Heights

Time Exceeded too

Post by mooseelkdog » Sat Apr 10, 2004 8:54 am

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]

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Apr 10, 2004 10:11 am

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
New poster
Posts: 30
Joined: Wed Oct 23, 2002 6:53 am

Post by Amir Aavani » Sun Apr 11, 2004 9:13 pm

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
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa » Tue May 11, 2004 1:46 pm

Per wrote: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

User avatar
alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Thanks to PER

Post by alu_mathics » Fri May 21, 2004 12:05 am

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

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Re: Thanks to PER

Post by CDiMa » Fri May 21, 2004 9:55 am

alu_mathics wrote:Thanks PER.
My first solution gave me W.A.
After a long period of time (may be 6 months :o ) i just read your message (the input section) and finally got A.C. :D 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

User avatar
alu_mathics
Learning poster
Posts: 55
Joined: Sat Jan 24, 2004 9:30 pm
Location: Chittagong
Contact:

Post by alu_mathics » Sat May 22, 2004 10:14 am

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.
cuii e

mum_and_dady
New poster
Posts: 1
Joined: Tue Aug 03, 2004 12:03 pm

10044 (Erd

Post by mum_and_dady » Tue Aug 03, 2004 12:24 pm

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
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac » Thu Sep 09, 2004 4:02 pm

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
New poster
Posts: 24
Joined: Wed Mar 02, 2005 12:29 am

10044

Post by kenneth » Wed Mar 02, 2005 12:32 am

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;
}

Post Reply

Return to “Volume 100 (10000-10099)”