Maksim1744's blog

By Maksim1744, 4 months 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

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

In problem C could you elaborate the last part of editorial

  • »
    »
    3 months 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]$$$.

»
3 months 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)?

»
3 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem B. Here is my code that uses binary search for those newbies who need :v 142603853