I solved C a bit another way with DP: http://codeforces.com/contest/466/submission/7770043 First consider the case when Σ a = 0, where a is input. Then count the number dp of all indexes i from 0 to n - 2, for which Σ₀ⁱa = 0. The answer is .

Now consider the case when s = Σ a ≠ 0. Take two lists dp₀ and dp₁. dp₀ will contain all indexes i, for which , and dp₁ will contain all indexes j, which satisfy . Now remains a bit tricky part, which can get TLE, if not correctly implemented: count all ordered pairs from dp₀ and dp₁. This can be done in linear time by looping through dp₁ and saving current dp₀ index:

f=0
for sec in dp1:
    ans += f
    for fir in dp0[f:]:
        if fir < sec:
            ans+=1
            f+=1
print ans

Hope so that D & E really comes soon !

I didn't quite understand Problem B's solution in the end. Why no need to consider newa > ceiling(sqrt(6n)) ? can someone give more details?

I don't quite understand the editorial for C. However, here's my solution. This is probably DP, although the fact that it might be DP doesn't come to my mind.

The first part is the same as the editorial's; find the sum s and if it's not divisible by 3, return 0.

On the second part, we keep three variables: t for the sum of all elements up to this point, ct to count the number of prefixes whose sum is , and res to count the actual number of pairs.

We loop over each element except the last one; suppose the current element is p. We add p to t. If this causes , we add the value of ct to res. If this causes , we increment the value of ct. We do this in that order; switching won't work (try input 0 0 0; expected answer is 1 but switching the order of the above gives 3). This gives O(n) time with O(1) memory besides storing the array, better than the proposed O(n). Now why does that work?

First, observe that ct holds the number of ways we can cut the array into two such that the left part sums to and the right part sums to , where the cut is done before p.

Whenever , it means the last part sums to . Now, ct holds the number of ways we can cut the array so that the left part sums to before p. So we now have ct possible divisions: the first cut is any cut that ct has counted, giving a left part of , and the second cut is right after p, giving a right part of (since the sum of the left and middle parts is ). And the middle part is of course by elimination. Thus we increase res by ct.

Now we update ct. If , dividing right after p gives a left part summing to , so this should now be counted by ct for future iterations. Note that we don't do this before the above so that our program won't mistakenly divide the array in the same place; if we update ct first, cutting right after p is now counted in ct, and if we also increase t, we will count dividing right after p among the possible ways, and thus both cuts happen right after p; this doesn't work for obvious reasons.

Thus, after every iteration, ct holds the number of ways to split the array somewhere before the next element into two such that the first part sums to , and res holds the current total number of ways sought, where the splits are done before the next element. Since the loop finishes at the penultimate element, res now holds the number of ways to split the array as stated where the splits are done before the last element, which is the number we seek. (If we advance one more, it's possible that res counts where the second cut is at the end of the array, giving an empty third part, not accepted.)

I hope the above is clear. The algorithm itself fits in three paragraphs (paragraphs 2-4 above); the proof is what makes everything bloaty.

Another way to solve C is to take the indexes strictly smaller than n where the sum from the beginning is exactly sum/3 and the indexes strictly smaller than n where the sum from the beginning is exactly 2*sum/3. Lets call these sets idx1 and idx2. Obviously they will be sorted because we iterate from 1 to n-1. For every index from idx1 we count the indexes from idx2 which are strictly greater than our current. This could easily be done in O(logn) using binary search. Total complexity: O(nlogn). My solution.

Задача B. Как доказать, что если ab ≥ 6n?, то мы всегда можем разместить всех людей?

how to solve E??

I am unable to understand the solution for problem D and please clear me the meaning of dp[i][opened].

In D,while a[i] + opened = h,why can we open a segment？Then,a[i]will bigger than h.Is it a mistake?

I am unable to understand the solution of problem E ,would anyone like to explain the problem E ??

Err..I've made a mistake.... Just ignore me, please..

i got my problem B code accepted by O(n).

Бонус: Придумайте, как решать задачу онлайн?

для каждого сотрудника будем хранить в СНМ сет документов, подписанных его подчиненными. Для каждого документа находим первого (first[i] = x) и последнего подписавшего (last[i] = find(x)). При объединении множеств сливаем меньший сет с большим.

Тогда для запроса типа 3 ответ "YES", если сет find(x) содержит нужный i, first[i] является потомком x, а last[i] — предком.

Задача "является ли u предком v" в онлайне в общем случае решается с помощью link/cut деревьев. Можно ли придумать здесь что-то проще?

There is typo in D (1) first case: it should be dp[i][opened] += dp[i-1][opened — 1]

In Problem D . We can close more than one segments as in the case a[i]+opened+2=h we can close 2 segments here, but in the Editorial it's considering the case of closing only one segment. Can anyone tell how it will produce right answer. Thanku...

sorry, i can not understand the solution of e, can anyone clear it, thanks very much

sorry, i can not understand the solution of e, can anyone clear it, thank very much

Can anyone please explain the solution of 466D — Increase Sequence. I am unabel to understand the solution given in editorial.

Can anyone explain me Solution D.??

Can anyone explain me solution D..??

Antoniuk nice fall :) For two contest you will beat dreamoon_love_AA.

