681A - A Good Contest

If for any participant before_i ≥ 2400 и 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 min, otherwise if heap is empty, then 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 to 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_n in not 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.

Для всех вершин (мужчин) из поддерева текущей вершины (т. е. для вершин, для которых текущая вершина является предком), для которых мы не знаем, кому эта вершина (мужчина) будет дарить подарок, верно, что эти вершины будут дарить подарок текущей вершине, потому что текущая вершина – самый первый их предок из списка.

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 on 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 have time to run to every point inside the circle with center of x₀, y₀ and radius v × t.

Let's iterate all shadow circles and for each figure how this circle relates with "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 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 find point of intersections between cockroach circle and current circle. If there is no such 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 find all the angles, we figure out that those are segments, covering a segment from 0 to 2π. Sort their ends and find a length of their union. This length divided by 2π is the answer.

Code