Statistics

Problem Statement for "Criminal"

Problem Statement

You are working for the FBI and are trying to locate a particular criminal organization. Within the organization you know which members communicate with each other. The problem is that the members may go by aliases. Given both the information in the database about the organization, and the field data about a suspicious organization, you will determine whether they represent the same group. The two sets of data represent the same group if and only if they only differ by the names of the participants. 
For example:
Database               Field Data 
FRANK ----- BOB        WILLARD ----- GEORGE
  |                       |
  |                       |
  |                       |
GEORGE                  GREG
The Database and Field Data represent the same organization even though the participants are using different names.
Renaming Scheme:
FRANK -> WILLARD           FRANK -> WILLARD         
BOB -> GEORGE       or     BOB -> GREG 
GEORGE -> GREG             GEORGE -> GEORGE
If the database data and the field data represent the same organization return how many of the members are going by aliases, otherwise return -1. If there is more than one naming scheme possible in mapping the database information to the field data, use the one that gives the greatest value for the number of aliases. So in the previous example we would use the first renaming scheme thus giving 3 instead of 2.

The database data will be given in a String[] database. Each element of database will be in the form "NAME1 NAME2" meaning that NAME1 and NAME2 communicate with each other. The field data will be given in a String[] fieldData that is formatted in the same way as database. In the above example, the input could have been formatted as:
database = {"FRANK BOB","FRANK GEORGE"}
fieldData = {"WILLARD GREG","GEORGE WILLARD"}
In any particular organization, no two people will have the same name or alias. In other words, no two different people in the database will have the same name in database. In addition, no two different people in the field data will have the same name in fieldData.

Definition

Class:
Criminal
Method:
numPseudonyms
Parameters:
String[], String[]
Returns:
int
Method signature:
int numPseudonyms(String[] database, String[] fieldData)
(be sure your method is public)

Notes

  • Communication is symmetric. In other words, if FRANK and BOB communicate then BOB and FRANK communicate.

Constraints

  • database will contain between 1 and 28 elements inclusive
  • fieldData will contain between 1 and 28 elements inclusive
  • Each element of database will contain between 3 and 50 characters inclusive
  • Each element of fieldData will contain between 3 and 50 characters inclusive
  • Each element of database and fieldData will be of the form NAME1_NAME2 where '_' is a single space and NAME1 is different than NAME2NAME1 and NAME2 will have at least 1 character, and will only contain uppercase letters ('A'-'Z')
  • Each element of database and fieldData will have NO leading or trailing whitespace
  • There will be between 2 and 8 unique names inclusive in database
  • There will be between 2 and 8 unique names inclusive in fieldData
  • database cannot contains any repeated elements. In other words, if database contains an element "A B", it cannot contain another element "A B" or "B A".
  • fieldData cannot contain any repeated elements. In other words, if fieldData contains an element "A B", it cannot contain another element "A B" or "B A".

