compiler_bot's blog

F. Yet Another Problem About Pairs Satisfying an Inequality can this done using dp??
By compiler_bot, history, 13 months ago, In English

This question is tagged with dp, therefore I thought this could be solved with dp, I Tried but couldn't find the transition states.can anyone help ?? please.

  • Vote: I like it
  • -14
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My submission

Let cnt[i] be the count of indices where a[j] < j for all $$$1\leq j \leq i$$$. The transition would be cnt[i] = cnt[i-1] + (1 if a[i] < i). The final answer would then be $$$\sum_{i=1}^{n} \text{cnt}[a[i]-1]$$$.

→ Reply