10044 - Erdos Numbers

[fresher96]

.

[fresher96]

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]

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?

[brianfry713]

http://www.udebug.com/UVa/10044
AC output for your input:

Code: Select all

Scenario 1
ghj,P. 1
ghj, P. 1

[lighted]

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.

[lighted]

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.

[lighted]

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

[lighted]

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

[s0mbra]

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]

Always print a newline char at the end of the last line.

[s0mbra]

Always print a newline char at the end of the last line.

I was doing that but still getting WAs.

[brianfry713]

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.

[garbage]

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