How should I practice Constrained Jump Sequences?

Start by reading the full statement, solve the visible examples, then compare the pattern against related PhonePe online assessment problems in FastPrep.

Is Constrained Jump Sequences associated with PhonePe?

FastPrep tags this as a PhonePe online assessment coding practice problem when the problem catalog has that company and stage context.

Problem · Dynamic Programming

Constrained Jump Sequences

Learn this problem

● Hard

PhonePeFULLTIMEOA

Problem statement

There are n locations on a straight line, numbered from 1 through n. You begin at start, and a fixed spotlight is at spotlight.

Make exactly jumps consecutive jumps. For every jump from the current location x to the next location y, both rules must hold:

x != y.
|x - y| < |x - spotlight|.

Return the number of valid jump sequences modulo 10^9 + 7.

Function

countJumpSequences(n: int, start: int, spotlight: int, jumps: int) → int

Examples

Example 1

n = 5start = 2spotlight = 4jumps = 1return = 2

From location 2, the current distance to the spotlight is 2. The legal destinations are 1 and 3.

Example 2

n = 5start = 2spotlight = 4jumps = 2return = 2

The first jump can reach 1 or 3. Location 3 has no legal next destination, while location 1 can jump to 2 or 3. Therefore there are two sequences.

Example 3

n = 6start = 5spotlight = 3jumps = 2return = 2

The only valid two-jump sequences are 5 -> 6 -> 4 and 5 -> 6 -> 5.

Constraints

2 <= n <= 2000
1 <= start, spotlight <= n
1 <= jumps <= 2000