Help me out in this

#1

https://cses.fi/problemset/task/1746

#2

@aa1 are u there kindly read the question?

#3

yeah , what is your doubt in this question

#4

@aa1 how to approach this problem recursively?

#5

you should try forming a dp matrix denoting number of ways to fill the array up to index i,if x[i] = v.

#6

@aa1 can you explain me in detail?

#7

If x[i] = 0, we can replace it by any value.
However, if we replace it by v, the previous value must be either v-1, v or v+1. so i can sya that the number of ways to fill the array up to i, is the sum of the previous value being v-1, v and v+1.

all the arrays that are valid. X - 1, x or x + 1 at the last index or at the n minus 1. then all these arrays can be extended to form a valid array of size n where x is the last element. So with this intuition, you should try forming a dp state.

We treat i = 0 separately.
1. Either x[0] = 0, so we can replace it by anything (i.e dp[0][v] = 1 for all v).
2. Otherwise x[0] = v ≠≠ 0, so that dp[0][v] = 1 is the only allowed value.

for i>0
If x[i] = v from the input, only dp[i][v] is allowed (i.e dp[i][j] = 0 if j ≠≠ v).
Still dp[i][v] = dp[i-1][v-1] + dp[i-1][v] + dp[i-1][v+1].

The complexity is O(n⋅m)O(n⋅m) with worst-case when x is all zeros.

#8

@aa1 can you tell me how to approach this recursively?

#9

i think for recursion u ll have to make 2 similar loops for i to n and j to m and you ll have to start from the second element and check both the prev and next occurring value to keep a count .we ll again keep the first location separate. but this wont pass the time limit . it ll be too complex as far as i can form the logic
still try to go through this article too : https://stackoverflow.com/questions/56722977/number-of-possible-arrays-such-that-adjacent-elements-have-difference-atmost-1