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

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

I have a doubt in https://codeforces.net/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
  • Проголосовать: не нравится

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

Please help

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

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

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

    Dont go on ratings. Its much simpler than 2300. Also the version I am asking is simpler than this (I think so).

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

      ok, well I would say that you better keep trying to understand that(yourself). It really helped my. How to do it?: just take time(10 minutes maybe) if can't just leave it for the future days :). Also it is important logic to actually understand the stuff you think are impossible, sometimes you need to re-read the statements 10 times, but still you need to do it and finally will understand everything.

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

If $$$a_1<a_2<\dots<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< a_{i+1}$$$.

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

→ Ответить