The last problem: if after 6 hours the rocket is higher than the eclyptic, send it then; else the rocket crosses eclyptics, and that moment can be found with binary search; to find the position after t seconds, rotate point (0,-cos(phi),sin(phi)) by t/day_length*2pi around z-axis, then rotate it by -alpha around y-axis, and z-coordinate will be oriented distance to the eclyptic

Problem 11. Trigonometry. Find ratio between A1-L and A2-L (tangets). Then calculate arcsine.

2) Just determine time when item starts decoding and time when it's leaving the buffer than you get segments [enters_buffer, exits_buffer]. After just found point in time where maximum segments intersects. How to find this "enters_buffer": iterate from the end to begin and keep time when current item enters buffer, when iterating just update this smth like enters_buffer = min(enters_buffer, i * d); enters_buffer -= time_of_decoding[i]. There is a case when we have "IBBI" we know that 3 must be decoded before 1 so in our loop we skip 3 and update "enters_buffer" after iterating 1. So how to find "exits_buffer": for every item u iterate for each item v where v depends of u and choose maximum of enters_buffer[v] + time_of_decoding[v]

6) First of all, parse all input and calculate number of fields which take 1, 2, 4 and 8 bytes.

For minimal size we can order fields in non-increasing order and then add padding so that the total size is divided by max-size field.

Maximal and average sizes can be found using dynamic programming. Let's consider dp[r][c1][c2][c4][c8] be avg/max size of current structure where r is current size mod 8 and cX -- number of remaining fields with size X. When calculating average we also maintaining probability to get to each state. Transitions are done by inserting fields of all possible sizes. Then, for maximum we need to find max for all r among dp[r][0][0][0][0] and average equals sum of all dp[r][0][0][0][0] + probability[r] * padding(r) where padding(r) -- is padding we need to add to the resulting structure having remainder r.

The dynamics can be optimized by using only two layers

I don't have ever seen single interesting problem with long description, and I think this time is no exception...

Kuhn or flows. With one of them it’s an easy task

Discard all packages that has at least one version that doesn't make conflict with any other package.
Now you are left with some packages where all versions make conflict with some other package. You want to choose exactly one version from each package, such that you also choose no more that 1 version from a conflict set. That is exactly like finding a matching, where all left nodes are included.
So, for this part, make a bipartite graph, with left nodes representing packages, and right nodes representing conflict sets. Add and edge between X and Y, if package X is in conflict set Y. Then answer is Yes, iff max bipartite matching = number of packages.
Solution can be constructed by looking at matched edges, and taking a version that is in both package and conflict set.

1.At first, check if there are any versions, which are not included in any conflict. Update answer for those programms.

2.Then, make a bipartite graph with conflicts in the left part and programms(which you don't have answers yet) in the right(and write a version on the every edge for output). Find maximum matching in that graph. That's it.

Greedy algorithm with random.

for each i = 0, 1, ..., n / s memorize the segments that are near point i * s, to answer the query with point x look at these ssegments at x / s - 1, x / s and x / s + 1; i took s as 4

Actually I only make all the coordinate 1E6 times larger and use a Segment Tree and Pass the problem. So I am wondering what's the official solution idea, Since my solution has nothing to do with the randomability.

We solved it with "naive" algorithm.

For every interval, [L, R] add it to vector for indices , to answer point query x, look at the vector corresp. to and just check how many intervals x lies inside.

It's not hard to show that expected runtime is ; I don't know how to show that it's quick with high probability.

We solved it with "interval tree"

Can also be solved with Binary Search Tree. Notice that number of segments that contains X = total number of segments — (number of segments that has right side  < X + number of segments that has left side  > X). So we can use two BSTs, one for storing left sides another for right, and keep sub-tree sum for the ids and size of sub-trees in each node. Since the data is random, so we don't need BBST like Splay-Tree / Treap, normal BST is enough.

I could pass the 8th test only by rewring computation from floating numbers to integers. But unfortunetaly, couldnt have time to squeze in TL.

You meant Ω(n²), didn’t you?

use dsu, but while unioning sets, append one with lesser sets of conflict vertices to one with bigger; after unioning sets, if you appended B to A, then for each conflict vertex in B's set change B to A in that set

Dijkstra on hex graph: build graph -> don't forget to add reverse edges for rivers -> run Dijkstra -> AC.

You can emulate many dimensional arrays on 1-dimensional. It is very easy.