G is really a strong problem.

When I saw G during the contest, I built a network flow graph: For each tree vertex i build a chain with infinity capacity, D = max{d_i}; for each tree edge (i, j) link all edge (v_i, 2k, v_{j, 2(k + li, j) - 1}), (v_j, 2k, v_{i, 2(k + li, j) - 1}) with infinity capacity; for each 1 ≤ i ≤ k set edge (v_{pi, 2di - 1}, v_pi, 2di)'s lower bound to f_i, the minimum flow is the answer.

Transform it into maximum flow: to check if , link (T, S) with capacity x, and create a new source S' and a new sink T', for each 1 ≤ i ≤ k remove edge (v_{pi, 2di - 1}, v_pi, 2di)'s lower bound f_i and link (S', v_pi, 2di), (v_{pi, 2di - 1}, T') with capacity f_i. If and only if the maximum flow is , then .

By using max-flow min-cut theorem, considering cut each chain , I transformed this problem into: distribute an integer x_v for each vertex v so that for each edge (u, v), , maximize the sum of f_i that satisfies x_pi = 2d_i - 1.

Obviously there is a O(nD) DP, let f(i, j) be the maximum value of subtree if x_i = j, which is going to be TLE. I tried to use data structure but still didn't know how to optimize this DP and then contest was ended.

After contest I tried more ways and they failed as well. At last I turned back to think using data structure to maintain DP arrays. The DP array can be discribed as some segments. When transferring , some segments in f(v,  * ) became longer and some became shorter, even disappear. In data structure, we can delete the segment which is earliest to disappear. When transferring f(u, j) = f(v, j) + f(w, j), merge the segments in f(v,  * ) and f(w,  * ). In data structure, we can do inserting and range adding.

Because of inserting and range adding, I gave up STL set and wrote a splay tree. The code is very long and has lots of details, so I spent 2 days to code and debug. It seems correct to give up G and check A~F during the contest.

Thanks for the analysis this problems!!!

O(n * log²(n)) solution of problem F passed with priority_queues and smaller to larger merging in tree. 41932704

Using the seventh set of data, my code is running YES locally, but after the commit it shows that my output is NO.

why ????

http://codeforces.net/contest/1023/submission/41933641

Easier way to solve C: Choose the first k/2 left brackets and the last k/2 right brackets. It's not hard to prove this gives a valid bracket sequence.

Actually, problem D can be easily solved with O( n + q ). Here you can take a look at the code. The idea is to use 2 pointers, so we can check if the array (except zeros) is correct. How? Initialize array of bools b[i] which tells us if we can find number i further. Then we move right pointer r until a[i - 1] > a[i]. Then we move left pointer l up to r and update bools array if a[l] > a[i] because if we meet number a[l] further, then the segment should have involved index i, so a[i] can't be lower than a[l]. So in this case b[a[l]] becomes false.

In the end we deal with max number (if it's not in the array, then use one zero to get it. No zeros in this case -> the answer is "No") and finally make all other zeroes like previous or following number, it won't break correct array.

The size of array b[i] is q and algorithm is linear in n, so time is really O( n + q ). Moreover it can be upgraded to amortized O( n ) if hash table is used istead of array of bools

I have a really easier solution for problem C: start from the first element and save the number of opening brackets that are not closed in x. the first time that i+x equals to k.(i is the index of current bracket) print the first i elements of s and k closing brackets.

the code for this solution:

int x=0;
for (int i=0; i<n; i++){
    if (i+x==k){
        cout<<s.substr(0, i);
        for (int j=0; j<x; j++) cout<<')';
    }
    if ( s[i] == '(' ) x++;
    else x--;
}

I got accepted with this solution :)

the python code :41698479

Could someone help me with problem F?
I don't understand which context "your" was used in in the beginning, what "path" are we looking at... Overall I do not at all understand what the editorial author wanted to say and I can't even "connect dots".
Thanks,

In problem F : if I understand it correctly then we need to collapse all the edges on the path of the currently considered opponent edges and for that we need to traverse the path from 'u' to 'v' and you had said "To do this efficiently, we can just do it naively (even without needing to compute LCAs!).". So, can you please explain how can we able to traverse the path without having LCA's??

can someone please explain the impoosible case in prob D. I didn't get that clearly from editorial.

In solution of problem B, when k <= n solution should be (k-1)/2 not k/2. also mn = k — n I believe, not n — k.

Minor typos but probably worth editing :D MikeMirzayanov

I would like to know if we can solve D problem like this....

change any zero value to a non zero value just to its left (or right, doesn't matter), check for occurrence of value "q" in the array, keep track of li and ri as index of first and last appearance of i in array for all possible i and then for every "i" check if there is a value less than i (let that be j) in the array in index range [li, ri] . If such a value exists then we can say that such an array cant occur because query with i>j will always happen after jth query so there can be complete overlap or partial of ith query over jth query and not vice-versa....

I think this a sufficent condition for the solution but i m not able to get ans....

I would to like to know for some flaw in the solution or counter example for the same (explaining the flaw)

Thanks in advance!!!

Lewin

For Problem F, How will u collapse the nodes along the path into larger node without LCA?

В задаче В при k≤n ответ не всегда ⌊k/2⌋. Например при n=8 и k=6 мы получаем пары 1-5 и 2-4, то есть ответ 2. Полагаю, если выразить формулой, то это k-(k/2 + 1).