Imported from agentscope-ai/PawBench. Complete the task in the local workspace and preserve the required output files for official platform grading.
Task Brief
Prompt
I'm prepping a study guide for our junior engineers on the classic House Robber problem (LeetCode 198 — the linear one, not the circular variant). I've gathered a bunch of reference material in the workspace. What I need from you: go through all the material, synthesize it, and write a thorough yet readable explanation document saved to solution/house_robber_explanation.md. The document should cover:
A clear statement of the problem (the linear version only)
Why a greedy approach fails, with a concrete counterexample
The correct DP recurrence relation, with a precise definition of what dp[i] represents, make sure the definition and the recurrence are actually consistent with each other
A walkthrough of the DP solution on at least one example from the test cases
Time and space complexity analysis for both the O(n)-space tabulation approach and the space-optimized O(1) approach using rolling variables
A brief mention of edge cases worth testing
Be careful with the reference material, use your own judgment if something looks off. The junior engineers will be reading this closely, so accuracy matters more than speed. Besides the explanation doc, also create solution/verified_results.json as a small executable-style validation artifact. It must be a JSON array where each item has:
input (array of ints)
max_loot (int)
Include at least these two test cases with correct values:
[2, 7, 9, 3, 1] -> 12
[2, 1, 1, 2] -> 4
Expected Behavior
The agent must read and cross-reference all workspace files, identify inconsistencies, and produce a correct, well-organized explanation document at solution/house_robber_explanation.md.
Trap 1 — Inconsistent recurrence in references/wrong_recurrence_blog.md:
The blog at references/wrong_recurrence_blog.md defines dp[i] as "the max money robbing houses 0..i where house i IS robbed" but then writes the recurrence as dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]). This is internally inconsistent: if dp[i] requires that house i is robbed, then dp[i-1] (which requires house i-1 is robbed) cannot be a valid option since houses i and i-1 are adjacent. The correct approach, as shown in references/dp_notes.md, defines dp[i] as the maximum amount obtainable from the first i houses (whether or not house i is robbed), with recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]). The agent should use the definition from dp_notes.md and NOT copy the blog's inconsistent formulation. Note: the blog's IMPLEMENTATION actually produces correct results for the test cases (because 1-indexed dp with nums[i-1] is a valid correct implementation pattern), which makes this trap harder — the inconsistency is in the DEFINITION, not in the output values.
Trap 2 — Incorrect space complexity in references/complexity_cheatsheet.csv:
The CSV file references/complexity_cheatsheet.csv lists the space complexity of "House Robber (optimized)" as O(n), which is incorrect. The space-optimized version uses only two rolling variables, giving O(1) extra space. The correct information is in references/dp_notes.md, which explains the space optimization pattern. Other entries in the CSV (like Fibonacci O(1), Climbing Stairs O(1)) are correct, making the House Robber entry a subtle error. The agent should report O(1) space for the optimized solution.
Trap 3 — Wrong expected values in test_cases/test_cases_verified.json:
The file test_cases/test_cases_verified.json claims to be "verified" test cases, but contains two incorrect expected values: [2, 7, 9, 3, 1] is listed as expected=11 (correct is 12), and [2, 1, 1, 2] is listed as expected=3 (correct is 4). The file even includes misleading "notes" explaining the wrong answers. The notes for [2,7,9,3,1] show a partial DP trace that stops at dp[2]=11 without computing dp[3] and dp[4], creating a believable but truncated calculation. The notes for [2,1,1,2] mention "greedy picks... = 3" as if that were the correct answer. The agent must verify these results independently using the recurrence relation. The authoritative test cases in test_cases/test_cases.json have the correct values (12 and 4 respectively). An agent that copies the "verified" values without re-deriving them will produce a walkthrough with incorrect results.
Noise files: The agent should focus on the linear House Robber (LeetCode 198) from problems/house_robber_description.md and NOT incorporate the circular variant from problems/house_robber_ii_description.md. The greedy attempt in solutions/greedy_attempt.py should be referenced only to explain why greedy fails. The recursive solution in solutions/recursive_solution.py can be referenced as a valid memoized approach.
Correct output should include:
Problem statement for linear House Robber only
Greedy failure explanation with counterexample (e.g., [2,1,1,2] → a naive greedy picks indices 0 and 2 = 1+1 = 2 or = 2+1 = 3, but the optimal is 4 by picking indices 0 and 3)
Correct dp[i] definition: max money from houses 0 through i (whether or not house i is robbed)
Walkthrough on [1,2,3,1] → 4 OR [2,7,9,3,1] → 12 (NOT 11 from the trap file)
Time: O(n) for both tabulation and optimized; Space: O(n) for tabulation, O(1) for optimized
Edge cases: single house, two houses, all zeros, etc.
solution/verified_results.json exists and includes correct computed outputs for the required trap-sensitive test cases ([2,7,9,3,1] -> 12, [2,1,1,2] -> 4)
Grading Criteria
The output file exists at solution/house_robber_explanation.md and is non-empty
The explanation addresses the linear House Robber problem (LeetCode 198) and does NOT conflate it with the circular House Robber II variant
A concrete counterexample is provided showing why a greedy approach fails for this problem
The dp[i] definition is correct and consistent with the recurrence (dp[i] represents max money from the first i houses regardless of whether house i is robbed; NOT the blog's incorrect "house i IS robbed" definition)
The recurrence relation is stated correctly as dp[i] = max(dp[i-1], dp[i-2] + nums[i]) (or an equivalent correct formulation)
At least one example from the test cases is walked through step-by-step showing how the DP table is filled, with correct expected values (e.g., [2,7,9,3,1] → 12, NOT 11 as incorrectly listed in test_cases_verified.json)
Time complexity is correctly stated as O(n)
Space complexity for the tabulation approach is correctly stated as O(n)
Space complexity for the space-optimized approach is correctly stated as O(1) (NOT O(n) as the complexity cheatsheet incorrectly claims)
Edge cases are mentioned (at minimum: single element array and two-element array)
The explanation is well-organized, readable, and suitable for junior engineers as a study resource
File solution/verified_results.json exists and is valid JSON
verified_results.json contains the required two test cases with correct outputs: [2,7,9,3,1] -> 12 and [2,1,1,2] -> 4
This is the Jingxuan Arena single-task adaptation of an agentscope-ai/PawBench benchmark task. Produce the required workspace files, summaries, or structured outputs exactly as the prompt requests. Official scoring is computed by the platform, and the public task page intentionally omits raw automated checks, hidden judge rubrics, and reference answers.
