Assessment Solutions and Scoring

Use only after saving an independent attempt. These are expected derivations and acceptance criteria, not a single required wording or witness. Apply the per-competency levels; a correct scalar cannot compensate for an invalid state.

A1 / C1

Unordered combinations for 5 are 11111,1112,122: count 3. Classifying by the number of 2s gives 0,1,2 with the rest ones, a disjoint complete partition. Ordered sequences number 8: 11111; four placements of one 2 among three ones; three placements of the one 1 among two 2s. The sequence recurrence is Q(t)=Q(t-1)+Q(t-2) with Q(0)=1, negative t contributing 0. A combination counter uses denomination prefix and target, or denomination-outer tabulation; its take branch keeps the current type available, while skip reduces the prefix. Every transition reduces target or type prefix under a suitable lexicographic rank.

Level-2 evidence: identifies counted objects, bases, non-overlapping decision classes, cache/state sufficiency and O(types*target) arithmetic work for these formulations. Double counting permutations as combinations is a C1 failure.

A2 / C2

Strict LIS length is 3, indices [1,2,4] or [1,3,4]. Lower-bound replacement prevents both equal 2s being used. An alignment for cab -> abc is (c,None),(a,a),(b,b),(None,c), cost 2. A single edit cannot produce the target: with equal lengths one operation would have to be a substitution, but all three positions differ. This establishes the small example's lower bound.

Level-2 evidence: checks index order and strict values; both ungapped strings and alignment cost; explains equality semantics; O(n log(n+1)) LIS time/O(n) witness storage and O((m+1)(n+1)) full-table edit time/storage. Insert/delete-only is a different contract even when this particular pair's answer still equals 2.

A3 / C3

Indices [0,1] use weight 5 and value 11. Other feasible nonempty subsets are the three singletons; item 2 alone gives 8. Exact weight 1 is impossible. Use only weight 0 reachable in the exact-fill base. One (2,3) item at capacity 4 becomes illegally value 6 with ascending updates. Descending scalar updates give 3, but mutable capacity parents can still yield repeated item 0.

Level-2 evidence: derives take/skip from the previous prefix and safely reconstructs while decreasing that prefix. Full table uses O((n+1)(W+1)) cells and the same-order work; value-only rolling uses O(W+1) cells but does not justify the same bound for naive parent reconstruction. Classify the W-dependent bound as pseudo-polynomial and state positive-weight requirements.

A4 / C4

Matrix tree (0,(1,2)) costs 24+30=54; the other parenthesization costs 100. Each split preserves fixed boundary dimensions, so child substitutions remain legal. On the star, leaf states are (skip,take)=(0,3), center (9,7); select leaves [1,2,3]. With center selected no leaf is permitted. Without center, child subtrees are independent because no edges join them.

Level-2 evidence: derives multiplication factors, interval bases and length order; validates connected acyclic input; gives O(n³)/O(n²) matrix costs and O(V) tree costs. Triangle plus isolated vertex disproves the edge-count-only check.

A5 / C5

Tours cost 4 via [0,1,2,0] and 12 via [0,2,1,0]. Removing 2->0 leaves the second. Base only {0},0; states encode exactly visited mask and last vertex; return edge required. Missing tours return (None,[]). Signed edges do not make a simple Hamiltonian tour unbounded because revisits are excluded.

Level-2 evidence: O(n2^n) states/storage and O(n²2^n) candidate work; n=20 rectangular payload is 167,772,160 bytes or 160 MiB at eight bytes per slot, before containers/keys/parents/objects. Checks vertex uniqueness, complete coverage, edge existence, closure and summed cost. A cheap open path is a failure.

A6 / C6

Numbers through 205 are 2,11,20,101,110,200, count 6. Restricting to 100..205 leaves 101,110,200, count 3. State (position,sum,tight) suffices for digit sum; transition uses old_tight and digit==bound_digit. Terminal count is one iff sum=2. Zero is included only for target sum 0. Per-query memoization, including tight states, is valid when bound and target are fixed.

Level-2 evidence: justifies unique padded representations, F(-1,S)=0 and range subtraction. A contains-zero variant must distinguish leading padding, then handle canonical zero at termination. General arithmetic bound is O(D10(min(S,9D)+1)); rolling storage O(D+min(S,9D)+1). Counts can require large integers. Enumerating 0..205 is a check, not the general algorithm.

A7 / C7

Earliest-finish greedy selects jobs 0,1 for cardinality 2 and value 8. Weighted optimization selects job 2 for value 9. Under budget 2, job 2's cost 3 is infeasible, so select 0,1 for 8. With sorted-prefix index i and budget b, D(i,b)=max(D(i-1,b), value[i-1]+D(p(i-1),b-cost[i-1])) when the cost fits. Bases are zero for no jobs and any at-most budget. Reconstruct through prefix and budget; the compatible predecessor can be far earlier than the last row.

Level-2 evidence: proves cardinality exchange and weighted take/skip separately, preserves original IDs and checks both nonoverlap and budget. Gives O(n log(n+1)+n(B+1)) work, O((n+1)(B+1)) full-table storage, and names the additional budget information absent from the old prefix-only optimum.

A8 / C8

Count transitions per state: rod cutting has n+1 states but Θ(n²) work. Exact Fibonacci uses O(1) integer objects with Θ(n) live bits, not constant bits. Two edit rows compute a value; alignment requires retained choices, recomputation or a separately derived low-space reconstruction. A feasible witness establishes attainability, not absence of a better solution. Matrix/tree recurrences combine several children, so their dependency DAG is not automatically a single-path optimization.

Level-2 evidence: proposes an oracle genuinely small enough to exhaust, checks witness legality separately, gives a contract-changing counterexample, and distinguishes tests, general proofs, resource estimates and measurements. For example enumerate all item subsets for tiny knapsack and reject reused IDs even if the returned scalar equals the exhaustive optimum.

Transfer scoring

Level 3 requires a fresh changed problem solved without this key, with a new proof and resource account. Record conceptual and arithmetic repairs separately. Do not promote a learner or the curriculum based solely on aggregate percentages.