**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**