123gjweq2's blog

By 123gjweq2, history, 6 months ago, In English

Hello. I can't seem to figure out this problem's solution. I've read the editorial and I understand the first part but when the author says:

"To further optimize this solution, another transformation is needed. Ideally, we would like each ai to contribute to the answer independently of other values. And this can almost be achieved. Notice that the maximum returns 0 only if ai<ai−1 for any k, not just for k=1. This may require proof, but it is quite obvious."

I just don't get what this means. I also don't know what he's tryna do with the ci coefficient. I'd really appreciate it if someone here could explain it to me.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In second option (last paragraph of editorial) $$$c_i$$$ is similar to what I did in my solution: https://codeforces.me/blog/entry/128421?#comment-1140048 but from slightly different angle.

»
6 months ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

After much deliberation, I finally figured it out. I learned a lot too. I am going to write down what I have learned so that I can reference it if I ever need to. Maybe someone else might find it helpful too.

explanation
$O(n \cdot \sqrt A)$ submission
$O(n + A\cdot\log A)$ solution
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    OMG, cp is hard, i'm giving up

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Wow, thanks for reminding me about this comment. I just figured out how to use latex so imma prettify it.

      edit: well... I tried my best. At least now I know why authors only use 1 letter to name arrays.