levi.ackerman1732's blog

Looking for flaw in my solution for Round #605(Div. 3D)
By levi.ackerman1732, history, 4 years ago, In English

Problem: 1272D - Remove One Element

My Solution:108781615

Hello all,

My idea: if two elements are in strictly increasing order(i.e a[I] < a[I+1] ) dp[I+1] = dp[I] + 1

else check if a[I-1] < a[I+1] then dp[I+1] = dp[I-1] + 1

I am not sure where this is going wrong. Any help is appreciated. Thanks for your time.

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You should also save another state to indicate whether you have already used up your ability to delete an element or not. Something like:

$$$dp[i+1][b]=dp[i][b]+1$$$, for $$$b\in \{0,1\}$$$, if $$$a[i]<a[i+1]$$$

$$$dp[i+1][1]=dp[i-1][0]+1$$$, if $$$a[i-1]<a[i+1]$$$

return $$$max(dp[n][0],dp[n][1])$$$

→ Reply