True bro, windows sucks

used linux, but still missed it ;(

Great, so this is not another stupid LP problem, that's consoling :D.

1000 can be solved with this very simple algorithm based on network flow.

Let num_i be the number of opens(left parentheses) lying on the path from node i to root. dep_i be the number of edges of the path from node i to root. Then bal_i = 2num_i - dep_i is the balance i.e. the number of opens substract the number of closes(right parentheses).

So for a restriction of path , we have:

bal_u = bal_v

bal_w - bal_u ≥ 0, for any node w that lies on the path from u to v.

Why? Because if is open, then is close. So we needn't care about the LCA.

Besides, obviously dep_u + dep_v must be even.

Thus, we've got two kinds of restrictions:

OK, now let's build a graph. We know the maximal flow is equal to the minimal cut, so we'll just talk about the cut. For any node in the tree, we make n new vertices, and connect the source to the first vertex, and connect the last one to the sink with capacity ∞, and connect adjacent vertices with capacity 0(actually we don't connect them, it's just for better-understanding), then, we have to cut one edge, if we cut the edge connecting the k-th vertex and the (k + 1)-th vertex, then we consider that num of the tree node is k.

So for each edge connecting one node and its father. num of the node mustn't be smaller than its father's and mustn't be bigger than its father's by more than 1. If cost_open is smaller, then we add the cost of open to the answer, and if the node's num is equal to its father we have to pay cost_close - cost_open, otherwise we'll do the similar thing.

So how to deal with those restrictions? For example, if num_u ≤ num_v - Δ, for all k, if k - Δ ≥ 0 then add an edge from the (k + 1)-th node of v to the (k - Δ + 1)-th node of u, or if k - Δ < 0, then num_v ≠ Δ, we can simply add an edge from the k-th node of v to the (k + 1)-th node of v. All these edge have a capacity of ∞.

Finally, add the minimal cut of this graph, which equals the maximal flow, to the answer.

For C = 1, B = 3, A = 3 we got:

f(3) + f(3) + f(1) — f(0) — f(2) — f(2) = 6 + 6 + 0 — 0 — 1 — 1 = 10 non triangles, but it is almost 1*3*3 = 9 combinations of al possible length values...

Something wrong..

Can anyone provide me a proof/hint (intuitive/mathematical) for this?

Interpolation of [0, 0, 1, 4] is f(x)=x(x+1)(x-1)/6

Why do you need replies on AoPS, you could have waited for the editorial :P

"Yes, I asked for help in the Internet during the contest. I didn't expect the answer though, so it's fine, right?"

:>

That's one of the lamest excuses I have ever heard xD

Correct me if I'm wrong, but it sounds like you think it's OK to post a problem from an active contest to a problem solving forum? Isn't that explicitly disallowed? From the topcoder rulebook:

Collaborating in any way with anyone else (member or not) during a rated event is considered cheating. This includes discussing problem statements or solutions between the time that the coding phase begins and the time that the challenge phase ends.

Can confirm. 1793 -> 1679 over the last two rounds.

I would say "YES, it is a bad contest". But sometimes it is difficult to estimate difficulty. :). So sometimes it happens :)

And the first problem A proved to be simple — it's just (as posted by Egor above):

f(A) + f(B) + f(C) - f(A - B) - f(A - C) - f(B - C) where f(X) = 0 + 1 + ... + X(X - 1) / 2

How much simpler can it be? :) It's intuitive :)

For a regular SRM round — yes problems were too hard. But the main purpose of the contest was to choose top 40 to advance, and 500 people with 0 is OK.

It is defnitely better than 150 people with 300 and 500 solved, and the question is who codes faster.