Libraion's blog

By Libraion, history, 3 years ago, In English

Given an array of $$$N$$$ $$$(1 \le N \le 10^5)$$$ elements $$$A_1,A_2,\dots,A_N$$$ $$$(1 \le A_i \le 10^6)$$$. You can replace $$$2$$$ consecutive elements with their sum. Find the minimum number of replacements such that the resulting array is non-decreasing.

As you can easily see, it is the same as split $$$A$$$ into maximum number of segments such that their sums from left to right is non-decreasing.

Thanks.

  • Vote: I like it
  • +61
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +97 Vote: I do not like it

Words are not enough to describe the distress that this problem has caused me. I suffered more anxiety while trying this problem than I have felt in my entire life up to this point. I felt more depressed after each WA than I felt during some of the funerals of some people close to me. This problem has been very important in changing my perception of the world, as I now understand the true depths of despair.

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I think this task is almost the same. My spoilers are for the linked problem.

Spoiler 1
Spoiler 2
»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it