 # ZIO19003 - Editorial

Editorialist: Aryan Agarwala

Problem link: ZIO 2019 Problem 3

Explanation:

This problem can be solved simply by constructing a table of size N x 2. Let the content in the ith row and jth column be represented by DP[i][j]. In this table, let DP[i] represent the number of selections where you only select from P_1, P_2, …, P_i, and P_i is definitely selected, but P_1 is definitely not selected… Let DP[i] represent the number of selections where you only select from P_1, P_2, …, P_i, and P_i is definitely selected, and P_1 is also definitely selected.

DP = 0, DP = 1

DP = 1, DP = 0

DP[i]=∑j=1i-2DP[j]+1 ( j represents the previous person before i that you are selecting. And the extra +1 is for the selection where you select only P_i )

DP[i]=∑j=1i-2DP[j] ( j represents the previous person before i that you are selecting. There is no 4+1\$ in this case, because we know that P_1 should also be selected at the least. )

This is because you cannot have a selection including the last person and the first person (since they are adjacent).

The method demonstrated on the first subtask of problem 3:

1 2
1 0 1
2 1 0
3 1 1
4 2 1
5 3 2
6 5 3
7 8 5
8 13 8
9 21 13
10 34 21
11 55 34