--- title: 'Using Practice Environments' source: 'https://academia.sh/en/courses/advanced-algorithms/using-practice-environments' course: 'Advanced Algorithms and Problem Solving' language: en updated: '2026-08-17T18:07:28+00:00' license: 'CC BY-SA 4.0' --- # Using Practice Environments Counting repeated practice's progress metric over the shared reference's five patterns: an environment that solves 144 problems sees all five patterns too, but its balance ratio is 0.2431, against 0.6667 in an environment that solves 30. The previous two lessons concerned a single solution: which pattern is chosen, how it is tested. This lesson carries the question outside a single solution. Practice is repeated work, and repeated work has to have a progress metric, or the work continues without anyone knowing where it is going. Environments are referred to by **type**, because what is measured is not the environment itself but the **shape of the problem stream** it produces. The result comes in two steps: neither the number of problems solved nor how many distinct patterns were seen is a progress metric. ## Three Environment Types In a **pool-based practice environment**, a large number of problems sit available and the person practicing chooses. Because the choice is free, it drifts toward what is familiar; the pattern distribution reflects the practitioner's habit. In a **timed contest environment**, the environment determines the set and the practitioner has to see all of it; the set is small. In an **in-house assessment**, the number of problems is smallest, the distribution is again not chosen by the practitioner, and the inputs are not prepared in advance. - **AD21** — The pattern set is the shared reference's five patterns: two pointers, sliding window, greedy, backtracking, memoization. These are the patterns measured throughout the course. - **AD22** — A round is one practice session spent in an environment. Problems per round are fixed by environment type: pool 24, contest 5, assessment 2. Six rounds are measured. - **AD23** — In the pool-based environment, choice weights are 50, 30, 10, 6, 4; in the other two environments the distribution is even. The weight models the practitioner's tendency to return to a familiar pattern. - **AD24** — Choice is made with the shared reference's deterministic generator; `random` is not used. - **AD25** — The **balance ratio** is the count of the least-seen pattern divided by its share under an even distribution. If all five patterns were seen equally, the ratio would be 1.0000. ```python """Pattern diversity across three environment rounds, over the shared reference's five patterns.""" SEED, SECOND = 20260218, 20260219 PATTERNS = ["two pointers", "sliding window", "greedy", "backtracking", "memoization"] ENVIRONMENTS = [("pool-based practice ", 24, [50, 30, 10, 6, 4]), ("timed contest ", 5, [20, 20, 20, 20, 20]), ("in-house assessment ", 2, [20, 20, 20, 20, 20])] def generator(seed): d = seed def next_value(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_value def choose(r, weights): x = r(sum(weights)) for i, w in enumerate(weights): if x < w: return i x -= w return len(weights) - 1 def metrics(counts): total = sum(counts) fair_share = total / len(counts) return {"problems": total, "covered": sum(1 for c in counts if c), "balance": round(min(counts) / fair_share, 4), "top_two": round(sum(sorted(counts)[-2:]) / total, 4)} def run(seed, rounds=6): print(f"seed {seed} , {rounds} rounds") print("environment problems covered balance top two distribution") for ad, per_round, weights in ENVIRONMENTS: r = generator(seed) counts = [0] * len(PATTERNS) for _ in range(rounds * per_round): counts[choose(r, weights)] += 1 o = metrics(counts) print(f"{ad} {o['problems']:7d} {o['covered']:8d} {o['balance']:6.4f}" f" {o['top_two']:7.4f} {counts}") run(SEED) print() run(SECOND) print() print("pool-based environment , cumulative round by round (seed 20260218)") print("round problems covered balance top two") r = generator(SEED) counts = [0] * len(PATTERNS) for t in range(1, 7): for _ in range(24): counts[choose(r, ENVIRONMENTS[0][2])] += 1 o = metrics(counts) print(f"{t:3d} {o['problems']:7d} {o['covered']:8d} {o['balance']:6.4f}" f" {o['top_two']:7.4f}") ``` ``` seed 20260218 , 6 rounds environment problems covered balance top two distribution pool-based practice 144 5 0.2431 0.7986 [64, 51, 11, 11, 7] timed contest 30 5 0.6667 0.5000 [4, 5, 9, 6, 6] in-house assessment 12 5 0.4167 0.5833 [1, 4, 3, 2, 2] seed 20260219 , 6 rounds environment problems covered balance top two distribution pool-based practice 144 5 0.1389 0.8194 [76, 42, 16, 6, 4] timed contest 30 5 0.6667 0.5667 [8, 4, 9, 4, 5] in-house assessment 12 5 0.4167 0.6667 [1, 1, 5, 2, 3] pool-based environment , cumulative round by round (seed 20260218) round problems covered balance top two 1 24 4 0.0000 0.8333 2 48 5 0.2083 0.7917 3 72 5 0.2778 0.7639 4 96 5 0.2604 0.7500 5 120 5 0.2500 0.7750 6 144 5 0.2431 0.7986 ``` The first table refutes two metrics at once. The pool-based environment solves **144** problems, the timed contest **30**, the in-house assessment **12** — a 12-times difference. Yet **the count of covered patterns is 5 in all three**: "how many problems did I solve" swings 12 times over; "how many distinct patterns did I see" does not move at all. The metric that distinguishes them is the distribution. In the pool the balance ratio is **0.2431**: the least-seen pattern gets under a quarter of its even-distribution share, and the two most-seen patterns cover **0.7986** of the problems. The timed contest gives **0.6667** with 30 problems — **2.74 times** more balanced on five times fewer. The in-house assessment's 0.4167 comes not from the distribution but from the smallness of the sample. The third table is the lesson's most contrarian result. In the pool-based environment, coverage rises to 5 in the **second round** and never changes again: the 72 problems solved from round three to round six **add nothing** to it. The balance ratio peaks at 0.2778 in the third round and then **falls** — 0.2604 in the fourth, 0.2431 in the sixth. As problem count rises, the progress metric declines, because every added problem goes to the two dominant patterns. The second corpus confirms the ranking: at seed `20260219` the pool gives 0.1389, the contest 0.6667, the assessment 0.4167. The pool's value drops from 0.2431 to 0.1389 — **the absolute value depends on the corpus** — but the ordering of the three environments and the size of the gap between pool and contest run the same way on both. ## Does the Environment Show the Error Distribution alone is not enough either. Applying a pattern fifty times does not show **what it does when its precondition breaks** — the shared reference's first reading already proved this: two pointers matches the oracle on 40 of 40 inputs when the precondition holds, so someone practicing on inputs that satisfy it **never sees** the pattern's wrongness. What is measured here is the environment's mix: what percentage of the inputs satisfy the precondition, and how that ratio changes the number of wrong answers seen. Two selection policies are compared. - **AD26** — In the pool-based environment, **90 percent** of inputs satisfy the precondition; in the timed contest, **75 percent**; in the in-house assessment, **50 percent**. In the pool, problems are prepared according to the pattern; in the assessment, the input arrives as it is. - **AD27** — **Habitual selection** applies the most-practiced pattern to every problem and never tests the precondition. - **AD28** — **Precondition-checked selection** first checks whether the input is sorted; if it is not, it does not apply the pattern and falls back to the oracle. The check is at most $n-1$ steps and stops at the first out-of-order pair. - **AD29** — 40 problems are solved in each environment, and the target is 11. ```python """Two selection policies, against the oracle, across a mix of three environments.""" SEED, SECOND = 20260218, 20260219 def generator(seed): d = seed def next_value(n): nonlocal d d = (d * 1103515245 + 12345) % 2147483648 return d % n return next_value class Counter: def __init__(self): self.step = 0 def count(self, n=1): self.step += n def mix(sorted_ratio, seed=SEED, n=40, length=12): """sorted_ratio: what percentage of inputs satisfy the precondition.""" r = generator(seed) items = [] for _ in range(n): array = [r(30) - 9 for _ in range(length)] items.append(sorted(array) if r(100) < sorted_ratio else array) return items def oracle_pairs(array, target, s): for i in range(len(array)): for j in range(i + 1, len(array)): s.count() if array[i] + array[j] == target: return True return False def pattern_two_pointers(array, target, s): left, right = 0, len(array) - 1 while left < right: s.count() total = array[left] + array[right] if total == target: return True left, right = (left + 1, right) if total < target else (left, right - 1) return False def habitual_selection(array, target, s): """Applies the most-practiced pattern to every problem.""" return pattern_two_pointers(array, target, s) def precondition_checked_selection(array, target, s): """Tests the precondition first; falls back to the oracle if it does not hold.""" for i in range(len(array) - 1): s.count() if array[i] > array[i + 1]: return oracle_pairs(array, target, s) return pattern_two_pointers(array, target, s) def measure(policy, items, target=11): diverging, policy_steps, oracle_steps = 0, 0, 0 for array in items: s1, s2 = Counter(), Counter() a = policy(list(array), target, s1) b = oracle_pairs(list(array), target, s2) policy_steps, oracle_steps = policy_steps + s1.step, oracle_steps + s2.step if a != b: diverging += 1 return diverging, policy_steps, oracle_steps ENVIRONMENTS = [("pool-based practice ", 90), ("timed contest ", 75), ("in-house assessment ", 50)] for seed in (SEED, SECOND): print(f"seed {seed} , 40 problems per environment , target 11") print("environment sorted habitual precondition check oracle") print(" inputs diverging step diverging step step") for ad, ratio in ENVIRONMENTS: K = mix(ratio, seed) s = sum(1 for d in K if d == sorted(d)) a1, k1, h1 = measure(habitual_selection, K) a2, k2, _ = measure(precondition_checked_selection, K) print(f"{ad} {s:6d} {a1:7d} {k1:4d} {a2:7d} {k2:4d} {h1:4d}") print() ``` ``` seed 20260218 , 40 problems per environment , target 11 environment sorted habitual precondition check oracle inputs diverging step diverging step step pool-based practice 34 5 165 0 600 834 timed contest 29 8 199 0 681 914 in-house assessment 17 15 255 0 754 856 seed 20260219 , 40 problems per environment , target 11 environment sorted habitual precondition check oracle inputs diverging step diverging step step pool-based practice 36 2 213 0 609 1055 timed contest 31 4 238 0 691 1079 in-house assessment 22 10 296 0 823 1161 ``` Three numbers side by side. **Oracle:** 834 steps in the pool mix, correct on 40 of 40 inputs. **Pattern:** habitual selection 165 steps, precondition-checked selection 600 steps. **Diverging inputs:** habitual selection gives **5** in the pool, **8** in the contest, **15** in the assessment; the precondition check gives **0** in all three. The first reading concerns the environment. Same policy, same pattern, same problem count — yet the wrong answers it sees rise from 5 to 15, **three times over**. The cause is the environment's input mix: 34 of 40 pool inputs satisfy the precondition, against 17 in the assessment. Working with prepared inputs means seeing a pattern's wrongness less, and seeing it less is not the same as fixing it. The second reading concerns the policy. The precondition check gives **0 diverging inputs** in all three environments; the cost is rising from 165 to **600 steps** in the pool mix, that is, **3.64 times**. It still stays below the oracle's 834 steps: correctness is bought not at brute force's price, but at **72 percent** of it. The second corpus gives the same ranking (2, 4, 10) and the same 0 diverging inputs; the absolute numbers depend on the corpus, the ranking does not. What follows is repeated practice's progress metric, made of three numbers: **how many patterns were seen**, **the distribution's balance ratio**, and **how many were seen with their precondition broken**. Problems solved gives none of these three. ## Summary - Environments separate by type: in pool-based practice the practitioner chooses the distribution; in the timed contest and in-house assessment the environment chooses and the set is small. - The number of problems solved separates the environments by a factor of 12 (144, 30, 12), but the covered-pattern count is 5 in all three; neither metric shows progress. - The distinguishing metric is the distribution: in the pool the balance ratio is 0.2431 and the two dominant patterns cover 0.7986 of the problems; the timed contest gives 0.6667 with five times fewer problems. - Coverage rises to 5 in the second round and freezes; the balance ratio peaks at 0.2778 in the third round and then **declines** to 0.2431 — adding problems can make the metric worse. - The environment's input mix determines how much wrongness is seen: the same policy produces 5, 8, and 15 diverging inputs in the pool, contest, and assessment. - Precondition-checked selection gives 0 diverging inputs in all three environments; its cost rises from 165 to 600 steps, 72 percent of the oracle's 834. ## Course Wrap-Up Twenty-three lessons asked a single question: what does choosing a pattern mean accepting. Every lesson answered with three numbers. The **oracle** was always brute force and always correct — but **not always expensive**: the Longest Path Problem lesson measured the oracle at 562 steps against the pattern's 3626 on eight vertices, and showed the threshold sits at ten. The **pattern** usually spent fewer steps. **Diverging inputs** counted how many inputs the pattern answered differently than the oracle. The course's rule: a pattern's number is not the steps it saves, but **how many wrong answers it gives once its precondition breaks**. | Lesson | Oracle (steps) | Pattern (steps) | Diverging inputs / cost | |---|---|---|---| | Brute Force | exhaustive count **2640** | early exit 866 | early exit **0**; sampling **14** at 406 | | Divide and Conquer | **3120** | linear combine step **2680** | **0**; incomplete combine step **40/40** at 920 | | Greedy Algorithms | bottom-up | greedy | **827 of 969 systems** (0.8535); largest excess **16 coins** | | Dynamic Programming | **163,840** | full-key memoization **2440** (67.15 times fewer) | **0**; missing key **39/40**; with no overlap, 19 memo entries wasted | | Backtracking | without pruning **960,800** nodes, n=7 | with pruning **552** nodes | **1740.6 times**, ratio grows with n (72.3 → 8156.2); over-pruning gives 0 solutions | | Randomization | **780** | verified sampling **944–1056** | **0**; unverified, at 200, **40/40** once the precondition breaks | | Two Pointers | **972** | **154** (6.31 times fewer) | **25/40** unsorted, speedup drops to **2.33 times** | | Sliding Window | **2396** | **867** (2.76 times fewer) | **10/40** with negatives, in **fewer steps** | | Fast and Slow Pointer | **480** | **299** | **14/40** on the second edge case; steps **never change** | | Interval Merging | sorting by start: **40/40** correct | **2154** | **29/40** sorting by end, **40/40** by length and unsorted | | Cyclic Sort | 1..n, no duplicates | comparison-free | with duplicates, plain **40/40**; guarded **39/40**; missing case **0/40** | | Two Heaps | **480** median | with rebalancing step **1261** | unbalanced **295/480** wrong; rebalancing is **more than half** the pattern (1261/550) | | K-th Element | four k values x 40 inputs | k-sized heap | **0/40**; "k-th distinct value" is a separate question: **27/40** | | Grid Traversal | same connectivity **40/40** | connected component | **38/40** once the definitions diverge | | Knapsack | fractional variant **100,800** | greedy **174** | fractional **0/40**; the same order in 0/1 gives **5/40**, loss 7 | | Travelling Salesman | **352,800** (20 samples) | nearest neighbor **560** | **17/20**; average deviation 9.3, **worst 33.33**; two-opt 2/20 | | Longest Path | acyclic **40/40** | relaxation procedure | with a cycle **38/40**; largest overestimate **228** | | N Queens | with pruning **2057** nodes, n=8 | with symmetry breaking **1029** | ratio **2.00**, constant across five sizes; pruning's grows, symmetry's **does not** | | Knight's Tour and Maze | path model **90,111** | cell model **25** | ratio **3604**, diverging **0** | | Hamiltonian Paths | counting **29,270** | decision **1526** | ratio **19.18**; in every case with no path, decision = counting | | Problem Reading and Constraint | **866** | hash table **486**, sorting pattern **1398**, counting **396** | the wrong constraint reading diverges on **18 of 40** inputs (17 on the second corpus); at n=108 none of the three solutions fit the budget | | Solution Verification | brute force, **1596** across 52 inputs | correct two pointers **329** | 40 random inputs catch **4 of 5** defects, 12 edge cases catch **all 5**; against an oracle sharing the same defect, diverging drops from **3 to 0** | | Practice Environments | **834** | habitual selection **165**, precondition check **600** | **5** diverging in the pool, **8** in the contest, **15** in the assessment; precondition check gives 0 diverging but **3.64 times** the steps | The table's second reading matters more than its first: **speedup brings a pattern closer to being wrong, and sometimes it does not even speed things up.** Two pointers' speedup drops to 2.33 times on an unsorted input while it is wrong on 25 inputs; greedy over-answers on 827 of 969 systems; memoization wastes 19 entries with no overlap. None of this was hidden: not knowing when a pattern goes wrong means not knowing when to choose it. The third and lasting result concerns the oracle itself: **brute force is not a baseline, it is an oracle.** Every number in the course was written because of it. In the final lesson this became a habit: counting correctness against a second solution's answer, not an opinion. The next course, **Theory of Computation**, takes up the question left in the oracle's shadow. The traveling salesman and Hamiltonian paths lessons explicitly deferred "why is this problem hard." What will be asked there is whether not knowing anything better than brute force is, for some problems, a fact about our knowledge or about the problems themselves. The answer comes through decidability, reduction, and complexity classes.