Connection Status:
Competition Arena > ErdosNumber

ErdosNumber

Member Beta · 2009-08-11 · by Nickolas

Member Beta · 2009-08-11 · by Nickolas · Graph Theory, String Manipulation, String Parsing
Class Name: ErdosNumber
Return Type: String[]
Method Name: calculateNumbers
Arg Types: (vector<string>)
Problem Statement

Problem Statement

The Erdos number is a way of describing the "collaborative distance" between a scientist and Paul Erdos by authorship of scientific publications.
Paul Erdos is the only person who has an Erdos number equal to zero. To be assigned a finite Erdos number, a scientist must publish a paper in co-authorship with a scientist with a finite Erdos number. The Erdos number of a scientist is the lowest Erdos number of his coauthors + 1. The order of publications and numbers assignment doesn't matter, i.e., after each publication the list of assigned numbers is updated accordingly.
You will be given a String[] publications, each element of which describes the list of authors of a single publication and is formatted as "AUTHOR_1 AUTHOR_2 ... AUTHOR_N" (quotes for clarity only). Paul Erdos will be given as "ERDOS".
Return the list of Erdos numbers which will be assigned to the authors of the listed publications. Each element of your return should be formatted as "AUTHOR NUMBER" if AUTHOR can be assigned a finite Erdos number, and just "AUTHOR" otherwise. The authors in your return must be ordered lexicographically.

Notes

  • All authors mentioned in the list must be present in your return.
  • Assume that all publications of mentioned authors are given in publications.
  • String S is lexicographically before string T if S is a proper prefix of T, or if S has an earlier character at the first position where the strings differ.

Constraints

  • publications will contain between 1 and 50 elements, inclusive.
  • Each element of publications will contain between 1 and 50 characters, inclusive.
  • An author is a string of between 1 and 50 uppercase letters ('A'-'Z'), inclusive.
  • Each element of publications will be a list of authors, separated by single spaces.
  • Each element of publications will not have any trailing spaces.
  • The authors in each element of publication will be distinct.
  • There will be at most 100 distinct authors in all publications.
  • Paul Erdos will be given as "ERDOS", and at least one publication will list him as one of the authors.
Examples
0)
{"ERDOS"}
Returns: {"ERDOS 0" }

The only author is Erdos himself, with Erdos number equal to 0.

1)
{"KLEITMAN LANDER", "ERDOS KLEITMAN"}
Returns: {"ERDOS 0", "KLEITMAN 1", "LANDER 2" }

publications[1] defines Kleitman's number as 1, and publications[0] defines Lander's number as 2.

2)
{"ERDOS A", "A B", "B AA C"}
Returns: {"A 1", "AA 3", "B 2", "C 3", "ERDOS 0" }
3)
{"ERDOS B", "A B C", "B A E", "D F"}
Returns: {"A 2", "B 1", "C 2", "D", "E 2", "ERDOS 0", "F" }

E has coauthors B (Erdos number 1) and A (Erdos number 2), so his Erdos number is defined through the coauthor with the lowest Erdos number. D and F aren't connected to Erdos and thus have no numbers assigned.

4)
{"ERDOS KLEITMAN", "CHUNG GODDARD KLEITMAN WAYNE", "WAYNE GODDARD KLEITMAN", 
 "ALON KLEITMAN", "DEAN GODDARD WAYNE KLEITMAN STURTEVANT"}
Returns: {"ALON 2", "CHUNG 2", "DEAN 2", "ERDOS 0", "GODDARD 2", "KLEITMAN 1", "STURTEVANT 2", "WAYNE 2" }
5)
{"ERDOS Q W E R T Y U I O P A S D F G H J K L Z X","AA AB AC AD AE AF AG AH AI AJ AK AL AM AN AO AP AQ","AQ AS AT AU AV AW AX AY AZ BA BB BC BD BE BF BG BH","BH BJ BK BL BM BN BO BP BQ BR BS BT BU BV BW BX BY","BY BZ CB CC CD CE CF CG CH CI CJ CK CL CM CN CO CP","CA CP CQ CR CS CT CU CV CW CX CY CZ QQ Q WW"}
Returns: {"A 1", "AA 6", "AB 6", "AC 6", "AD 6", "AE 6", "AF 6", "AG 6", "AH 6", "AI 6", "AJ 6", "AK 6", "AL 6", "AM 6", "AN 6", "AO 6", "AP 6", "AQ 5", "AS 5", "AT 5", "AU 5", "AV 5", "AW 5", "AX 5", "AY 5", "AZ 5", "BA 5", "BB 5", "BC 5", "BD 5", "BE 5", "BF 5", "BG 5", "BH 4", "BJ 4", "BK 4", "BL 4", "BM 4", "BN 4", "BO 4", "BP 4", "BQ 4", "BR 4", "BS 4", "BT 4", "BU 4", "BV 4", "BW 4", "BX 4", "BY 3", "BZ 3", "CA 2", "CB 3", "CC 3", "CD 3", "CE 3", "CF 3", "CG 3", "CH 3", "CI 3", "CJ 3", "CK 3", "CL 3", "CM 3", "CN 3", "CO 3", "CP 2", "CQ 2", "CR 2", "CS 2", "CT 2", "CU 2", "CV 2", "CW 2", "CX 2", "CY 2", "CZ 2", "D 1", "E 1", "ERDOS 0", "F 1", "G 1", "H 1", "I 1", "J 1", "K 1", "L 1", "O 1", "P 1", "Q 1", "QQ 2", "R 1", "S 1", "T 1", "U 1", "W 1", "WW 2", "X 1", "Y 1", "Z 1" }

