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

1 Like

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 @anon38711361

2 Likes

Big Note for those guys who couldn’t find a general expression for n

Okay, this might not be a surprise but the answer for n \geq 3 is F_{n+1} + F_{n-1} - 1
where F_{n}, is the n'th fibonacci number
One can check this answer.
If this is found to be wrong… well sorry
But if it is not !! then I will post my solution

2 Likes

Nice recurrence…seems correct !

My approach :

Thanks :slight_smile:

6 Likes

Allow me to show an alternative method…
The idea is beautiful so stick around!

First let G(n) be the value we wish to compute but with the possibility that we don’t choose anything. Define f_n to be the n^{\text{th}} fibonacci number.(f(1) = 1, f(2) = 1)
Now we define a new number called F(n) which refers to the number of ways we can choose objects placed in a line such that no two are adjacent(again including the possibility that nothing is chosen).
Now we derive a dp on F.
Consider F(n) for n \ge 2. Either we choose the last element or we don’t. If we do we can’t take the 2nd last element and so this number is F(n - 2).When we don’t take the last element it just corresponds to the case F(n - 1).
So we have the recursion:
F(n) = F(n - 1)+ F(n - 2)
Now we can easily see that F(1) = 2 and F(2) = 3. Thus F is really just the fibonacci sequence displaced by 2 !
Hence F(n) = f_{n + 2}.
Now onto relating G with F
Note that G is a circular based problem whereas F is a line based problem.
So we break the circle and continue. Consider G(n) for n \geq 4.
Pick any random element X of the circular arrangement. Either we take this or we don’t. If we don’t then the circle has broken and the number of ways is F(n -1). If we do take this element then we can’t take the 2 elements adjacent to it anymore so the value is just F(n-3).
So in all we now have:
G(n) = F(n-1) + F(n - 3) = f_{n+1} + f_{n - 1}.
However G(n) is not exactly what we want. We still need to erase the possibility that we don’t take anything.So our answer to the problem is just f_{n + 1} + f_{n - 1} - 1 for n \ge 4(actually for n = 3 this is correct too, but you have to check and add)
Hope this proof helps… :wink::slight_smile:

2 Likes