Difficulty: Intermediate | Prerequisites: Trie Fundamentals study notes (part 1 of this set), comfort with C I/O (scanf), dynamic memory allocation.

Big Picture

This is the applied problem where you put your trie knowledge to work. You are managing feeding records for orangutans whose names can change over time, and you need to answer prefix-sum queries efficiently. The problem exercises three skills at once: building and updating a trie, handling event-driven input parsing in C, and reasoning carefully about how name changes propagate through a prefix-sum structure. It is a graded assignment worth up to 100 points with strict compilation and output requirements.

TL;DR

Read a stream of events (feedings, name changes, prefix queries) and use a trie with subtreeSum tracking to answer each query. The main pitfall is handling name changes correctly by subtracting from the old path and adding to the new path.

Key Terms

Event type 1 (feeding)

Format: 1 name amount. Add amount mangos to the named orangutan. Update subtreeSum along the entire path from root to the name's endpoint, and increment nodeTotal at the endpoint.

Event type 2 (name change)

Format: 2 oldName newName. Move the orangutan's accumulated mangos from the old name path to the new name path. No orangutan will change to an already-existing name.

Event type 3 (prefix query)

Format: 3 prefix. Print the total mangos eaten by all orangutans whose current name starts with prefix. This is the subtreeSum at the node where the prefix path ends.

Core Content

Input Parsing

The first line gives two integers: n (number of orangutans, up to 500,000) and e (number of events, up to 500,000). You do not need to do anything with n other than read it. The next e lines each start with an integer (1, 2, or 3) that tells you how many additional tokens to read:

• Event 1: read a string and an integer.

• Event 2: read two strings.

• Event 3: read one string.

Switching on the event type to decide how many tokens to scan is part of the grading rubric (5 points).

Constraints to Remember

• Names are strictly uppercase A through Z, at most 20 characters, no whitespace.

• Feeding amounts are between 1 and 100 inclusive.

• No orangutan changes to an already-existing name, so you will never have collisions during a name change.

• No orangutan has eaten anything before the events begin.

• All output is from event type 3 only. No prompts, no debug prints, no extra whitespace.

Walkthrough of Sample Case 1

Initial state: 10 orangutans exist, but we only interact with those mentioned in events.

Walkthrough of Sample Case 2

Four orangutans, eight events. Pay close attention to event 6, where WILL becomes MATT:

Implementation Skeleton

The overall structure of your C program:

1. Read n and e.
2. Create the trie root (a single empty node).
3. For each of the e events:
   a. Read the event type.
   b. If type 1: read name and amount, walk/create the path,
      add amount to subtreeSum at each node, add amount
      to nodeTotal at the endpoint.
   c. If type 2: read oldName and newName.
      - Walk oldName to find nodeTotal at its endpoint.
      - Walk oldName again (or in the same pass), subtracting
        nodeTotal from subtreeSum at each ancestor.
      - Set old endpoint's nodeTotal to 0.
      - Walk/create newName path, adding the saved value to
        subtreeSum at each node and setting nodeTotal at the
        new endpoint.
   d. If type 3: read prefix, walk the trie. If you reach the
      end of the prefix, print subtreeSum. If you hit NULL,
      print 0.
4. Free all allocated memory (good practice, though not
   typically graded).

Edge Cases to Watch

• A query prefix that matches no path at all (NULL hit on the first character): return 0.

• A query prefix that exactly equals a stored name: the subtreeSum at that endpoint includes the orangutan itself plus any names that extend it further (e.g., querying "WILL" includes WILLIAM, WILLIAN, WILLY, and WILL itself).

• Feeding an orangutan that has never been fed before: you create new nodes as you walk the path. This is the "insert only names you read" requirement.

• A name change for an orangutan that has eaten 0 mangos: the subtraction is 0, so the trie values do not change, but you may still need to create nodes for the new name if it is later fed.

Grading Breakdown

The assignment is scored out of 100 points total:

• Good comments, whitespace, variable names: 15 points

• No extra input/output (no prompts or debug prints): 10 points

• Switch token reading based on event type: 5 points

