CCC '05 S4 - Pyramid Message Scheme

View as PDF

Submit solution

Points: 10
Time limit: 1.0s
Memory limit: 256M

Problem type
Canadian Computing Competition: 2005 Stage 1, Senior #4

Spamway Inc. maintains a network of zombie computers to solicit and collect orders for its various fine products. Each zombie computer is responsible for zero or more subordinate zombies that it coordinates in these activities.

Spamway uses a simple communication strategy among its zombies for transmitting solicitations and receiving orders. Each solicitation originates at Spamway's head zombie, which then communicates it to each of its subordinates in turn, waiting to collect orders from one subordinate before proceeding to the next. Each subordinate employs the same strategy - it sends to and receives from each of its subordinates in turn.

For example, suppose that Home has two subordinate zombies named Alfred and Betty; Alfred's subordinates are named Cindy and Dennis; Betty has no subordinates. This organization is pictured below.

            Cindy
           /
     Alfred
    /      \
Home        Dennis
    \
     Betty

Home first sends to Alfred; Alfred then sends to Cindy; Cindy responds to Alfred; Alfred sends to Dennis; Dennis responds to Alfred; Alfred responds to Home; Home sends to Betty; Betty responds to Home.

Each message takes 10 seconds to be delivered. So the example given above would be completed in 80 seconds. You have been retained by Spamway, who will pay you handsomely (in Spam Bucks which may be redeemed for any of their valuable products) to help them reduce the time necessary to solicit and collect orders. In particular, Spamway is considering a new strategy in which each zombie sends out messages to each of its subordinates and waits for their responses only after all messages have been sent.

Spamway's network administrator has captured a chronological list of the name of the recipient of each message involved in a particular solicitation. For the example above, using the slow strategy, this list would be: Alfred, Cindy, Alfred, Dennis, Alfred, Home, Betty, Home. (Note that 8 messages at 10 seconds per message is 80 seconds.)

Using the new and improved strategy, Home sends to Alfred and Betty simultaneously, Alfred sends to Cindy and Dennis at the same time as Betty is responding, Cindy and Dennis respond simultaneously to Alfred and finally Alfred responds to Home. Using the new strategy, Spamway needs only 40 seconds to accomplish the communication that takes 80 seconds using the old strategy. Thus, Spamway can send twice as many solicitations and make twice as much money.

Input Specification

As input, you are given lists of names describing the order that messages are received using the old Spamway strategy. The input contains the integer L, followed by L message lists. Each list begins with an integer, n, identifying the number of message recipients in the list, followed by n lines, each containing the name of a message recipient.

Output Specification

For each list you are to print out a single integer indicating the amount of time in seconds that Spamway saves.

Sample Input

1
8
Alfred
Cindy
Alfred
Dennis
Alfred
Home
Betty
Home

Sample Output

40

Comments


  • 2
    dechen4198  commented on May 28, 2022, 5:25 a.m.

    Wow I really didn't read the input specification carefully...


  • 3
    RIPRoyale  commented on Nov. 29, 2021, 10:14 p.m.

    Always read the output specification.... Had a working solution but didn't do subtraction lol


  • 1
    Subway_Man  commented on March 28, 2020, 12:19 a.m. edited

    Nevermind, the question requires output for multiple lists, eliminating the need for more testcases.


  • 9
    hi_there  commented on Nov. 2, 2017, 2:14 a.m.

    What are the limits on n?


    • 10
      Kirito  commented on Nov. 2, 2017, 5:01 p.m.

      1 \le L \le 10, and 1 \le n \le 100.


  • 42
    nathanl3  commented on Oct. 10, 2016, 11:11 p.m.

    It might be helpful to clarify that the root node will not always be named "Home", even though this is never confirmed nor denied in the problem statement.


    • -4
      account_disabled  commented on Feb. 13, 2018, 1:24 p.m.

      For test 5/10, its "home" not "Home"... just do the last element. Debugging for EVER.


      • 11
        0xc3  commented on March 27, 2018, 6:41 p.m.

        It's not even "home" nor "Home" for the last two cases. Don't waste time like me, who tried to change all uppercase letters to lowercase.


    • 10
      Xue_Alex  commented on Jan. 17, 2018, 5:26 a.m.

      saw your comment after debugging hopelessly... feels bad :(