MCO16303 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Zi Song Yeoh

DIFFICULTY:

EASY

PREREQUISITES:

DYNAMIC PROGRAMMING

PROBLEM:

You start from 0. Each step you can choose to go right by a_{i} or left by a_{i}. What is the number of awys to end in [l, r]?

EXPLANATION:

Subtask 1 can be solved in O(2^{n} \cdot n) by trying all possible ways to perform the moves.

To solve subtask 2, we let dp[i][j] denote the number of ways to end in number j after the i-th move. Now, the transition is dp[i][j] = dp[i][j+a[i]] + dp[i][j-a[i]].

This solution works in O(n \cdot Sum of a_{i}) time.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Tester’s solution can be found here.

RELATED PROBLEMS:

1 Like
//