Блог пользователя Maksim1744

Автор Maksim1744, 3 года назад, По-английски

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
Разбор задач Codeforces Round 171 (Div. 2)
  • Проголосовать: нравится
  • +111
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In problem C could you elaborate the last part of editorial

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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]$$$.

»
10 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How do we do B using Binary search?

  • »
    »
    10 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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://codeforces.com/contest/279/submission/208379855

»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can we solve B with out Binary Search???

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

l mean problem b

»
7 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How C could be solved by Dynamic Programming?

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 !!