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

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

Re: 10044 - Erdos Numbers TL

Post by fresher96 » Tue Sep 16, 2014 8:40 pm

.
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

Post by fresher96 » Fri Sep 19, 2014 12:49 am

hey guys i spent a whole day solving this problem
and finally got it right and want to revenge :evil:
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

Post by lighted » Wed Dec 10, 2014 1:48 pm

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

Post by brianfry713 » Thu Dec 11, 2014 10:34 pm

http://www.udebug.com/UVa/10044
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!

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

Re: 10044 - Erdos Numbers

Post by lighted » Sat Dec 13, 2014 7:30 pm

Finally, got accepted. :)

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

- 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

Post by lighted » Sun Dec 14, 2014 8:00 am

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

Post by lighted » Sun Dec 14, 2014 8:30 am

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

Post by lighted » Sun Dec 14, 2014 8:48 am

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

Post by s0mbra » Tue Jan 13, 2015 3:17 am

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

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

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

Re: 10044 - Erdos Numbers

Post by brianfry713 » Tue Jan 13, 2015 11:02 pm

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

Post by s0mbra » Wed Jan 14, 2015 7:46 pm

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

Post by brianfry713 » Fri Jan 16, 2015 4:50 am

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.
Check input and AC output for thousands of problems on uDebug!

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

Re: 10044 - Erdos Numbers, WA. Please help...

Post by garbage » Fri Mar 06, 2015 7:17 pm

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

Post Reply

Return to “Volume 100 (10000-10099)”