Escape the Matrix

Implement SparseMatrix, which represents a matrix that stores only non-zero values and supports efficient matrix operations.

This problem focuses on data structure design and algorithmic efficiency, not linear algebra tricks.

---

Constructor

SparseMatrix(rows, cols)

• rows is the number of rows in the matrix.
• cols is the number of columns in the matrix.
• The matrix is initially all zeros.
• Zero values must not be stored internally.

---

Methods

set(r, c, val)

• Sets the value at position (r, c) to val.
• If val == 0, the entry must be removed from storage if present.
• You may assume 0 ≤ r < rows and 0 ≤ c < cols.

get(r, c)

• Returns the value at position (r, c).
• If the entry is not present, return 0.

add(other)

• Returns a new SparseMatrix equal to this + other.
• Matrix dimensions must match.
• Only non-zero entries should be stored in the result.

multiply(other)

• Returns a new SparseMatrix equal to this * other.
• Requires this.cols == other.rows.
• The implementation must avoid iterating over zero entries.

nnz()

• Returns the number of non-zero entries currently stored in the matrix.

---

Behavior Details

• All operations must preserve sparsity (no dense conversion allowed).
• Multiple operations may be chained.
• Addition and multiplication must only process entries that actually exist.
• The implementation should be efficient for large dimensions with few non-zero values.

---

Input Format

The first line contains an integer Q, the number of operations.

Each of the next Q lines is one of the following:

• NEW name rows cols
  Create a new sparse matrix with the given name.

• SET name r c val
  Call set(r, c, val) on matrix name.

• GET name r c
  Call get(r, c) and output the result.

• ADD out A B
  Compute A + B and store the result in out.

• MUL out A B
  Compute A * B and store the result in out.

• NNZ name
  Call nnz() and output the result.

You may assume:

• Matrix names are unique unless overwritten by an operation.
• All indices are valid.
• Errors should be reported if dimensions are incompatible.

---

Output Format

• For each GET operation, output a single integer.
• For each NNZ operation, output a single integer.
• For invalid ADD or MUL operations, output ERROR.

---

Notes

• You may not convert the matrix to a dense representation.
• A correct solution should run in time proportional to the number of non-zero entries involved.
• This problem is about implementation and data structures, not numerical precision.