its_time_to_grow's blog

Problem in old CF problem
By its_time_to_grow, history, 3 months ago, In English

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.

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

»
3 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Please help

→ Reply
»
3 months ago, # |
  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
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply