Statistics

Problem Statement for "TeaCoffee"

Problem Statement

The IBM Research group supports a web page called "Ponder This", where a math problem is posted every month for people to solve. This problem is based on the March 2002 Ponder This Challenge.

A club contains a finite number of members. Some pairs of these members are friends (friendship is symmetric). The club meets once a week and each member drinks one cup of either tea or coffee. At the first meeting each person selects his favorite drink, but starting from the second week he chooses what to drink according to the following rule:

  • He remembers what each of his friends drank last week and chooses what the majority of them drank. If there was a tie (an equal number of coffee and tea drinkers among them) he drinks the same thing he drank last week.

In the IBM puzzle one of the questions was to prove that eventually the drinking pattern becomes periodic with period 1 or 2. We will solve a much simpler problem. We will find if they stabilize on everybody drinking the same drink within a year.

Your task is, given a String[] describing friendships and a String[] describing what everybody chose for the first week, follow what everybody drinks for one year (51 more weeks) and return the smallest week number when everybody drinks the same thing. If there is no such week in the year, return -1. Assume that the starting week is week number 1.

In more detail:

Assume that club members are numbered from 0. For each i, the String friends[i] will list the friends of club member i. The String favoriteDrinks[i] will represent the favorite drink of club member i. Each element of friends will be a space separated list of integers. For example if the 0-th String is " 2 3 5", then the 0-th member has the second, third and fifth members as his friends.

Definition

Class:
TeaCoffee
Method:
stabilizes
Parameters:
String[], String[]
Returns:
int
Method signature:
int stabilizes(String[] friends, String[] favoriteDrinks)
(be sure your method is public)

Constraints

  • friends has between 1 and 25 elements inclusive
  • favoriteDrinks has the same number of elements as friends
  • each element of favoriteDrinks is either "TEA" or "COFFEE"
  • each element of friends has between 1 and 50 characters inclusive, and only contains digits '0'-'9' and space (' ') characters
  • each integer in each element of friends will be between 0 and the number of elements in friends - 1, inclusive, without leading zeros
  • no integer will appear more than once in the same element of friends
  • no person appears in his own list of friends
  • friends represents a symmetrical friendship relationship, that is, if A appears on the list of friends of B, then B appears on the list of friends of A

