Вау, да это самый быстрый разбор на свете! :)

Thanks Sereja
What a speedy tutorial!
I wonder how fast are you!

This is so obviously Google Translated. Look at the first sentence of div1 A: "100000 numbers" is translated as "number 100000". Nobody who knows English at least a little bit would reverse the order of words like that.

Needless to say, I really don't understand the solutions from it. At least I know a bit of Russian :D

в 380C: a = a1 + a2 + t

наверное имелось ввиду: a = a1 + a2 + 2*t?

А можно поподробней 380D - Сережа и кинотеатр?

:o Really weird that I missed that particular solution to C, I like such tricks with segment trees. But fortunately I came up with another solution. Let's calculate two arrays sum_pref_all, sum_pref_end. In order to calculate first, change ( to 1 and ) to -1 and calculate prefixes' sums. In order to calculate second change ( to 0 and ) to 1 and calculate prefixes' sums. Answer is 2 * (sum_pref_end[r] — sum_pref_end[l — 1] — sum_pref_all[l — 1] + c) where c is equal to min(sum_pref_all[l — 1], sum_pref_all[l], ..., sum_pref_all[r]. First part sum_pref_end[r] — sum_pref_end[l — 1] is a number of all ')' in this subword and sum_pref_all[l — 1] — c is a number of ')' which can't find their corresponding '('. In order to retrieve c of course build a segment tree.

UPD: I have updated this post, since I messed up sum_pref_all and sum_pref_end in few places.

Is this a tutorial ?

Поправь формулу в разборе Е, там V * p[i] внутри скобок.

По понятнее разбор задачи 380А, пожалуйста.

For problem C,

In the contest, I also used a stack to match the paranthesis first, but then I chose an O(nsqrtn) approach (how stupid) which ultimately got me a TLE. QAQ.

I don't understood DIV2-D problem.Can it be solved with DP?

I know that it has been said already, but it's almost impossible to read this kind of tutorials in English (I mean when it's google translated). I would volunteer to translate the solutions from Russian to English, shouldn't take that much time and effort :)

I really cannot understand Sereja's D1-C solution at all. Could someone explain it? What are really stored in each of the segment tree nodes?

Задача с префиксами. "Иначе посмотрим, какому элементу будет соотвествовать наш" — как это понимать? Ведь это спуск за O(m) — не пройдёт по времени. UPDПонял.

Объясните задачу Div.1 C, пожалуйста. Я вообще не понял разбор.

В задаче С я почему-то подумал, что нужно найти самую длинную подстроку, а не подпоследовательность. Ничего не придумал. А есть ли решение такой задачи за разумное время?

380C — Sereja and Brackets I think a = a1 + a2 + t

should be a = a1 + a2 + 2*t

In the problem C: 380C — Sereja and Brackets,

It should be a = a1 + a2 + (2)*t instead of a = a1 + a2 + t

I have seen some DP solutions for problem C Sereja and Brackets. Can anyone explain how a DP solution would work?

PS: BTW, the tutorial quality is very poor (at least the English version).

380A — Sereja and Prefixes

why can the kth of element, kth can be fit in 64-bit integer ?

Can the problem Sereja and Brackets be converted into an equal problem of : Given a set or intervals and queries (of type l_i and r_i), find the number of intervals within that range ?

I know this is very old, but it may help someone that's studying: on problem Sereja and Brackets there is a way easier solution. The key observation here is that the closing bracket will be chosen greedly, that is, the last opened bracket can be closed with the first available bracket everytime, yelding the optimal bracket matching for any query. That observation being made, the problems is reduced to counting the matchings inside the interval of the query. I did this by first storing the right side of each query in it's corresponding position and then sweeping the string from left to right, keeping a Fenwick Tree (BIT) for the matchings: when a left bracket finds a closing bracket, I add 1 to the position of the left bracket. When I hit a spot that contains some query end, I answer this query with RSQ(Li,Ri).

Here is the pseudocode:

for (q in queries):
  events[R[q]].add(q);

//will store the indexes of the brackets waiting for a match
openBrackets := empty_stack()

for(i=0, i < line.size(); i++):
  if(line[i] == ')' && sizeof(openBrackets) > 0):
    add(openBrackets.top()) // adds 1 to the index of the last opened bracket
    openBrackets.pop();
  else if(line[i] == '('):
    openBrackets.push(i);
  // goes through all the queries that ends in 'i'
  for(q in events[i]):
    ans[q] = rsq(L[q],R[q])

// Prints the answers. Multiply it by 2, since the value stored in "ans" is 
// the number of pairs of matching brackets
for(q in queries):
  print 2*ans[q] + '\n'

And here is my AC submission: 7108258

deleted