• Offset letters by 'A' for index mapping (0 to 25): 5 points

• Insert only names you actually read: 5 points

• Correctly handle name changes (remove old value, add to new): 10 points

• 10 test cases at 5 points each: 50 points

Programs that do not compile with gcc -std=gnu11 -lm receive 0. Programs that do not use a trie are capped at 50.

Common Misconceptions

• Students sometimes think that a name change deletes the old name's nodes from the trie. It does not. You zero out the nodeTotal and subtract from subtreeSum along the path, but the nodes remain because other names might share that prefix.

• Students occasionally try to use a hash map for everything, which handles feedings and name changes but cannot answer prefix queries efficiently. The problem requires a trie for a reason.

• Students forget that the query is about current names. If BETTY changed to ALICE, a query for "B" should no longer include BETTY's mangos, even though BETTY was the name at the time of feeding.

• Students sometimes update subtreeSum only at the endpoint node during a feeding, missing the ancestor updates. Every node on the path from root to endpoint must be incremented.

Why It Matters / Exam Flags

⚠️ Trace through both sample cases by hand before writing code. The second case in particular exercises name changes interleaved with feedings and queries.

⚠️ The name change logic (subtract old, add new) is worth 10 points on its own and is the most error-prone part of the implementation.

⚠️ Make sure your program produces no output other than the answers to type-3 queries, one per line. Even a stray newline or prompt will cost 10 points.

⚠️ Time limit is strict: 10 seconds or 5x the instructor's solution time. The O(L) operations on a trie with L at most 20 are well within bounds, but an inefficient subtree traversal on every query could time out on the larger cases.

Quick Self-Test

T/F: You need to pre-allocate nodes for all n orangutans at the start. False. You create nodes only as names appear in events.

Fill in the blank: Event type 2 reads ____ string(s) from the input. Two (the old name and the new name).

T/F: After a name change from BETTY to ALICE, querying prefix "A" will include BETTY's old mangos. True. Those mangos now belong to ALICE, whose name starts with A.

T/F: If WILL changes to MATT, the W->I->L->L nodes are deleted from the trie. False. They remain, with subtreeSum reduced by WILL's nodeTotal. Other names like WILLIAM may still use those nodes.

Fill in the blank: The maximum length of any name or prefix in this problem is ____ characters. 20.

Practice Q&A

Q: Given events 1 CAT 3, 1 CAR 7, 3 CA, what is the output?

A: 10. Both CAT (3) and CAR (7) share the prefix "CA", so the subtreeSum at the A-node (child of C) is 10.

Q: After events 1 DOG 5, 2 DOG DEER, 3 D, what is the output?

A: 5. DOG's 5 mangos were moved to DEER. DEER starts with D, so the D-node's subtreeSum is still 5.

Q: After events 1 DOG 5, 2 DOG DEER, 3 DO, what is the output?

A: 0. DOG was renamed to DEER, so the path D->O no longer has any mangos associated with it. The subtreeSum at the O-node (child of D) was reduced to 0 during the name change.

Q: Why can we not use a hash map alone to solve this problem?

A: A hash map can store name-to-mango mappings, but answering "how many mangos for all names starting with prefix P" would require scanning every key in the map to check for the prefix, which is O(n) per query. A trie answers the same query in O(L) by reading subtreeSum at the prefix endpoint.

Q: What should you print if the prefix in a type-3 event matches no path in the trie?

A: 0.

Connections to Other Topics

This problem combines data structures (tries) with event-driven simulation, a pattern that shows up again in operating systems (event loops) and databases (transaction logs). The subtreeSum technique, where you maintain running aggregates at internal nodes, is a general principle that also appears in segment trees and binary indexed trees, both of which you may encounter in an algorithms or competitive programming course. The name-change mechanic is a practical example of maintaining data integrity when keys change, a challenge that comes up in database indexing and file system design.

Related Terms / Search Tags

Name Game, trie assignment, COP 3502, UCF Computer Science I, prefix sum trie, orangutan feeding problem, trie in C, name change trie, subtreeSum, prefix query, event-driven trie, trie implementation C, gcc gnu11, competitive programming trie