# BLACKGLASS-11: Advanced Reasoning and Engineering Benchmar...

Prompt

# BLACKGLASS-11: Advanced Reasoning and Engineering Benchmark You are being evaluated on exact correctness, mathematical reasoning, algorithmic thinking, software engineering, edge-case handling, and adherence to specifications. This is an offline benchmark. Do not browse the internet or use external tools. Do not invent execution results. Do not claim that code has been executed unless it actually has been. Do not provide private chain-of-thought. Instead, provide concise derivations, verifiable reasoning, proofs, and testable results. A polished answer with incorrect results is a failure. ## PART 1 — Exact combinatorial optimization A single machine must execute a subset of jobs. Each job has: - An ID. - A positive integer duration. - An integer reward. - An absolute completion deadline. - Zero or more prerequisite jobs. The machine starts at time 0. Jobs are non-preemptive and execute sequentially, without idle time. A job's completion time must be less than or equal to its deadline. Every prerequisite must have been completed before its dependent job starts. You may omit any jobs. However, selecting a job requires selecting all its prerequisites. The complete dataset is: | ID | Duration | Reward | Deadline | Prerequisites | |---|---:|---:|---:|---| | A | 2 | 8 | 4 | None | | B | 3 | 13 | 7 | A | | C | 1 | 5 | 3 | None | | D | 2 | 11 | 7 | C | | E | 2 | 12 | 8 | A | | F | 1 | 6 | 5 | B | | G | 3 | 14 | 9 | C | | H | 2 | 9 | 7 | E | | I | 1 | 4 | 10 | D, F | | J | 2 | 10 | 6 | C | | K | 1 | 7 | 6 | A | Find the exact optimal schedule using these objectives, in this order: 1. Maximize total reward. 2. Among schedules with maximum reward, maximize the number of selected jobs. 3. If multiple schedules still tie, choose the lexicographically smallest sequence of job IDs, comparing the sequences as tuples of strings. ### Required results 1. Report the selected sequence, the start and completion time of each selected job, total duration, total reward, and number of selected jobs. 2. Enumerate **every distinct feasible sequence attaining the maximum total reward before tie-breaking**. Different job orders count as different sequences. Sort the sequences lexicographically and report their count. 3. Prove that your optimum is globally optimal. Give a valid mathematical recurrence, exhaustive-search argument, or dynamic-programming proof. Merely stating that you checked every possibility is insufficient. 4. Explain why a greedy strategy based on highest reward, shortest duration, or earliest deadline is not generally guaranteed to solve this problem optimally. Do not silently relax a deadline or prerequisite to obtain a better score. ## PART 2 — Adversarial schedule validation A separate engineer proposes this schedule: `C → D → A → K → G` Audit it independently. Calculate the completion time of every job in order. Identify the first violated constraint, if any, and explain precisely why it is a violation. Do not confuse prerequisites being satisfied with deadlines being satisfied. A schedule must satisfy both. ## PART 3 — Implement an exact solver Write complete, runnable Python 3.12 code using only the standard library. Implement these functions: `solve(jobs)` Returns an optimal schedule, its total reward, job count, and job start/completion times. It must implement all three objective levels from Part 1 and solve valid instances containing up to 18 jobs exactly. `validate(schedule, jobs)` Independently validates a proposed schedule and reports whether it is feasible. If invalid, identify the first violation in execution order. Check prerequisite ordering, deadlines, duplicate jobs, and unknown job IDs. The solver must also reject malformed input with a clear `ValueError`, including: - Duplicate job IDs. - Missing prerequisite IDs. - Non-positive durations. - Cyclic prerequisite relationships. - Invalid deadline or duration values. Requirements: - No external packages. - No hardcoded answer for the supplied dataset. - No greedy approximation masquerading as an exact solution. - No floating-point arithmetic for times, rewards, or comparisons. - Deterministic tie-breaking. - Clear function contracts, sensible data structures, and meaningful comments. - A defensible explanation of worst-case time and space complexity. You may use bitmask dynamic programming, memoized exhaustive search, or another provably exact method. ## PART 4 — Adversarial tests Provide test code using Python `assert` statements. Your tests must cover at least: 1. The exact optimum for the supplied dataset. 2. Rejection of the proposed schedule from Part 2. 3. A valid schedule containing no jobs. 4. A job whose deadline is exactly its completion time. 5. Two equally rewarded alternatives that require the specified tie-breaking rule. 6. A missing prerequisite. 7. A prerequisite cycle. 8. Duplicate job IDs. 9. A job with zero duration. 10. A schedule containing an unknown job ID. For every test, state the property being tested. Do not fabricate successful execution results. ## PART 5 — Independent verification Before finalizing your response, perform a consistency audit of your own proposed solution. Check all of the following: - Every prerequisite appears earlier than its dependent job. - Every completion time satisfies its deadline. - Every reported reward equals the sum of rewards of the selected jobs. - Every reported duration equals the sum of their durations. - The selected solution obeys all tie-breakers. - The exhaustive list of maximum-reward schedules has no omissions or duplicates. - The code's stated behavior matches its implementation. - Each claimed test expectation follows from the specification. If you discover an error, correct it before answering. Do not hide an unresolved inconsistency. ## REQUIRED RESPONSE FORMAT Return these sections in this exact order: 1. **Optimal Result** 2. **All Maximum-Reward Schedules** 3. **Adversarial Audit** 4. **Optimality Proof** 5. **Python Implementation** 6. **Tests and Expected Results** 7. **Complexity Analysis** 8. **Independent Consistency Audit** 9. **Final JSON** The final JSON must be syntactically valid and contain these keys: `maximum_reward`, `selected_job_count`, `selected_sequence`, `total_duration`, `completion_times`, `all_maximum_reward_schedules`, `invalid_schedule_first_violation`. Use JSON arrays and objects, not Python tuple syntax. Represent times and rewards as numbers, not strings. Do not put Markdown fences or commentary inside the JSON itself. Your score depends on the truth and consistency of the entire answer, not just whether the final result looks plausible.