Funrated.

It's fixed, and the calendary says unrated also.

I think rated->unrated is very gaoxiao.do you think so?

А мне оно не пришло. Вот я встал к 12, поел, вижу -- еще целый час! Так я проспал начало. :)

Судя по результатам финала — сверху:)

So will it be fixed？

I think I have a solution based on that idea, but it got TLE despite being N log N. I think my function to determine whether the intersection point is inside the circle is too slow (right after the contest I realised a much simpler way to test it, but during the contest I had to use a bignum class to avoid overflows).

I sort the points by angle made at A and at B, and rank them. Then I place them in a new coordinate system, where x1 < x2 means A-P1-P2 is counter-clockwise and y1 < y2 means B-P1-P2 is clockwise. Now satellites P1 and P2 can be connected if there is an intersection outside the planet, and there is no other satellite (x, y) such that x <= max(x1, x2) and y <= max(y1, y2) in this other coordinate system. That I do by keeping the smallest y coordinates for each x coordinate (using a set for each x coordinate), and then maintaining a segment tree over those.

The intersection of two satellite coverage area can be formed as a satellite-like coverage area.

If this satellite-like coverage area is covered by other satellites, there will exists at least one satellite coverage area which contains this satellite-like coverage area (instead of some union).

Considering the projections of coverage areas on the half-circle border (as intervals), the query is equal to determine whether there exists one interval (except i-th and j-th) which is able to cover the intersection of i-th interval and j-th interval.

When I finally realized that, I tried to modify my wrong solution but actually I didn't have enough time :(

Our recommended solution is to sort all the intervals by their left endpoints, and use a segment tree to maintain the maximum right endpoints, which can be done in .

Yes, greedy by decreasing of length.

If we sort all prefixes by decreasing of length, we can take them greedy. And with hashes we can check if we can pick current prefix.

I tried something different. I'm pretty sure my idea is valid but my implementation is wrong. This is my idea: first of all, we will use rolling hashing to quickly compare strings. We say string A is a child of string B if the first letter of A can be removed to get B. We construct a tree or many trees with all the prefixes. Now the problem is equivalent to the most nodes you can "color" so that no two adjacent nodes are both "colored". You can solve with two dp arrays. dp1[i] will be the most you can color in the subtree of i while coloring i. dp2[i] will be the most you can color in the subtree of i without coloring i. We get the recursive formula that dp1[i] = 1 + sum of dp2 of children and dp2[i] = sum of max(dp1, dp2) of children.

1. build the trie

2. build another graph G where the vertices are the nodes of the trie (all possible preffixes) and add an edge from v to u if string v can be obtained from u by removing the first letter

3. G is a forest

4. now the problem can be solved with dp

I solved with DP, but there was people that solved in 11 minutes, maybe there is an easier solution. My idea, lets consider every prefix of all strings and build an graph, where exists an edge between the prefix and the prefix without the first letter. It will be a forest. No two adjacent vertex can be at the set and just the vertexes that are prefix can be choose. Since you have to find maximun, you can apply dp.

Am I the only one who used Aho-Corasick for B? Using suffix links, we can build a forest and the problem reduces to finding maximum independent set in a forest, which is straightforward.

Observe the input. check the difference between any 2 numbers in given array. B should not have this difference. Choose smallest number which is not one of these differences as b[1]. Repeat from b[2] and so on

It's always possible — just greedily add the smallest possible element to B that doesn't violate the constraints.

centroid decomposition and dp f[u][v]=maximum beauty of subtree u if vertices in the path u->v are in a cycle

Maybe a DP on the tree, using some data-struct like segment tree to obtain the sum of a path. The answer of the subtree of node x is ans[x] = max(sans[x]. max{i.c + sans[x] + sum(x,i.a) + sum(x,i.b)}), for i in V[x], V[x] is the set of input triple<a,b,c> where lca(a,b)=x, sans[x] = the sum ans of x's children, sum(a,b) if the sum of value[x] for each x on the path(a,b), value[x] = sans[x] — ans[x]

dp[v][0] — maximum beauty of substree when v is not in any cycle

dp[v][1] — maximum beauty of substree when v is in cycle

We have u, v, cost. Let's try to add cycle at lca(u, v). In order to get right sum we need to count on path from u, v to lca the sum of beauties not including this path. It can be done by calculating sparse table the same way we do with lca. O(nlogn)

let dp_node be the maximum sum of edges you can add such that those edges belong in this subtree and the subtree is still a cactus.
let
Then if you do not make any cycle pass though node then dp_node = sum_node. otherwise if you take the edge (u, v) , lca(u, v) = node and make it's cycle pass through node , then dp_node is .
All you need to do is tree sum updates and queries which can be done by building a bit on dfs start end times easily in NlogN.

Brute force, since all b[i] <= 1e6, you can try for each i in {1..1000000} to loop through the array a and find for each a[j], if i+a[j] is visited before, if not add that i to the answer list, and mark i+a[j] for all a[j] as visited, you need to break when the answer list equal to n.

1. Check that all numbers A[i] are different.
2. Generate random number from 1 to 10⁶ (define it x)
3. Check x. (if it`s bad — repeat 2)
4. Add to set all pairs A[i] + x.
5. Repeat 2,3,4 N times