Statistics

Problem Statement for "LunchScheduler"

Problem Statement

This afternoon, several TopCoder members independently ate lunch at the prestigious TopCoder cafe. They each arrived and left at different times, and nobody returned to the cafe after having left once. Throughout the day, TopCoder waiters noticed that certain members saw each other in the cafe and shook hands. This information was collected in the form of a String[] M, where M[i][j] is '1' if member i and member j were seen to shake hands. Otherwise, M[i][j] is '0'. Clearly, if M[i][j] is '1', then members i and j must have been at the cafe at overlapping times. On the other hand, certain TopCoder members do not know each other, so they might not have shaken hands even if they were at the cafe at overlapping times. Given this information, TopCoder is interested in estimating the largest number of people who were in the cafe at one time.

Create a class LunchScheduler that contains a method getOverlap, which is given a String[] M, as described above. It should return an int, specifying the largest integer k such that at least k members must have been in the cafe together at one time.


Suppose, for example, 
   M = {"0110", 
        "1010", 
        "1100", 
        "0000"}.
Then, two possible lunch schedules are shown below. 
   Member | Time period          Member | Time period
   -------+-----------------     -------+-----------------
      1   | ***************         1   |   *******
      2   |  ***************        2   |       *******
      3   |    ***********          3   |      ***
      4   |   ******                4   |            *****

Here, the *'s indicate the time periods during which each member was in the cafe. As can easily be checked, both schedules are consistent with M. The leftmost schedule has four members in the cafe at one time, but this is not necessary, as can be seen from the fact that the rightmost schedule never has more than three people together at once. It turns out that any other valid schedule will also have at least three members in the cafe at one time, so the correct value for k is 3 in this case.

Definition

Class:
LunchScheduler
Method:
getOverlap
Parameters:
String[]
Returns:
int
Method signature:
int getOverlap(String[] M)
(be sure your method is public)

Constraints

  • M will contain between 2 and 9 elements inclusive.
  • If M contains exactly n elements, then each element of M will contain will contain exactly n characters.
  • Every character in M is either '0' or '1'.
  • Character i in element j of M will be equal to character j in element i of M for all i and j.
  • Character i in element i of M will be '0' for all i.

