Maksim1744's blog

By Maksim1744, 5 weeks ago, In English

Continuing with the theme of absent editorials for old rounds, here is an editorial for Codeforces Round #171 (Div. 2). Even though there is an official editorial, it is only in russian and doesn't have solution for the last problem.

A

Editorial
Code

B

Editorial
Code

C

Editorial
Code

D

Editorial
Code

E

Editorial
Code
 
 
 
 
  • Vote: I like it
  • +111
  • Vote: I do not like it

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C could you elaborate the last part of editorial

  • »
    »
    8 days ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Let's look at $$$tol[i]$$$. If $$$a[i - 1] < a[i]$$$, then $$$tol[i] = i$$$, otherwise $$$a[i - 1] \geqslant a[i]$$$ and we can continue longest nonincreasing sequence which ends in $$$a[i - 1]$$$ by adding $$$a[i]$$$, so $$$tol[i] = tol[i - 1]$$$.

»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the optimal time complexity of problem B O(n^2) or O(nlogn)?