Problem-C 466C - Number of Ways is exactly the same problem as 21C - Stripe 2 ...Nothing to say !!

i am having problem understanding the solution of C.

let’s iterate the end of first part i (1 ≤ i ≤ n - 2) and if sum of 1..i elements is equal S/3 then it means that we have to add to the answer the amount of such j (i + 1 < j) that the sum of elements from j-th to n-tn also equals S/3 .

why not such j(i<j)?

In problem C why do we do cnt[i]+=cnt[i+1] and at the end ans+=cnt[i+2] ?

I had serious difficulty in understanding the editorial of problem D. Took me a good amount of time to reach the solution. This comment helped a lot.

Here's the approach: Firstly, if there exists an element in the array >= h, there is no way, so the answer is 0.

Now, let dp[i][j] denote the no. of ways to make the first i points be equal to h s.t. there still remain j open segments after the point j. Now, there are 5 possibilities at a particular element:

• Don't open or close any segment here: In this case, we require j + a[i] == h and the no. of open segments after (i-1)st element must also be j. So, here we consider the no. of ways to make first (i-1) elements to be equal to h s.t. there exist j open segments after it. So, we add dp[i-1][j] to dp[i][j].

• Open a segment here and don't close any: We require a[i] + j == h and no. of open segments after (i-1) must be (j-1). So, we add dp[i-1][j-1] to dp[i][j].

• Close a segment here and don't open any: We require a[i] + (j + 1) == h since total contribution to ith element is by (j+1) segments (j which still remain open and 1 which is closed) and no. of open segments after (i-1) must be (j+1). Note here that there are also (j+1) ways to choose the segment we close at i. So, we add (j+1) * dp[i-1][j+1] to dp[i][j+1].

• Open and close a segment here (length 1 segment): We require a[i] + (j + 1) == h and no. of open segments after (i-1) elements must be j. So, we add dp[i-1][j] to dp[i][j].

• Close a previously opened segment and open a new segment: We require a[i] + (j + 1) == h and no. of open segments after (i-1) elements be j. Also, there are j ways to choose the segment to close. So, we add j * dp[i-1][j] to dp[i][j].

The answer to the problem is simply dp[n][0].

Here's my submission: 45472102

The last line of the explanation of problem E is a little ambiguous. Here's the actual interpretation:

...which we can calculate using dfs(). If v is an ancestor of u, then it must hold that in[v] ≤ in[u] and out[u] ≤ out[u].

One more point: the above condition holds iff we ensure that in the final set of trees, every dfs performed on a tree starts at the root node. For this in the main loop of dfs(), for all the vertices processed in sequence, we can check if that vertex has not been visited and it is the root node of a tree (its indegree is 0), we can perform dfs starting from that vertex by calling a function that performs the dfs (say dfs_()). Here's my code: 46903908

Please explain Problem C in simple words. I am facing lot of difficulties in understanding the approach. I tried to dry run the code for various test cases but couldn't figure out the approach.