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

magister_ludi
New poster
Posts: 1
Joined: Wed Jul 28, 2010 8:16 am
Location: Germany

Re: 10044 - Erdos Numbers

Post by magister_ludi » Wed Jul 28, 2010 8:32 am

I followed all hints in this topic and my program still gets WA.
It would be great if someone could give me a hint what's wrong in my code.

Furthermore would testdata with a lot authors/papers be helpful.

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

public class Main
{
	static Map<String, Author> authorIdx;
    
	public static void main(String[] args) throws IOException {

		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintStream cout = System.out;
    	StringBuffer sbOut = new StringBuffer();

        String line = reader.readLine();
        StringTokenizer tokenizer = new StringTokenizer(line);
        int numScenarios = Integer.parseInt( tokenizer.nextToken());		
        
        for (int i = 0; i < numScenarios; i++)
        {
        	authorIdx = new HashMap<String, Author>();
        	
        	// Database Size and Name Size
            line = reader.readLine();
            while (line.trim().length() == 0)
            {
            	line = reader.readLine();
            }
            tokenizer = new StringTokenizer(line);
            int numPapers = Integer.parseInt( tokenizer.nextToken());		
            int numNames = Integer.parseInt( tokenizer.nextToken());		

            String[] papers = new String[numPapers];
            String[] names = new String[numNames];
            
            // read database
            for (int j = 0; j < numPapers; j++) 
            {
            	line = reader.readLine();
            	papers[j] = line;
            }
            
            // read names
            for (int j = 0; j < numNames; j++) 
            {
                line = reader.readLine();
                names[j] = line;
                names[j] = trim(line);
                createAuthor(names[j]);
            }
            
            // Solve it
            // 1. Build Author Graph
            for (String paper : papers)
            {
            	Collection<String> paperAuthors = splitPaper( paper);
            	for (String authorName : paperAuthors)
            	{
            		Author author = authorIdx.get( authorName);
        			if (author == null)
        			{
        				author = createAuthor(authorName);
        			} else 
        			{
        				for (String coAuthorName : paperAuthors)
        				{
        					if (!coAuthorName.equals( authorName))
        					{
        						Author coAuthor = authorIdx.get( coAuthorName);
        						if (coAuthor == null)
        						{
        	        				coAuthor = createAuthor( coAuthorName);
        						}	
       							author.addCoAuthor( coAuthor);
        					}	
                		}
                	}
            	}
            }
            
            // 2. Measure distance from Erdos
            Author erdosHimself = authorIdx.get( "Erdos, P.");
            if (erdosHimself == null)
            {
            	erdosHimself = createAuthor( "Erdos, P.");
            }
            erdosHimself.erdosNo = 0;
            
            List<Author> hasToBeProcessed = new ArrayList<Author>();
            hasToBeProcessed.add( erdosHimself);
            while(!hasToBeProcessed.isEmpty())
            {
            	Author author = hasToBeProcessed.remove( 0); 
        		author.processed = true;
        		for (Author a : author.getCoAuthors())
        		{
        			if ((author.erdosNo + 1) < a.erdosNo)
        			{	
        				a.erdosNo = author.erdosNo + 1;
        			}	
        			if (!a.processed && !hasToBeProcessed.contains( a))
        			{
        				hasToBeProcessed.add(a);
        			}
        		}
            }
            
            // Dump Result
            sbOut.append( "Scenario " + (i+1) + "\n");
            for (String name : names) 
            {
            	Author author = authorIdx.get( name);
            	if (author != null)
            	{
            		String erdNr;
            		if (author.erdosNo == Integer.MAX_VALUE)
            		{
            			erdNr = "infinity";
            		} else {
            			erdNr = String.valueOf( author.erdosNo);
            		}
            		sbOut.append(name + " " + erdNr + "\n");
            	}
            }
        }
        
        cout.print(sbOut.toString());
	}

	static Collection<String> splitPaper(String paper)
	{
		// 0: name vollständig gelesen, erwarte neuen namen
		// 1: Nachname gelesen, erwarte vorname
		
		paper = trim(paper);
		
		int colon = paper.indexOf( ':');
		if (colon > 0)
		{
			paper = paper.substring( 0, colon);
		}	
		
		int state = 0;
		int lastIndex = 0;
		
		Collection<String> names = new HashSet<String>();
		
		int nameStart = 0;
		while (true)
		{
			int comma = paper.indexOf( ',', lastIndex);
			if (comma != -1)
			{
				if (state == 0)
				{
					nameStart = lastIndex;
					state = 1;
				} else 
				{
					String name = paper.substring( nameStart, comma);
					name = name.trim();
					
					names.add( name);
					state = 0;
				}
				lastIndex = comma+1;
			} else {
				
				if (state == 1)
				{
					String name = paper.substring( nameStart);
					name = name.trim();
					names.add( name);
				}				
				break;
			}
		}		
		return names;
	}
	
