CustomCC0-1.0#cp0161500

Minimal Jumps to Reach Zero

Summary

•Phase 4 / bfs, array, shortest path
•Reasoning-first competitive programming drill

Problem Description

Given an array A of n positive integers, you start at index 0. In one step, you can jump from position i to i+

A_{i}

or to i-

A_{i}

, if inside array bounds. Find the minimal number of steps to reach index n-1. How to read this problem in plain language: - This is a Phase 4 reasoning drill focused on bfs, array, shortest path. - Typical lenses to test first: bfs, array, shortest path. - Constraints reminder: 1 ≤

n \leq 1 e 5;

1 ≤

A_{i} \leq n

Mini examples for mental simulation: 1) Boundary example: Describe why this case is tricky. Explain expected behavior and why naive logic may fail. 2) Adversarial example: Adversarial case where naive greedy/local decision looks correct but fails globally. 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 \leq 1 e 5;$ 1 ≤ $A_{i} \leq n$

Analysis

Key Insight

Use this hint to refine your reasoning. This step should reduce search space or formalize correctness. State why this insight changes your algorithm choice.

bfsarrayshortest path