This blog is really helpful for those struggling to understand the editorial for 380C — Sereja and Brackets . Also a great resource to learn Segment Trees.

In Div1C — Sereja and Brackets, what if, instead of a subsequence, a substring is asked? How would we proceed?

In sereja and brackets ~~~~~ struct Info{ int open,close,full; Info(int _open,int _close,int _full){ open=_open; close=_close; full=_full; } }; vector<Info*>segtree; string s; Info * merge(Info * left,Info * right){ int open=left->open+right->open-min(left->open,right->close); int close=left->close+right->close-min(left->open,right->close); int full=left->full+right->full+min(left->open,right->close); Info*ans=new Info(open,close,full); return ans; } void build(int index,int st,int en){ if(st==en){ segtree[index]=((s[st]=='(')?new Info(1,0,0):new Info(0,1,0)); return; } int mid=(st+en)/2; build(2*index,st,mid); build(2*index+1,mid+1,en); segtree[index]=merge(segtree[2*index],segtree[2*index+1]); } Info* query(int index,int st,int en,int l,int r){ if(st>=l && en<=r) return segtree[index]; if(st>r || en<l) return new Info(0,0,0); int mid=(st+en)/2; return merge(query(2*index,st,mid,l,r),query(2*index+1,mid+1,en,l,r)); } void solve() {

cin>>s;
s=" "+s;
int n=sz(s);
n--;
segtree=vector<Info*>(4*(n));
fo(i,4*(n)) segtree[i]=new Info(0,0,0);
build(1,1,n);
int m;
cin>>m;
while(m--){
    int a,b;
    cin>>a>>b;
    cout<<(query(1,1,n,a,b)->full)*2<<"\n";
}

}

this gives a memory limit exceeded but 

void solve() {

cin>>s;
s=" "+s;
int n=sz(s);
n--;
segtree=vector<Info*>(4*(n),new Info(0,0,0));
build(1,1,n);
int m;
cin>>m;
while(m--){
    int a,b;
    cin>>a>>b;
    cout<<(query(1,1,n,a,b)->full)*2<<"\n";
}

} ~~~~~ this passes. I dont understand the difference between the two.

Thank you very much Sereja. But excuse me, where is the tutorial?

hi, can anyone explain me why Im having the wrong answer on test 3? I can't figure it out. here is my code:

void sort(int array[], int size) { int i,j; for(i = 0; i < size — 1; i++) { for(j = 0; j < size — 1 — i; j++) { if(array[j] < array[j+1]) { int temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } } } }

int main() { int n,i; int sumD = 0, sumS = 0;

scanf("%d", &n);
int *arr = (int *)malloc(n * sizeof(int));
for(i = 0; i < n; i++)
{
    scanf("%d", &arr[i]);
}
sort(arr, n);

int k = 0;
int m = 1;
while(k < n)
{
    sumS += arr[k];
    k += 2;
}
while(m < n)
{
    sumD += arr[m];
    m += 2;
}
printf("%d %d", sumS, sumD);
return 0;

}

In 380C, I get TLE on test 12; help me, please :

include <bits/stdc++.h>

using namespace std;

struct node { int mo, dg, ca; int l,r; node () { mo = dg = ca=0; l=r = 0; }
}; node operator+(node a, node b) { node t; t.l = a.l; t.r = b.r; t.ca = a.ca + b.ca; int tc; tc = min(a.mo,b.dg); t.ca += 2*tc; t.mo = a.mo — tc + b.mo; t.dg = a.dg + b.dg — tc;

return t;
}

typedef vector tnode; void maketree (tnode &tr, string s, int id, int l, int r) { tr[id].l =l; tr[id].r = r; if (l == r){
if (s[l-1] == '(') tr[id].mo = 1; else if (s[l-1] ==')') tr[id].dg = 1; return; } int m = (l+r)/2; maketree(tr,s,id*2, l,m); maketree(tr,s,id*2+1, m+1,r); tr[id] = tr[id*2] + tr[id*2+1]; return; } node getcap (tnode tr, int id, int u, int v) { node t; if (tr[id].l>v || tr[id].r<u) return t; if (tr[id].l>=u && tr[id].r<=v) return tr[id]; return getcap(tr, id*2, u,v) + getcap(tr, id*2+1,u,v); } int main(int argc, char const *argv[]) { ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen("380c.inp","r", stdin); string s; cin>>s; int q; cin>>q; tnode st(4*s.size()); maketree(st,s,1,1,s.size()); while (q--){ int u,v; cin>>u>>v; node re =getcap(st,1,u,v); cout << re.ca <<endl; } return 0; }

Can someone say why am I getting a TLE on tc13 , I have used the usual segment tree approach for solving it . 271336839