	static Author createAuthor(String name)
	{
		Author a = new Author(name);
		authorIdx.put( name, a);
		return a;
	}
	
    static String trim(String s)
    {
		int from = 0;
		int to = s.length()-1;
		
		while (s.charAt( from) == ' ' || s.charAt( from) == '\t')
		{
			from++;
		}
		while (Character.isWhitespace( s.charAt( to)))
		{
			to--;
		}
    	
		StringBuffer sb = new StringBuffer();
		for (int i=from; i<=to; i++)
		{
			char c = s.charAt( i); 
			if (c == ' ')
			{
				sb.append( c);
				while(i<=to && s.charAt( i+1) == ' ')
				{
					i++;
				}
			} else
			{
				sb.append( c);
			}
		}
		return sb.toString();
    }
    	
	static class Author
	{
		String name;
		int erdosNo;
		boolean processed;
		Collection<Author> coAuthorOf;
		
		Author(String name)
		{
			this.erdosNo = Integer.MAX_VALUE;
			this.processed = false;
			this.name = name;
			coAuthorOf = new HashSet<Author>();
		}
		
		Collection<Author> getCoAuthors()
		{
			return coAuthorOf;
		}
		
		void addCoAuthor(Author a)
		{
			coAuthorOf.add( a);
		}

		@Override
		public String toString()
		{
			return name;
		}

		@Override
		public boolean equals(Object obj)
		{
			return name.equals( ((Author)obj).name);
		}

		@Override
		public int hashCode()
		{
			return name.hashCode();
		}		
	}	
}

davidbak
New poster
Posts: 3
Joined: Thu Mar 31, 2011 11:44 pm

Re: 10044 - Erdos Numbers

Post by davidbak » Sat Apr 02, 2011 1:48 am

For me the keys to this problem were revealed by this forum thread, thank you!

1) Maximum input line length was longer than I assumed.
2) I wasn't handling the case where names didn't have the "first name initials" part.

Thanks to you also, on this thread, for learning the trick on how to get the judge to return useful debugging information by forcing a TLE, too much output, etc. etc. I'm sure that'll come in handy in the future!

BTW, for those of you wrestling with problem size limits - needing to know problem sizes so you can allocate arrays and such in advance - one of the principal advances in programming languages in the past 20 years has been the widespread acceptance of languages that include data structures that can be sized at run time (to the limits of available memory), not compile time. We're not programming in Fortran or COBOL here: use the features of the language to make your life easier.

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 10044 - Erdos Numbers

Post by Imti » Sun May 08, 2011 12:05 pm

I got it accepted after lot of WA.The mistake I did was in input parsing.Really,input parsing of this problem is quite embarrassing.However,in this thread,some tricks U may get ,which works but unnecessary.Just strictly follow sample format given problem statement to parse the input.I'm giving some tricky cases here,Try to get it from there:
Input:

Code: Select all

5
1 2
Erdos, P. , ghj, P.:fh
ghj,P.
ghj, P.
1 2
Erdos, P., ghj, P.:fh
ghj,P.
ghj, P.
1 2
Erdos, P.,  ghj, P.:fh
ghj,P.
ghj, P.
1 2
Erdos, P.,  ghj,P.:fh
ghj,P.
ghj, P.

Output:

Code: Select all

Scenario 1
ghj,P. infinity
ghj, P. infinity
Scenario 2
ghj,P. infinity
ghj, P. 1
Scenario 3
ghj,P. infinity
ghj, P. 1
Scenario 4
ghj,P. 1
ghj, P. infinity

danieldonadon
New poster
Posts: 4
Joined: Thu Nov 24, 2011 3:29 am

Re: 10044 - Erdos Numbers

Post by danieldonadon » Thu Nov 24, 2011 4:05 am

The lack of information in this problem is quite annoying, taking you a long time trying to figure out what's the best approach without using dynamic structures, and if they are fast and not too much memory consuming.
Here is an "update" of what Maniac has already discovered about the input data size years ago, along with my own observations:
- maximal number of different persons in all papers together of one scenario is less than 5001
Checked, I use some 5,000 pre-allocated memory vectors and a 5,000 x 5,000 matrix with no ME.
- maximal length of input lines is less than 10001
Each line from the input data has actually less than 1024 characters.
- maximal length of person names is less than 101
Each person's full name (like "Erdos, P.") has less than 32 characters after removing extra spaces (it is, if there really are such spaces).
- maximal number of links from one person to others is less than 501
(I have not checked this.)

I hope this missing information may help other people as well.

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 10044 - Erdos Numbers

Post by plamplam » Thu Feb 23, 2012 6:23 pm

