its_time_to_grow's blog

Problem in old CF problem
By its_time_to_grow, history, 21 month(s) ago, In English

I have a doubt in https://mirror.codeforces.com/contest/713/problem/C If I will modify problem that array should be increasing, not necessarily strictly increasing, then how can we solve this problem.

Any help will be appreciated.

Any other solution for my problem statement is also welcome.

Tags dp
  • Vote: I like it
  • -12
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
21 month(s) ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

Please help

→ Reply
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

how do you expect me to help you with a 2300 rated problem?

→ Reply
»
21 month(s) ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

If $$$a_1 \lt a_2 \lt \dots \lt a_n$$$ then you can replace $$$a_i$$$ with $$$a_i-i$$$ and you have $$$a_1-1\le a_2-2\le \dots\le a_n-n$$$. It's true since $$$a_i-i\le a_{i+1}-(i+1)$$$ means $$$a_i\le a_{i+1}-1$$$ what is the same as $$$a_i \lt a_{i+1}$$$.

The problem you are talking about is this one. The solution is the same but on the modified array.

→ Reply