100 authors

6)
{"ERDOS ARRARRARRARRARRARRARRARRARRARRARRARRARRARRAR","ARRARRARRARRARRARRARRARRARRARRARRARRARRARRAR JOHN","ERRERRERRERRERRERRERRERRERRERRERRERRERRERRERRERROR"}
Returns: {"ARRARRARRARRARRARRARRARRARRARRARRARRARRARRAR 1", "ERDOS 0", "ERRERRERRERRERRERRERRERRERRERRERRERRERRERRERRERROR", "JOHN 2" }

Fun with long author names.

7)
{"ERDOS Q","Q W","W E","E R","R T","T Y","Y U","U I","I O","O P","P A","A S","S D","D F","F G","G H","H J","J K","K L","L Z","Z X","X C","C V","V B","B N","N M","M QW","QW QE","QE QR","QR QT","QT QY","QY QU","QU QI","QI QO","QO QP","QP QA","QA QS","QS QD","QD QF","QF QG","QG QH","QH QJ","QJ QK","QK QL","QL QZ","QZ QX","QX QC","QC QV","QV QB","QB QN"}
Returns: {"A 11", "B 24", "C 22", "D 13", "E 3", "ERDOS 0", "F 14", "G 15", "H 16", "I 8", "J 17", "K 18", "L 19", "M 26", "N 25", "O 9", "P 10", "Q 1", "QA 36", "QB 49", "QC 47", "QD 38", "QE 28", "QF 39", "QG 40", "QH 41", "QI 33", "QJ 42", "QK 43", "QL 44", "QN 50", "QO 34", "QP 35", "QR 29", "QS 37", "QT 30", "QU 32", "QV 48", "QW 27", "QX 46", "QY 31", "QZ 45", "R 4", "S 12", "T 5", "U 7", "V 23", "W 2", "X 21", "Y 6", "Z 20" }

Max Erdos number (50)

47)
{"ERDOS ASD NBVMJ SERU", "ASDYYTU VBNGJK ASFSD ERDOS UIPF", "QWEY ERDOS FVNJY"}
Returns: {"ASD 1", "ASDYYTU 1", "ASFSD 1", "ERDOS 0", "FVNJY 1", "NBVMJ 1", "QWEY 1", "SERU 1", "UIPF 1", "VBNGJK 1" }

Erdos present in all publications

48)
{"ERDOS ERTY YUIN","YUIN ERTY ERDOS"}
Returns: {"ERDOS 0", "ERTY 1", "YUIN 1" }

Identical authors lists

49)
{"DIACONIS ERDOS",
 "BOCK DIACONIS HUFFER PERLMAN",
 "BERGER BOCK BROWN CASELLA GLESER",
 "LEVINE CASELLA",
 "LEVINE YU HANELY NITAO",
 "GLASSLEY NITAO GRANT JOHNSON STEEFEL KERCHER",
 "ANDERSON ERDOS PINKUS SHISHA",
 "ROSEN SHISHA",
 "BANCHOFF ROSEN",
 "MAX BANCHOFF",
 "MAX CRAWFIS GRANT",
 "BOROSH CHUI ERDOS",
 "CHUI SCHUMAKER",
 "NEAMTU POTTMANN SCHUMAKER",
 "BERTRAM BARNES HAMANN JOY POTTMANN WUSHOUR",
 "JOY GRANT MAX HATFIELD"}
Returns: {"ANDERSON 1", "BANCHOFF 3", "BARNES 4", "BERGER 3", "BERTRAM 4", "BOCK 2", "BOROSH 1", "BROWN 3", "CASELLA 3", "CHUI 1", "CRAWFIS 5", "DIACONIS 1", "ERDOS 0", "GLASSLEY 6", "GLESER 3", "GRANT 5", "HAMANN 4", "HANELY 5", "HATFIELD 5", "HUFFER 2", "JOHNSON 6", "JOY 4", "KERCHER 6", "LEVINE 4", "MAX 4", "NEAMTU 3", "NITAO 5", "PERLMAN 2", "PINKUS 1", "POTTMANN 3", "ROSEN 2", "SCHUMAKER 2", "SHISHA 1", "STEEFEL 6", "WUSHOUR 4", "YU 5" }

I have three strings of publications (that I know about) that go back to Erdos with lengths 6, 5 and 5.

Submissions are judged against all 88 archived test cases, of which 11 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class ErdosNumber with a public method vector<string> calculateNumbers(vector<string> publications) · 88 test cases · 2 s / 256 MB per case

Submitting as anonymous