For problem C: Using dynamic programming that f[x] means the maximum speed when the current mass of rocket is x. enumerating the type and the number of the new stage is O(NM^2). But this can be optimized to O(NM) by saving the prefix maximum of f[x]  -  Isp[i] * log(x) for every type of rocket i and every mass x.

Here is another way to look at DP optimization.

When we add a stage with some drive type, we can put K >= Kmin drives of it. But instead of taking K drives at once, we can take exactly Kmin drives, and then add arbitrary number of same-type drives in special steps which follow. Then we need f[x] — maximal speed for complete rocket of mass x, and g[x, i] — maximal speed of rocket of mass x with last stage composed of drives of type i (which is not complete yet and can be extended).

I tried to compute volume with numerical integration during contests, but my output error was too big. (Even it couldn't pass examples)

I have a hypothesis(?) that planes which divide x²  +  y² ≤ 1,  0 ≤ z ≤ a₁x  +  b₁y  +  c₁z region in half and perpendicular to xy-plane always through same point, But I can't prove it.

Interesting, so basically the cutting plane can always be a vertical one, right?

I want to share how to obtain a direction of the required plane in O(1) right after reading an input.

First of all, assume we have a unit circle, a linear function over it (say, Ax + By + C, let it be positive for convenience) and a line ax + by + c = 0. We want to compute an integral of the linear function over one of the parts the line divides the circle. We choose a parameter t, say that an one-dimensional integral over the chord parallel to the line and passing through the point equals its length () multiplied by the value at the center (), and our integral equals smth like

It equals something like

the key observation to obtain it is to change t to .

Our target is to find such a, b and c that this equals , or that the obtained linear function of A, B and C (the function above minus ) equals zero for (A₁, B₁, C₁) (the bottom layer) and (A₂, B₂, C₂) (the whole sandwich). This means that the obtained coefficients of this linear combination (, etc) represent a vector which is collinear to the cross product of (A₁, B₁, C₁) and (A₂, B₂, C₂). One can easily calculate this vector once he has read the input.

Let the cross product equal (A * , B * , C * ). Then obviously , so we just said that a = A * , b = B *  and found c using one binary search, having handled cases when one or both planes are horizontal, this solution got accepted.

We tried calculate this volume by Simpson's rule. Looks like it was very close by precision, but not enough. Do anybody know, how this precision could be predicted before writing code? Error could be estimated by . But how estimate this derivative?

It's easy to calculate this volume if you notice that the integral of a linear function over some figure equals to the area of this figure multiplied by the value of this function in the center of mass of the figure.

You can reduce the problem to the standard Longest Increasing Subsequence problem. Take all the compositions ordered by number, and write down for each of them: its position minus sum of all lengths of compositions with smaller number. Now you need to find longest nondecreasing subsequence in the resulting sequence (add zero before start and M-N after end as sentinels), and it can be done in O(N log N) with ordinary 1D segment tree or Fenwick tree.

11: There are two cases: UEF has no more than acquaintances, or no more than non-acquaintances.

First case is just dp over subsets: for every mask of already listed acquaintances remember maximum possible number of new friends we can make and mask of people who stopped not knowing us already. Updating this when we list new acquaintances is kind of straightforward with bit operations.

Second case: notice that nothing changes if list some acquaintance second time, or if we already made all people who can theoretically start knowing us know us). We will try to find longest path in following DAG: vertices are subsets of our original non-acquaintances that still don't know Uef yet, but will start knowing Uef after he lists all his acquaintances; our acquaintances naturally correspond to transitions in this graph (subsets only become smaller as we do transitions, it does not make sense to take transition that does not change the mask). We found some way to list all our acquaintances that makes all people who can theoretically know Uef actually know him and best among such paths. There can be some repeats and some acquaintances not listed, we just will delete repeats and add all not yet listed acquaintances to the end of list.

This solution works in O(2^kn) time and O(2^k) memory, where .

You can optimize solution to O(nk) — it does not make sense to make day an entrance day if there are no students who apply to NSU on this day (be careful with case where nobody actually applies to NSU). Also double-check speed of reading input, because input can be really large.

Let us first calculate the expected gain of NSU for a given fixed entrance day t (1 ≤ t ≤ T).

Suppose, S =  The set consisting of the students who applied to NSU.

Where,

P(i, t) = Probability that the i-th student will be available till the t-th day.

G_i = Value of the i-th student.

If you can calculate E(t) in O(K), then the total complexity of your solution will be O(TK) (as you can iterate over all possible valid t ). You can speed up the solution with this optimization.

How to calculate P(i, t):

Suppose,

C =  The set consisting of the colleges where the i-th graduate has applied.

r_ij =  The day on which the i-th graduate applied to the j-th college.

G(c, l, r) =  Probability that the c-th college will have its entrance day between the l-th day and r-th day.

Then:

This requires high school physics/dynamics formula, like: v = u + at, s = ut + 0.5*a*t^2, v = d/t etc.

It is always better to have "higher acceleration". So sort the extinguishers by the acceleration parameters. Use one by one until you reach your goal, or run out of the extinguishers. In the second case, you will move the rest of the way in uniform speed (no acceleration)

So you use dijkstra to compute shortest path? and instead of the heap, we can use a link-list to maintain the current min because edge weight is small? I still worry that it will be too slow to pass, so I'll appreciate it if you could send me your code. thanks!