Maksim1744's blog

By Maksim1744, 3 years 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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C could you elaborate the last part of editorial

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

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

How do we do B using Binary search?

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

    You create an array with the sum of prefixes from $$$1$$$ to $$$n$$$. Since the value of $$$a_i$$$ is always greater than $$$0$$$, the array of the sum of prefixes is always increasing.

    Given that, for each position $$$i$$$ you can ask with binary search what is the maximum $$$j$$$ that the sum of the interval [i, j] is less than t.

    Here I have my code that solves it with that logic: https://mirror.codeforces.com/contest/279/submission/208379855

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

      Got it! Thanks so much, you're a godsend

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

Can we solve B with out Binary Search???

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

this problem give me time limit in test 9 but the time in worst case is 1e10 + 1e5 why it give my that please any one help me

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

l mean problem b

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

How C could be solved by Dynamic Programming?

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

hey i have a doubt ...

int n,t; cin >> n >> t;

vector<int> vec(n);

vector<int> v(n+1,0);
for(int i = 0 ;i<n;i++)cin >> vec[i];
for(int i = 1; i<n+1;i++) v[i] = v[i-1]+vec[i-1];
// for(int i = 0 ;i<n+1;i++)cout << v[i] << endl;
int i =  0;
int j = n;
int flag = 0 ;
while(i<j)
{
    if(v[j]-v[i] <= t)
    {
        flag = 1;
        cout << j-i << endl;
        break;
    }else
    {
       if(vec[i]>vec[j-1])
       {
            i++;
       }else
       {
            j--;
       } 
    }


}

if(flag == 0) cout << 0 << endl;

why is the above code not working for question B can anyone help !!