My accepted code produces different results on your input @Imti:

Code: Select all

Scenario  1
ghj,P. infinity
ghj, P. infinity
Scenario  2
ghj,P. infinity
ghj, P. 1
Scenario  3
ghj,P. infinity
ghj, P. 1
Scenario  4
ghj,P. 1
ghj, P. infinity
Scenario  5
ghj, P. infinity
ghj, P. infinity
You don't need to remove extra spaces, I just used the ',' character as separator. But input parsing is really annoying
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

three0s
New poster
Posts: 3
Joined: Sat Aug 04, 2012 9:52 am

Re: 10044 - Erdos Numbers

Post by three0s » Sat Aug 04, 2012 9:59 am

Well, I think the best way to read input is to find ".," and ".:" instead of "," and ":" .
I am also sure that there is no extra blank spaces in each line of input. (Mine got AC)

vpanait
New poster
Posts: 17
Joined: Sun Apr 01, 2012 11:01 am

Re: 10044 - Erdos Numbers

Post by vpanait » Sat Sep 08, 2012 12:54 pm

miserable problem statement, I got AC using a parse after {,} and {:}

it may happen that "erdos" is actually not in the list, so you cannot do BFS, or it may happen that a name from the author's list, is also not in the original nodes.
so if you use a hash to keep all names, just check if the "name" is in the hash or not.. before doing any computation..

AhmadKhatar
New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 10044 - Erdos Numbers

Post by AhmadKhatar » Wed Feb 20, 2013 9:58 pm

Hi!
Sorry! I got RE!
Here is my code:

Code: Select all

#include <iostream>
#include <map>
#include <cstring>
#include <string>
#include <queue>
#include <cctype>

using namespace std;

int p, n;
map<string,int> aut;
int mat [ 1000 ][ 1000 ];
int nameCnt;
int len [ 1000 ];
int color [ 1000 ];

void preprocess();
void process( string name );

int main()
{
	int tNo;
	char tLine [ 1000 ];
	string lineStr;
	string pStr [ 1000 ];
	int pCnt;

	cin >> tNo;
	for ( int i = 0; i < tNo; i++ )
	{
		nameCnt = 0;
		aut.clear();
		memset( mat, 0, sizeof(mat) );
		cin >> p >> n;
		cin.ignore();
		for ( int j = 0; j < p; j++ )
		{
			cin.getline( tLine, 1000, '\n' );
			lineStr = tLine;
			int comInd [ 1000 ];
			//
			int comCnt = 0;
			comInd[ comCnt++ ] = -2;
			for ( int k = 0; k < lineStr.length(); k++ )
			{
				if ( lineStr[ k ] == ',' || lineStr[ k ] == ':' )
				{
					comInd[ comCnt++ ] = k;
				}
			}
			
			pCnt = 0;
			for ( int k = 2; k < comCnt; k += 2 )
			{
				int stInd, endInd;
				stInd = comInd[ k - 2 ] + 2;
				endInd = comInd[ k ] - 1;
				pStr[ pCnt++ ] = lineStr.substr( stInd, endInd - stInd + 1 );
				if ( aut.find( lineStr.substr( stInd, endInd - stInd + 1 ) ) == aut.end() )
				{
					aut[ lineStr.substr( stInd, endInd - stInd + 1 ) ] = nameCnt++;
				}
			}
			//

			for ( int i = 0; i < pCnt; i++ )
			{
				for ( int j = i + 1; j < pCnt; j++ )
				{
					mat[ aut[ pStr[ i ] ] ][ aut[ pStr[ j ] ] ] = mat[ aut[ pStr[ j ] ] ][ aut[ pStr[ i ] ] ] = 1;
			   }
			}
		}
	
		preprocess();
		cout << "Scenario " << i + 1 << endl;
		for ( int k = 0; k < n; k++ )
		{
			cin.getline( tLine, 1000, '\n' );
			lineStr = tLine;
			process( lineStr );
		}
	}

	return 0;
}

void process( string name )
{
	cout << name << " ";
	if ( aut.find( name ) == aut.end() )
	{
		cout << "infinity" << endl;
	}
	else
	{
		if ( len[ aut[ name ] ] == -1 )
		{
			cout << "infinity" << endl;
		}
		else
		{
			cout << len[ aut[ name ] ] << endl;
		}
	}
}

