2005 Canadian Computing Competition, Stage 1

Problem S4: Pyramid Message Scheme

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

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

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

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 30, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

When I started to solve this problem I thought that the root node was always named "Home" but this assumption proved to be wrong. Also, it would be useful to consider that the maximum value for n is 1000.

Is the head zombie always home?

I believe the problem statement is clear enough

^ Title. Just a heads up, and great job with your project! May we all get IOI gold

1
10
Alfred
Cindy
Alfred
Dennis
Alfred
Home
Betty
Home
Cindy
Home

That doesn't appear to be a valid input.