The subproblem "find the probability that you select an odd number of balls if you pick each ball independently with prob p" has a solution: $$$\frac{1 - (1 - 2p)^{balls}}{2} $$$

How to solve C and E?

BTW, if i am not missing something then the last 4 lines could be ++mask

Okay, and how to solve it? :)

Maybe solution can be obtained on the following way. DP over the tree decomposition. State is a bag + some tree that spans vertices from the bag. And in transitions one should preserve edges which are already added in the parent bag. Number of states would be N(k + 1)^k - 1 ≈ 1.2·10⁷ and one should be careful with transitions (perhaps some precomputing will help). Does it make sense?

Have you proved that "there exists a solution where every pair of matching open and close brackets belongs to the same subsequence"? Is there some simple proof?

I have passed in practice room with the following greedy solution (which seems to work only for cost functions growing faster than linear):

• Answer is not -1 iff initial sequence is a valid parentheses sequence

• If the sequence is valid there is corresponding forest (And depth of the sequence is exactly the height of the forest).

• "there exists a solution where every pair of matching open and close brackets belongs to the same subsequence" => there exists solution where the relation of being nested over parentheses is preserved => there exists solution where the relation of being successor over vertices in the forest is preserved

• Since function grow is faster than linear it is optimal to just colour every tree into 2 colours. (The parentheses corresponding to each colour form the sequence)

Complexity is linear. But I have to admit there are some gaps in the proof.

Code http://ideone.com/uCzy9E

Saying partial cascading you mean fractional cascading, right?

it is UB in case of overflow signed integers

At least 30 people are still curious :)

For me it is quite surprising that so many teams have solved J (at least J1). How have you come up with idea? Have you used disassembling or just played with executable?

ok, everything is fine with it :)

Is smth wrong with 8-connected metric for 500ptr?

dolphin secret agents - stan - acherepanov - permin

Because circulation is actually a union of cycles?

Was the problem statement of 500ptr clear for everyone? I was confused, what the primary goal of Alice is: either to reach N-1 or to minimise traveled distance. On one hand we have "She wishes to travel to node N-1.". On other hand minimising travel distance occurs in the statement at least twice: "Alice wishes to minimize her travel time" and "Alice will always choose an option to minimize the total cost". Thus for me it was totally unclear, what the answer for the following graph is. Two vertices: 0 and 1 and two edges {from 0 to 0 cost 0}, {from 0 to 1 cost 1}. Won't Alice just loop along the first edge and get total travel distance 0 * 10^9 (she traverses that edge 1,000,000,000 times without reaching the node 1)? Now the correct understanding is clear, but anyway has somebody faced the same difficulties?

But seems that I don't have enough authority to make people change their oppinions...

It is quite usual in normal society. Normally nobody has "authority" to force people think on one way or another.

The general advise is always to create a bit bigger arrays than you need (e.g. 100010, when n <= 100000).

My general advise is to use vector instead of static array :) In that case you will find out of range even in small cases.

This is the one of the few contests where code reuse may be helpful :))

The problem C has interesting interpretation. We have a context-free grammar (robots are nonterminals and diamonds are terminals). And the questions of the problem are to find lengths of the shortest/longest strings that can be produced from each nonterminal.

Is that origin problem formulation?

P.S. Code in grammar terms: http://mirror.codeforces.com/contest/325/submission/4067816

Photo request: MIT ;)