Блог пользователя its_time_to_grow

Problem in old CF problem
Автор its_time_to_grow, история, 21 месяц назад, По-английски

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.

Теги dp
  • Проголосовать: нравится
  • -12
  • Проголосовать: не нравится

»
21 месяц назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

Please help

→ Ответить
»
21 месяц назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
21 месяц назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить