681A - A Good Contest

If for any participant before_i ≥ 2400 and after_i > before_i, then the answer is "YES", otherwise "NO"

Code

681B - Economy Game

We can simply try every a from 0 to n / 1234567 and b from 0 до n / 123456, and if n - a * 1234567 - b * 123456 is non-negative and divided by 1234, then the answer is "YES".

If there is no such a and b, then the answer is "NO".

Code

681C - Heap Operations

Let's solve this problem with greedy approach. Let's apply operations from log in given order.

If current operation is insert x, then add element x to heap.

If current operation is removeMin, then if heap is not empty, then simply remove minimal element, otherwise if heap is empty, add operation insert x, where x can be any number, and then apply removeMin

If current operation is getMin x then do follows:

1. While heap is not empty and its minimal element is less than x, apply operation removeMin.
2. Now if heap is empty or its minimal element is not equal to x, apply operation insert x.
3. Apply operation getMin x.

In order to fit time limit, you need to use data structure, which allows you to apply given operations in O(logN) time, where N is a number of elements in it. For example, std::priority_queue or std::multiset.

Code

681D - Gifts by the List

Formal statement of the problem:

You have a directed acyclic graph, every vertex has at most one ingoing edge. Vertex A is an ancestor of vertex B if there is a path from A to B in graph. Also every vertex is an ancestor of itself.

Every vertex i has a pair – vertex a_i, a_i – ancestor of i.

You need to build such sequence of vertex, that for every vertex i the leftmost vertex in the sequence which is ancestor of i must be equal to a_i.

Or you need to tell, that such sequence does not exists.

Solution:

Assume sequence ans, which contains every vertex from sequence a_n by once and only them. Let's order elements of this sequence in such way, that for every i and j if ans_i – ancestor of ans_j, then i ≥ j.

If this sequecne is the answer, then print it. Otherwise, there is no answer.

Why?

1. If some vertex a_i from sequence a in not present in ans, then a man, who needs to give a gift to a man number a_i, will not be able to do it. So every vertex a_i must have place in the resulting sequence.

2. If a_i – ancestor of a_j and i < j, then a man, who needs to give a gift to a man number a_j will not be able to do it.

How can we build this sequence?

Let's sort vertices topologically, than reverse it and remove redundant vertices.

Now we need to check if that this sequence can be the answer.

Let's calculate to whom every man will give his gift. At start for any man we don't know that. Let's iterate through vertices of the resulting sequence.

For every vertex (man) from current vertex subtree (i.e. for vertices whose ancestor is current vertex) such that we still don't know whom will this vertex (man) give a gift to, stays that these vertices would give a gift to current vertex, because it is their first ancestor in the list.

Iterate through that vertices (men) in dfs order and remember for them, to whom they will give their gift.

After we apply this operation to all vertices from resulting sequence, compare for each man to whom he will give his gift and to whom he needs to give his gift. If there is at least one mismatch, then the answer doesn't exist.

Code

681E - Runaway to a Shadow

At first assume the case when cockroach at the moment 0 is already inside or on the border of some circle. In that case the cockroach will always survive, i. e. the probability is 1.

Otherwise the cockroach will have time to run to every point inside the circle with center of x₀, y₀ and radius v × t.

Let's iterate through all the shadow circles and figure out how each circle relates to "cockroach circle". We want to find the maximum angle, such that choosing the direction from this angle the cockroach will have enough time to reach current circle and survive.

In general, maximal "surviving" angle, such that choosing the direction from it the cockroach will reach the circle in infinite time – is an angle between two tangents from a start point to the circle. If length of this tangents is not greater than v × t, then this angle is the needed one.

Otherwise we need to find intersections of cockroach circle and current circle. If there is no intersection points or there is only one, then current circle is too far away from cockroach. Otherwise intersection points and start point form the needed angle for this circle.

After we've found all the angles, we can figure out that those angles are segments that cover a segment from 0 to 2π. Sort their ends and find a length of their union. This length divided by 2π will give us the answer.

Code