Spreadsheet String Concatenation with Dependent Cells

Implement a 26-column, 100-row spreadsheet that stores strings and supports formulas that concatenate other cells. When a referenced cell changes, future reads of dependent formulas must reflect the new string.

Use columns A through Z and rows 1 through 100. Implement concatenate_sheet(operations: string[][]) -> string[]:

• ["set", cell, raw] stores a literal string or formula and returns the string "OK".
• A raw value starting with = is a formula, such as =C1C2, which concatenates the computed values of C1 and C2 in that order.
• ["get", cell] returns "VALUE:" followed by the computed string, or exactly "CYCLE" if the read reaches a circular reference.
• Return one string per operation. The VALUE: prefix is part of the output contract and distinguishes arbitrary literal content from error/status tokens.

Constraints & Assumptions

• The fixed grid size and concatenation form are the reported variant; the following parsing and error rules make the practice task deterministic.
• A formula is = followed by one or more valid cell names with no separators or spaces. Each name has exactly one uppercase column letter followed by a decimal row number without leading zero.
• Repeated references repeat the corresponding string. Formula order matters.
• A literal does not start with =. Unset cells evaluate to the empty string, so getting one returns "VALUE:".
• Set replaces the old literal or formula completely. Cycles are stored and diagnosed on reads that reach them; an unrelated cycle does not affect another cell.
• There are at most 500 operations, at most 20 references per formula, and at most 100 characters per literal. Every successfully evaluated cell has a computed length of at most 10,000 characters.
• All inputs follow the grammar and grid bounds. Persistent stale caches must not survive an input update.

Examples

operations = [
  ["set","C1","hello"],
  ["set","C2"," world"],
  ["set","A1","=C1C2"],
  ["get","A1"],
  ["set","C1","goodbye"],
  ["get","A1"]
]
result = ["OK","OK","OK","VALUE:hello world","OK","VALUE:goodbye world"]

operations = [["set","A1","=B1B1"],["set","B1","=A1"],["get","A1"]]
result = ["OK","OK","CYCLE"]

Hint: Parse references before evaluating them

The next uppercase letter starts the next cell reference. Preserve the resulting reference sequence even if a separate dependency set is used for cycle detection.

Spreadsheet String Concatenation with Dependent Cells

Hints

1. A get must preserve literal content even when it resembles a status token.
2. An unrelated circular reference must not affect the requested cell.

Approach

Store the latest raw string for each set. For each get, start a fresh memo table and active-recursion set. A cell already active lies on the current dependency path, so reaching it proves a cycle. A completed memoized cell is safe to reuse, including in a shared dependency graph. An unset cell contributes the empty string. For a formula, parse its references from left to right, evaluate every occurrence, and concatenate in that same order. Mark a cell complete only after all of its references complete. Induction on the dependency DAG proves each completed value equals its definition. A reachable cycle aborts the read; all traversal state is discarded, so repairing formulas or changing literals is visible on the next get.

• Time complexity: O(S + sum_g(P_g + L_g)) expected, where S is total stored-input processing, P_g is reachable raw-text size, and L_g is total constructed string length for read g
• Space complexity: O(S_live + max_g(V_g + L_g)) auxiliary, excluding returned strings; memoization and traversal state are per read