CCC '05 S4 - Pyramid Message Scheme - Olympiads Online Judge

CCC '05 S4 - Pyramid Message Scheme

View as PDF

Submit solution

All submissions

Best submissions

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$ ~10~ seconds to be delivered. So the example given above would be completed in $80$ ~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$ ~8~ messages at $10$ ~10~ seconds per message is $80$ ~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$ ~40~ seconds to accomplish the communication that takes $80$ ~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$ ~L~, followed by $L$ ~L~ message lists. Each list begins with an integer, $n$ ~n~, identifying the number of message recipients in the list, followed by $n$ ~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

Comments

3

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. ← edited →

What are the limits on $n$ ~n~?

10

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

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

43

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.

-5

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.

This comment is hidden due to too much negative feedback. Show it anyway.

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 :(