void preprocess()
{
	for ( int i = 0; i < nameCnt; i++ )
	{
		len[ i ] = -1;
	}

	if ( aut.find("Erdos, P.") != aut.end() )
	{
		// bfs
		queue<int> q;
		memset( color, 0, sizeof(color) );

		q.push( aut[ "Erdos, P." ] );
		color[ aut[ "Erdos, P." ] ] = 1;
		len[ aut[ "Erdos, P." ] ] = 0;

		while ( !q.empty() )
		{
			int u = q.front();
			q.pop();

			for ( int i = 0; i < nameCnt; i++ )
			{
				if ( mat[ u ][ i ] == 1 && color[ i ] == 0 )
				{
					q.push( i );
					color[ i ] = 1;
					len[ i ] = len[ u ] + 1;
				}
			}
		}
	}
}
Please help and Thanks in advance! :D
Last edited by AhmadKhatar on Thu Feb 21, 2013 1:24 am, edited 11 times in total.

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 Feb 21, 2013 12:49 am

You can see the reason for your compile error by clicking My Submissions, however, your code is producing a Runtime Error.

Try the I/O in this thread.
Check input and AC output for thousands of problems on uDebug!

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 Feb 21, 2013 11:40 pm

Try the I/O in this thread. See what plamplam and Imti posted recently.
Check input and AC output for thousands of problems on uDebug!

AhmadKhatar
New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 10044 - Erdos Numbers

Post by AhmadKhatar » Fri Feb 22, 2013 12:06 am

Hi!
Thanks for your help!
But after removing leading spaces I still get RE!
:(

Yusif
New poster
Posts: 27
Joined: Tue Jun 25, 2013 2:24 am

Re: 10044 - Erdos Numbers

Post by Yusif » Tue Aug 06, 2013 9:12 am

I checked my code with the I/O by Imti, yet it is wa :(
help pls!

Code: Select all

#include <iostream>
#include <stdio.h>
#include <map>
#include <queue>
#include <vector>
#include <string>

using namespace std;

struct adj {
	vector < map<string, adj>::iterator > neip;
	int dis;
	
	adj() : dis(-1) {
		neip.reserve(40);
	}
	
};


int main(){
	int tc, p, n, cas=0;
	cin>>tc;
	while(++cas<=tc){
		cin>>p>>n;
		map<string, adj> m;
		
		
		for (int i=0; i<p; ++i){
			vector <map<string, adj>::iterator> tn; tn.reserve(80); string ts; ts.reserve (15);
			char c;
			while (true){
				while (!isalpha((c=getchar())));
				bool firstcom=false;
				do{
					if (c==',') firstcom=true;
					ts.push_back(c);
					c=getchar();
					
				} while (c!=':' && (!firstcom||c!=','));

				m[ts];
				tn.push_back(m.find(ts));
				ts.clear();
				if(c==':') break;
			}
			int neinum=tn.size();
			for (int i=0; i<neinum; ++i){
				for (int j=0; j<neinum; ++j){ if (i==j) continue;
					tn[j]->second.neip.push_back(tn[i]);
				}
			}
			while (getchar()!='\n');
		}
		
		vector<string> names(n); 
		for (int i=0; i<n; ++i){
			while (isspace(cin.peek())) getchar();
			getline(cin, names[i]);
		}
		
	
		int lev;
		queue <map<string, adj>::iterator> bfs;
		bfs.push(m.find("Erdos, P."));
		bfs.front()->second.dis=0; // his own Erdos num
		while (!bfs.empty()){
			map<string, adj>::iterator fro=bfs.front();
			lev=fro->second.dis+1;
			int neisize=fro->second.neip.size();
			for (int i=0; i<neisize; ++i){
				if (fro->second.neip[i]->second.dis==-1){
					fro->second.neip[i]->second.dis=lev;
					bfs.push(fro->second.neip[i]);
				}
			}
			bfs.pop();
		}
		
		printf("Scenario %d\n",cas);
		for (int i=0; i<n; ++i){
			cout<<names[i];
			map<string, adj>::iterator it=m.find(names[i]);
			if (it==m.end()|| it->second.dis==-1){
				printf(" infinity\n");
			}
			else{
				printf(" %d\n",it->second.dis);
			}
		}
	}
	
	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 » Fri Aug 16, 2013 1:23 am

Try the I/O in this thread by Ivan Goroun » Sun Jan 10, 2010 11:28 am
Check input and AC output for thousands of problems on uDebug!

Yusif
New poster
Posts: 27
Joined: Tue Jun 25, 2013 2:24 am

Re: 10044 - Erdos Numbers

Post by Yusif » Fri Aug 16, 2013 12:42 pm

I modified it according to that and even did a little more overkill, yet wa!
Maybe I better move on. :roll:

cyberdragon
New poster
Posts: 20
Joined: Fri Aug 30, 2013 5:42 am

10044 - Erdos Numbers

Post by cyberdragon » Thu Oct 17, 2013 6:27 am

Why TLE ?
Even I've used bool Vis array that works in O(1).
http://ideone.com/KsnVd0

Any Help ?

Post Reply

Return to “Volume 100 (10000-10099)”