Examples

  1. {" "," "}

    {"TEA","TEA"}

    Returns: 1

    Though there are no friends in the club, everybody starts with the same drink

  2. {" 1 2","0 2","0 1 "}

    {"TEA","TEA","COFFEE"}

    Returns: 2

    Everybody is friends with each other, so they all will drink TEA starting from the second week

  3. {"1 2 3","0 2 3","0 1 3","0 1 2"}

    {"TEA","TEA","COFFEE","COFFEE"}

    Returns: -1

    Everybody is friends with each other. Each week they will choose the drink they didn't drink the previous week, hence it never stabilizes.

  4. {"1","0 2","1 3","2 4","3 5","4 6","5 7","6 8","7 9","8 10","9 11", "10 12","11 13","12 14","13 15","14 16","15 17","16 18","17 19", "18 20","19 21","20 22","21 23","22 24","23"}

    {"TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "TEA", "TEA"}

    Returns: 23

  5. {" 1"," 0 2"," 1 3"," 2"}

    {"TEA","COFFEE","TEA","TEA"}

    Returns: 3

  6. {" 1 2 3 4", " 0 2 3 4", " 0 1 3 4", " 0 1 2 4", " 0 1 2 3", " ", " "}

    {"TEA", "TEA", "TEA", "TEA", "TEA", "TEA", "COFFEE"}

    Returns: -1

  7. {" 1 3"," 0 2"," 1 3"," 0 2"}

    {"COFFEE","COFFEE","TEA","TEA"}

    Returns: -1

    personal comment non-bipartite graph that doesn't stabilize

  8. {" 1 3 5 7"," 0 2 4 6"," 1 3 5 7"," 0 2 4 6"," 1 3 5 7"," 0 2 4 6"," 1 3 5 7"," 0 2 4 6"}

    {"TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE"}

    Returns: -1

    personal comment - 4/4 bipartite graph

  9. {" 24 1"," 0 2"," 1 3"," 2 4"," 3 5"," 4 6"," 5 7"," 6 8"," 7 9"," 8 10"," 9 11", " 10 12"," 11 13"," 12 14"," 13 15"," 14 16"," 15 17"," 16 18"," 17 19", " 18 20"," 19 21"," 20 22"," 21 23"," 22 24"," 23 0"}

    {"TEA","TEA","COFFEE","COFFEE","TEA","TEA","COFFEE","COFFEE","TEA","TEA","COFFEE","COFFEE","TEA","TEA","COFFEE","COFFEE","TEA","TEA","COFFEE","COFFEE","TEA","TEA","COFFEE","COFFEE","COFFEE"}

    Returns: -1

    personal comment - circle

  10. {" 24 1"," 0 2"," 1 3"," 2 4"," 3 5"," 4 6"," 5 7"," 6 8"," 7 9"," 8 10"," 9 11", " 10 12"," 11 13"," 12 14"," 13 15"," 14 16"," 15 17"," 16 18"," 17 19", " 18 20"," 19 21"," 20 22"," 21 23"," 22 24"," 23 0"}

    {"TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","COFFEE"}

    Returns: 13

  11. {" 24 1"," 0 2"," 1 3"," 2 4"," 3 5"," 4 6"," 5 7"," 6 8"," 7 9"," 8 10"," 9 11", " 10 12"," 11 13"," 12 14"," 13 15"," 14 16"," 15 17"," 16 18"," 17 19", " 18 20"," 19 21"," 20 22"," 21 23"," 22 24"," 23 0"}

    {"TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","COFFEE","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","COFFEE"}

    Returns: 7

  12. {" 1 2 3 4 5 6 7 8 9 10 11 12 13 14"," 0 2 3 4 5 6 7 8 9 10 11 12 13 14"," 1 0 3 4 5 6 7 8 9 10 11 12 13 14"," 1 2 0 4 5 6 7 8 9 10 11 12 13 14"," 1 2 3 0 5 6 7 8 9 10 11 12 13 14"," 1 2 3 4 0 6 7 8 9 10 11 12 13 14"," 1 2 3 4 5 0 7 8 9 10 11 12 13 14"," 1 2 3 4 5 6 0 8 9 10 11 12 13 14"," 1 2 3 4 5 6 7 0 9 10 11 12 13 14"," 1 2 3 4 5 6 7 8 0 10 11 12 13 14"," 1 2 3 4 5 6 7 8 9 0 11 12 13 14"," 1 2 3 4 5 6 7 8 9 10 0 12 13 14"," 1 2 3 4 5 6 7 8 9 10 11 0 13 14"," 1 2 3 4 5 6 7 8 9 10 11 12 0 14"," 1 2 3 4 5 6 7 8 9 10 11 12 13 0"},

    {"TEA","TEA","TEA","TEA","TEA","TEA","TEA","TEA","COFFEE","COFFEE","COFFEE","COFFEE","COFFEE","COFFEE","COFFEE"}

    Returns: 2

    15-complete graph

  13. {" 1"," 0 2"," 1 3"," 2 4"," 3 5"," 4 6"," 5 7"," 6 8"," 7 9"," 8 10"," 9 11", " 10 12"," 11 13"," 12 14"," 13 15"," 14 16"," 15 17"," 16 18"," 17 19", " 18 20"," 19 21"," 20 22"," 21 23"," 22 24"," 23"}

    {"TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE", "TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","COFFEE","COFFEE","COFFEE"}

    Returns: 22

  14. {" 3", " 4", " 5", " 0 6", " 1 7", " 2 8", " 3 9", " 4 10", " 5 11", " 6 12", " 7 13"," 8 14"," 9 15", " 10 16", " 11 17", " 12 18", " 13 19", " 14 20", " 15 21", " 16 22", " 17 23", " 18 24", " 19 24", " 20 24", " 21 22 23"}

    {"TEA","TEA","TEA","COFFEE","COFFEE","COFFEE","TEA","TEA","TEA","COFFEE","COFFEE","COFFEE", "TEA","TEA","TEA","COFFEE","COFFEE","COFFEE","TEA","TEA","TEA","COFFEE","COFFEE","COFFEE","COFFEE"}

    Returns: 8

    personal comment - star with long rays

  15. {" 1"," 0 2"," 1 3"," 2 4"," 3 5"," 4 6"," 5"," 8"," 7 9"," 8 10"," 9"}

    {"TEA","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","COFFEE","COFFEE","TEA","COFFEE"}

    Returns: -1

    personal comment - two lines coming to different limits

  16. {" 1"," 0 2"," 1 3"," 2 4"," 3 5"," 4 6"," 5"," 8"," 7 9"," 8 10"," 9"}

    {"TEA","TEA","COFFEE","TEA","COFFEE","TEA","COFFEE","TEA","TEA","COFFEE","TEA"}

    Returns: 6

  17. {"1","0 2","1 3","2 4","3 5","4 6","5 7","6 8","7 9","8 10","9 11", "10 12","11 13","12 14","13 15","14 16","15 17","16 18","17 19", "18 20","19 21","20 22","21 23","22 24","23"}

    {"COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "COFFEE","COFFEE"}

    Returns: 23

  18. {"1 3","0 2","1 3","0 2 4 5","3","3"}

    {"TEA","COFFEE","TEA","COFFEE","COFFEE","COFFEE"}

    Returns: 3

  19. {"1 3 4 2","0 2 3","1 3 0","0 2 1 4","0 3"}

    {"COFFEE","TEA","COFFEE","TEA","COFFEE"}

    Returns: 3

  20. {"1 21 22 23","0 2","1 3","2 4","3 5","4 6","5 7","6 8","7 9","8 10","9 11", "10 12","11 13","12 14","13 15","14 16","15 17","16 18","17 19", "18 20","19 21","20 0","0","0"}

    {"COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "COFFEE"}

    Returns: 12

  21. {" "}

    {"COFFEE"}

    Returns: 1

  22. {" "}

    {"TEA"}

    Returns: 1

  23. { "1 2 3", "0 2 3", "0 1 3", "0 1 2" }

    { "TEA", "TEA", "COFFEE", "COFFEE" }

    Returns: -1

  24. { " 1 2", "0 2", "0 1 " }

    { "COFFEE", "COFFEE", "TEA" }

    Returns: 2

  25. { " ", " " }

    { "TEA", "COFFEE" }

    Returns: -1

  26. { "1", "0 2", "1 3", "2 4", "3 5", "4 6", "5 7", "6 8", "7 9", "8 10", "9 11", "10 12", "11 13", "12 14", "13 15", "14 16", "15 17", "16 18", "17 19", "18 20", "19 21", "20 22", "21 23", "22 24", "23" }

    { "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "COFFEE", "TEA", "TEA", "TEA" }

    Returns: 23

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: