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][1] 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][2] 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[1][1] = 0, DP[1][2] = 1

DP[2][1] = 1, DP[2][2] = 0

DP[i][1]=∑j=1i-2DP[j][1]+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][2]=∑j=1i-2DP[j][2] ( 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. )

The final answer is ∑i=1N(DP[i][1]+DP[i][2])-DP[N][2]

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

The final answer is 198

What made you think we need two dp ?

You have already solved it and you know how to do , but when we noobs see it , why are you using two dps ? why doesn’t it work ? where does it fail ?

Need better explanation and more easy @aggu_01000101