Examples

  1. {"FRANK BOB","FRANK GEORGE"}

    {"WILLARD GREG","GEORGE WILLARD"}

    Returns: 3

    The example from above.

  2. {"ADAM FRANK","BOB SUZY"}

    {"BRETT GEORGE","BRETT TOM"}

    Returns: -1

    These can't both be describing the same organization. The fieldData contains 3 distinct people where as the database contains 4.

  3. {"HARRY LLOYD","GEORGE BILL"}

    {"FRANK THOMAS","GEORGE WILL","WILL FRANK"}

    Returns: -1

    These can't both be describing the same organization. The number of pairs of communicating members differs.

  4. {"TIM BOB","BOB SUE","SUE AAA","BBB CCC","CCC DDD","DDD BBB"}

    {"A B","B C","C D","AAA BBB","BBB CCC","CCC AAA"}

    Returns: 7

  5. {"A B","B C","C A","AA BB","BB CC","CC AA"}

    {"A B","B C","C A","AA BB","BB CC","CC AA"}

    Returns: 6

  6. {"A B","B C","C A","AA BB","BB CC","CC DD","DD AA"}

    {"A B","B C","C A","AA BB","BB CC","CC DD","DD AA"}

    Returns: 7

  7. {"A B","A C","A D","AA BB","AA CC","AA DD"}

    {"A B","A C","A D","AA BB","AA CC","AA DD"}

    Returns: 8

  8. {"A B","A C","AA BB","AA CC","AA DD"}

    {"A B","A C","AA BB","AA CC","AA DD"}

    Returns: 5

  9. {"A B","A C","B D","B E"}

    {"A B","A C","B D","B E"}

    Returns: 2

  10. {"A B", "B C", "C D", "D E", "E F", "F G", "G H"}

    {"A B", "B C", "C D", "D E", "E F", "F G", "G H"}

    Returns: 8

  11. {"C E","A B","G D","C A","C D","G E","A G","F E","G H"}

    {"B H","A E","D C","H A","E C","D A","F E","F A","D G"}

    Returns: -1

  12. {"H G","E F","D A","C G","B A","A G","E G"}

    {"A F","B F","C F","C E","C H","G H","C D"}

    Returns: 8

  13. {"E B","A F","B A","G F","A D"}

    {"B E","C A","B C","G B","G D"}

    Returns: 6

  14. {"G E","C A","H E","H G","G C"}

    {"G B","D B","D C","C A","D A"}

    Returns: 5

  15. {"E G","D B","H F","E F","B E"}

    {"A G","E H","C G","C E","D C"}

    Returns: 6

  16. {"A C","F A","C E","C B","G B"}

    {"A C","H B","C F","A G","A B"}

    Returns: 6

  17. {"H A","B E","B F","A D","A G","F E"}

    {"A H","B H","H D","F G","C A","G B"}

    Returns: -1

  18. {"G F","F D","A G","E F","G B","D B","E H"}

    {"H D","G H","E A","E B","E D","A C","D G"}

    Returns: -1

  19. {"G E","C B","D H","H A","B A","B D","G A","H C","C E","A C","G H","F H","B G","E D","B E","E F","F C","D G","D F"}

    {"D A","G E","H F","D H","H E","B F","F G","B A","C B","E F","A G","F C","C E","F A","C G","B E","F D","A E","D E"}

    Returns: -1

  20. {"D A","B E","C H","F C","C E","B G","A F","F E","B C","G A","D F","C A"}

    {"E F","F C","H C","G A","G E","F B","E C","B E","G H","H B","A D","C A"}

    Returns: -1

  21. {"E G","G H","G F","H D","D A","B G","D C","F C","E H"}

    {"C F","D E","D C","A D","G F","H E","H C","A B","A E"}

    Returns: -1

  22. {"G H","A G","C A","G C","E F","G F","D H","F B"}

    {"D H","B C","F A","E C","F D","F B","G A","H F"}

    Returns: -1

  23. {"D B","A F","D F","G E","G H","G A","B A"}

    {"F H","C D","A G","H A","D F","H D","C B"}

    Returns: -1

  24. {"G B","E B","H D","C F","E H","F A","C D"}

    {"B A","B E","A C","G A","D H","F C","A D"}

    Returns: -1

  25. {"A D","B D","G C","H B","D E","B C","F D","F B","G F","D G","E H","E G","E C"}

    {"H D","G C","D C","D B","C H","A H","H F","E F","E H","C B","C A","G A","E C"}

    Returns: -1

  26. {"D B","D H","C A","G E","G D","H B","B F"}

    {"H A","H G","B D","F A","G F","G C","E H"}

    Returns: -1

  27. {"B H","C H","A C","B G","E C","A F","H G","A H","G E","B C"}

    {"E D","F E","B D","B A","H E","B C","F B","C E","B H","H F"}

    Returns: -1

  28. {"G D","D C","H A","A G","G H","B F","H C","C E","D A","E G","G B","F G","F C","D E","B D"}

    {"B G","H E","F H","D G","B E","C D","F D","G A","D B","F A","D A","F C","E A","H D","E C"}

    Returns: -1

  29. {"B H","A H","A C","C E","B C","A E","H F","E D","H D","C F","A F","H C","B E","A D","G C","F G"}

    {"D B","B E","F H","F G","C H","H B","F B","G D","A C","A H","A F","H G","E F","A E","G B","G C"}

    Returns: -1

  30. {"E D","E C","G D","A C","H D","C H","H F","G B","D F","C D","D A","H E","B A","E B"}

    {"H G","G D","A D","A G","D E","C H","A F","F D","B E","E A","G F","A B","H A","G B"}

    Returns: -1

  31. {"A H","C F","B H","H C","D C","A C","C G","C E","D G","B F","F G","A G","E G","B E","D H"}

    {"C B","C F","B D","F D","F E","F G","G D","E G","D H","A B","E B","B G","F B","E A","H C"}

    Returns: -1

  32. {"B F","D H","C A","C E","E D","B E","C G","A B","B G","D C","B C","G E","A F","D A","H E","B D","H A","F C"}

    {"G H","H E","F H","G D","D C","B D","F G","B C","D A","G B","A E","B H","G A","B F","C H","D H","D E","F E"}

    Returns: -1

  33. {"A B"}

    {"A B"}

    Returns: 2

  34. {"A B","A C","A D","A E","A F","A G","A H", "B C","B D","B E","B F","B G","B H", "C D","C E","C F","C G","C H", "D E","D F","D G","D H", "E F","E G","E H", "F G","F H", "G H" }

    {"A B","A C","A D","A E","A F","A G","A H", "B C","B D","B E","B F","B G","B H", "C D","C E","C F","C G","C H", "D E","D F","D G","D H", "E F","E G","E H", "F G","F H", "G H" }

    Returns: 8

  35. {"A B","A D","A F","A G","A H","C B","C H","D C","D F","E B","E F","E G","G D","H B","H F"}

    {"C A","C B","D A","D C","E B","E D","F E","G A","G B","G C","G E","G F","H A","H B","H F"}

    Returns: 8

  36. {"STEVE BRETT", "STEVE LARS", "STEVE JAMES"}

    {"SCHVEIGUY ADMINBRETT", "ADMINBRETT LBACKSTROM", "LBACKSTROM STEVEVAI"}

    Returns: -1

  37. {"A B","B C","C A","A D","B D","C D","E F","F G","G E","E D", "F D","G D"}

    {"A B","B C","C D","D E","E F","F A","A G","B G","C G", "D G","E G","F G"}

    Returns: -1

  38. {"A D","A E","A F","B D","B E","B F","C D","C E","C F"}

    {"A D","A E","A F","B D","B E","B F","C D","C E","C B"}

    Returns: -1

  39. {"A B","B C","C D","C E"}

    {"A B","B C","C D","C E"}

    Returns: 2

  40. {"A B","B C","C D","C E","D E","E F"}

    {"A B","B C","C D","C E","D E","E F"}

    Returns: 0

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: