INOI1301 - Editorial

editorial
, ,
1

Problem link - Calvins Game

Problem Statement

Calvin wakes up early one morning and decides to play a game by drawing a sequence of N squares, numbered 1 to N, with an integer in each square. He starts at square k (1 ≤ k ≤ N). The game consists of two phases: a forward phase followed by a backward phase.

  • Forward Phase: Starting from square k, Calvin can move to either p+1 or p+2, as long as he stays within the N squares.

  • Backward Phase: Once the forward phase is over, Calvin can move backwards to square 1, either to p-1 or p-2.

Calvin wants to end up at square 1 and maximize his score. The score is calculated based on the integers on the squares he jumps to (the square where he starts is not counted).

The goal is to determine the maximum score Calvin can achieve, starting at square k and ending at square 1.

Approach

The idea behind the code is to split Calvin’s journey into two phases: the forward and backward phases.

  1. Forward Phase (P Array): Calculate the maximum score Calvin can achieve moving forward from square 1 to N. For each square, compute the best score by jumping from either p-1 or p-2.

  2. Backward Phase (Q Array): Calculate the maximum score moving backward from square k to 1. Initialize Q[k] and compute the backward score by jumping to either p-1 or p-2.

  3. Maximization: Combine both phases by calculating P[i] - A[i] + Q[i] to get the best score, excluding the initial score at square k.

Time Complexity

O(N) — The code involves two loops, each running through the N squares.

Space Complexity

O(N) — Two arrays (P and Q) of size N are used.