CustomCC0-1.0#ct-p2-041680
Median Feasibility Subarray
Summary
- •Phase 2 / binary-search-answer
- •Reasoning-first competitive programming drill
Problem Description
Find maximum median among all subarrays of length at least k. Your submission must justify algorithm choice, prove correctness, and test adversarial edge cases.
How to read this problem in plain language:
- This is a Phase 2 reasoning drill focused on binary-search-answer.
- Typical lenses to test first: binary-search, prefix-sum, monotonicity.
- Constraints reminder: 1 <= n <= 2e5
Mini examples for mental simulation:
1) Boundary example: Answer equals max element. Explain expected behavior and why naive logic may fail.
2) Adversarial example: Binary search boundaries collapse correctly.
Lite-mode writing target:
- Write 1~2 observations that shrink the search space.
- Name one final algorithm and state target complexity explicitly.
- Validate with at least 2 edge cases and one hand simulation.
Constraints
- •1 <= n <= 2e5
Analysis
Key Insight
Check O(n), binary search value domain. This step should reduce search space or formalize correctness. State why this insight changes your algorithm choice.
binary-searchprefix-summonotonicity