Examples

  1. {"0110", "1010", "1100", "0000"}

    Returns: 3

    This is the example from the problem statement.

  2. {"011111", "101111", "110111", "111011", "111101", "111110"}

    Returns: 6

    Here, every member shook every other member's hand. Consider the earliest time period in which a member left the cafe. Nobody can leave before that, by definition, and nobody can arrive after that, or they would not have been able to shake the leaving member's hand. Thus, all six members must have been at the cafe during that time period.

  3. {"01000000", "10000000", "00000000", "00000000", "00000000", "00000000", "00000001", "00000010"}

    Returns: 2

    At least two people must be in the cafe simultaneously when the first two members shake hands. As shown below, it is also not necessary for three people to be in the cafe simultaneously. Member | Time period -------+---------------- 1 | ** 2 | ** 3 | * 4 | * 5 | * 6 | * 7 | ** 8 | **

  4. {"011011010", "101000111", "110010110", "000001101", "101001000", "100110101", "011101010", "111000100", "010101000"}

    Returns: 5

  5. {"00001000","00000011","00011000","00100110","10100000","00010001","01010000","01000100"}

    Returns: 3

  6. {"000001","000000","000010","000000","001000","100000"}

    Returns: 2

  7. {"0001001","0010000","0100001","1000100","0001000","0000000","1010000"}

    Returns: 2

  8. {"0000010","0000010","0000010","0000000","0000000","1110000","0000000"}

    Returns: 2

  9. {"001010","000100","100001","010000","100001","001010"}

    Returns: 3

  10. {"000000010","000000011","000101000","001010000","000100000","001000000","000000000","110000000","010000000"}

    Returns: 2

  11. {"000110001","001111011","010010000","110001111","111000101","010100100","000111000","010100001","110110010"}

    Returns: 5

  12. {"0010000","0000011","1000110","0000111","0011000","0111000","0101000"}

    Returns: 3

  13. {"000011111","001101100","010000111","010011010","100101110","110110110","111011001","101111000","101000100"}

    Returns: 6

  14. {"01110101","10011111","10011110","11101110","01110111","11111011","01111101","11001110"}

    Returns: 6

  15. {"001011","001000","110111","001001","101001","101110"}

    Returns: 4

  16. {"00101111","00010110","10000011","01001010","10010001","11000010","11110101","10101010"}

    Returns: 4

  17. {"0111000","1001000","1000110","1100100","0011010","0010100","0000000"}

    Returns: 3

  18. {"01110100","10100011","11010101","10100111","00000110","10111000","01011000","01110000"}

    Returns: 5

  19. {"0110101","1000000","1000000","0000001","1000011","0000101","1001110"}

    Returns: 3

  20. {"0001011","0001010","0000000","1100100","0001001","1100000","1000100"}

    Returns: 3

  21. {"001100","000010","100101","101011","010101","001110"}

    Returns: 3

  22. {"00000001","00101001","01010000","00101000","01010011","00000000","00001000","11001000"}

    Returns: 3

  23. {"0000000","0000100","0000001","0000000","0100000","0000000","0010000"}

    Returns: 2

  24. {"010100","100110","000100","111010","010101","000010"}

    Returns: 3

  25. {"01000110","10011110","00011111","01101000","01110101","11101001","11100001","00101110"}

    Returns: 5

  26. {"011110","101010","110011","100011","111101","001110"}

    Returns: 4

  27. {"00010100","00000111","00011100","10101010","00110000","11100000","01010000","01000000"}

    Returns: 3

  28. {"000000001","001000100","010010001","000000001","001001000","000010100","010001000","000000000","101100000"}

    Returns: 3

  29. {"010111","101000","010111","101000","101001","101010"}

    Returns: 4

  30. {"0011111","0010011","1100011","1000111","1001000","1111001","1111010"}

    Returns: 4

  31. {"00100000","00000100","10000000","00000001","00000000","01000000","00000000","00010000"}

    Returns: 2

  32. {"011100","100111","100111","111000","011000","011000"}

    Returns: 4

  33. {"0010000","0000010","1000000","0000010","0000000","0101001","0000010"}

    Returns: 2

  34. {"01111111","10111101","11011101","11100111","11100101","11111011","10010100","11111100"}

    Returns: 6

  35. {"011101","101110","110001","110011","010101","101110"}

    Returns: 4

  36. {"0001000","0010001","0101010","1010001","0000010","0010101","0101010"}

    Returns: 3

  37. {"00000000","00000001","00000000","00000010","00000000","00000000","00010000","01000000"}

    Returns: 2

  38. {"000110000","000000011","000000111","100000101","100000011","000000101","001101010","011010101","011111010"}

    Returns: 4

  39. {"000001000","000000010","000000000","000011001","000100000","100100010","000000001","010001000","000100100"}

    Returns: 2

  40. {"000001001","000000000","000100000","001000010","000000010","100000010","000000000","000111000","100000000"}

    Returns: 2

  41. {"011111","101111","110111","111011","111101","111110"}

    Returns: 6

  42. {"00001100","00011101","00011010","01101001","11110100","11001011","00100101","01010110"}

    Returns: 5

  43. {"00000101","00011101","00010111","01101001","01010000","11100000","00100000","11110000"}

    Returns: 4

  44. {"000011","000000","000001","000000","100000","101000"}

    Returns: 2

  45. {"010011","100010","000101","001011","110101","101110"}

    Returns: 3

  46. {"00000000","00001000","00000000","00000000","01000000","00000000","00000000","00000000"}

    Returns: 2

  47. {"0011010","0011000","1101100","1110101","0011011","1000101","0001110"}

    Returns: 4

  48. {"011111","101101","110011","110011","101101","111110"}

    Returns: 5

  49. {"010101","101100","010000","110000","000000","100000"}

    Returns: 3

  50. {"000011","001010","010101","001010","110101","101010"}

    Returns: 3

  51. {"0111110","1000111","1001101","1010111","1111011","1101101","0111110"}

    Returns: 5

  52. {"000011110","001010010","010100000","001010000","110100001","100000010","100000000","110001001","000010010"}

    Returns: 3

  53. {"0011110","0010000","1100110","1000111","1011000","1011000","0001000"}

    Returns: 4

  54. {"01010100","10110111","01001111","11001011","00110111","11101011","01111101","01111110"}

    Returns: 6

  55. {"0001010","0001111","0000101","1100101","0111011","1100101","0111110"}

    Returns: 5

  56. {"00100011","00001110","10001011","00000101","01100000","01010000","11100000","10110000"}

    Returns: 4

  57. {"0111011","1011111","1101000","1110111","0101010","1101101","1101010"}

    Returns: 5

  58. {"01001110","10001111","00010101","00101101","11010111","11111011","11001101","01111110"}

    Returns: 5

  59. {"01110010","10011101","10010000","11100100","01000010","01010000","10001001","01000010"}

    Returns: 4

  60. {"000000000","000000000","000001100","000000000","000001000","001010000","001000001","000000000","000000100"}

    Returns: 2

  61. {"0110001", "1010001", "1101000", "0010100", "0001010", "0000101", "1100010"}

    Returns: 4

    0: **************** 1: **************** 2: **** 3: **** 4: **** 5: **** 6: ****

  62. {"00","00"}

    Returns: 1

  63. {"000", "000", "000"}

    Returns: 1

    Even with no handshakes, each person had to be in the cafe at some time.

  64. { "011011010", "101000111", "110010110", "000001101", "101001000", "100110101", "011101010", "111000100", "010101000" }

    Returns: 5

  65. { "0111", "1011", "1100", "1100" }

    Returns: 3

  66. { "0111111", "1011000", "1100000", "1100100", "1001000", "1000001", "1000010" }

    Returns: 3

  67. { "010000100", "100110001", "000110011", "011010110", "011100111", "000000011", "100110011", "001111101", "011011110" }

    Returns: 5

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: