If for any participant *before*_{i} ≥ 2400 and *after*_{i} > *before*_{i}, then the answer is "YES", otherwise "NO"

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".

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:

- While heap is not empty and its minimal element is less than
*x*, apply operation*removeMin*. - Now if heap is empty or its minimal element is not equal to
*x*, apply operation*insert**x*. - 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`

.

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?

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.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.

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*_{0}, *y*_{0} 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.

is there a math approach to Problem B? like GCD o like that? Because i tried with diophantine equation, but i can't solve it!

Mine is a faster solution, which uses some math, but it's not

O(1).Let

p= 1234567,q= 123456,r= 1234 .Note that .

Let

ibe inverse ofrwrtppa+rc=n-qbNow, for all non-negative values of

b, such thatqb< =n, is the minimum non negative possible value ofc. Findacorresponding to this value, and if it is > = 0, then there exists a non negative triple.Gives answer in O(n/123456)

No. This is the Frobenius Postage Stamp problem, which doesn't have any closed solutions for more than 2 summands. See https://en.wikipedia.org/wiki/Coin_problem You can of course solve it with Euclid's algorithm, but some coefficients might be negative. Getting a solution for positive integers is a much harder problem.

Maybe it's now very hard to get a solution for positive integers.

AC Code

it's Euclid's algorithm right?

I of course meant a closed form solution. You can obviously brute force it in O(n^(k-1)) where k is the number of different items, but there's no equivalent to euclid's O(k log n) for positive integer coefficients.

I want to thank you for sharing such a nice code for extended gcd, I have always tried to learn some code which was around 20 lines (like this one — http://stackoverflow.com/questions/12826114/euclids-extended-algorithm-c) by heart without understanding why it works, now everything is much simpler. Thank you! :)

Something interesting: because of the Frobenius problem, any number higher than 27406117 will always result in "YES".

During the contest, I used this fact to recursively brute-force check the remaining 27 million integers.

I am using a map for the third problem but i can't understand why my solution is showing time limit exceeded, here is my solution http://codeforces.com/contest/681/submission/18472898. plz help, I then tried to further optimize by removing a a for loop inside but then it is giving memory limit exceeded, here is my modified code http://codeforces.com/contest/681/submission/18475008. Plz help.

Your links are broken cuz of ".plz" suffix

corrected, Plz check it now

Try with scanf once instead of cin.

I've implemented with maps and got passed see my code http://codeforces.com/contest/681/submission/18536377

My submission for problem C timed out because I used cin/cout -_-.

same here. :(

Without ios_base :: sync_with_stdio(false) :

(TLE) http://codeforces.com/contest/681/submission/18466644

After putting ios_base :

(AC) http://codeforces.com/contest/681/submission/18480979

why so many downvotes? :(

In E, I got a TLE on one of the pretests for reading the input as doubles instead of integers. Is it really necessary to have such strict time limits just for reading the input?

Disappointed with my performance on C. Timed out when using

`std::to_string`

, but passes if I keep a pair of string and int. Not a fan of problems that require fast in/out optimizations, but I understand why they're necessary.WA: http://codeforces.com/contest/681/submission/18463859 AC: http://codeforces.com/contest/681/submission/18481068

Any proof for problem C?

Seems everyone knows it is a gready problem...

For D, I think this is simpler solution (with idea by pdwd):

Note that a man

vmay want to give gift either to himself or to the same guy as a direct parent ofvwants. Otherwisevand his parent have a conflict. Then we simply DFS and check this for each node, and after leaving the node, we add the node to the answer only if it wants to give present to itself. We can do it because if the man is in someone's preference, he has to give his present to himself, otherwise they have a conflict.Submission: 18481462

Yeah I was just solving it out of competition now, and that's actually pretty much what I did, I had just missed one edge case. I was pushing the index into the answer vector if it hadn't been pushed before, not only if it was giving it to himself.

Which would fail when a node has several children, and all it's descendants of a branch are giving gifts to it, but some descendants in other branches aren't.

Then you probably got WA on pretest 6. I had the same problem and noticed that we can push just when a node gives a gift to himself. However I don't consider this as an edge case. You would have to sort nodes by depth and make them unique to make your approach somehow working.

Darn. I wasn't familiar with std::priority_queue. So I had to implement everything myself with std::vector.

[SOLVED}Can anyone help me look at my problem E code? I keep getting WA in question 29, and I even carefully studied the editorial's code, and feel like my code is doing exactly the same?

Where am I going wrong?

Thanks for the help:

http://codeforces.com/contest/681/submission/18482766

EDIT: Found my stupid mistake, nevermind

Problem D: We don't even need to make topsort, just go up for every vertexiuntil we founda_{i}or a marked vertex (if it marked not asa_{i}, then - 1), and mark on this path all vertices asa_{i}(it means, that vertex has a passing path to thea_{i}), because all path shouldn't be intersected. And answer will be list of distincta_{i}sorted by height in the tree.Code: 18471518

Anyone used unordered_set for B? I just brute forced every possible combination of (a,b) and matched with values from c. Actually didn't time out. I feel so lucky.

Infact,O(n/1234567 ★ n/123456) is pretty quick, even it is brute force.

That's very true. I tried using normal set first on my machine, but it seemed very slow, so I had to use unordered_set instead.

Two for loop will do :)

My code is the same as the code presented in problem C, but done in Java 8. I used a priority queue, but it still times out on test 10. I don't know what else I could implement for this problem. Any help would be appreciated. Here is the code: http://codeforces.com/contest/681/submission/18484919

System.out.print is slow in Java. Try using a StringBuilder or PrintWriter. I believe it will pass as syso is enough to cause TLE in this problem.

Ah thanks! Yeah this problem seemed to be entirely decided by I/O speed which was kind of annoying :)

Thanks for such an awesome contest!!! I got wrong answer in case 27 of Problem C. Here is my code :- https://ideone.com/CVl5ov

Thanks for a good contest.Enjoyed solving good problems.

can anyone explain me B(Economy Game) no problem please? I can't understand given code of B(Economy game). My problem is that : why I increased the value of b to n-a?

here is the code :

## include

using namespace std;

int main() { int n; cin >> n; for (int a = 0; a <= n; a += 1234567) { for (int b = 0; b <= n — a; b += 123456) { if ((n — a — b) % 1234 == 0) { cout << "YES"; return 0; } } } cout << "NO";

}

(n-a)-(b)>=0

(n-a)>=b

b<=n-a hope it helps.

D could be done very easily in 20 lines. Link

Nice,Can u ellaborate the approach ?

This is how, I solved problem D.

If a person gifts to himself, no problem. If person gifts to its ancestor 'x', then its parent must also gift to 'x', this way we can go to top following the parent pointer,till person doesn't gift himself. We can do this for all leaf nodes, If its successful, answer exist else -1.

Now, how to print answer, just print all unique a[i]'s in the order they appear in Topological sort, as topological sort (not necessarily unique) is kind-of ordering which should appear first & which one later.

http://codeforces.com/contest/681/submission/18495490

There are so many ways to do D. Mine is,

In the problem you are given a forest of directed trees, build the LCA using Nodes which are root( Root have in-degree 0 ).

dp[i][j] stores information for LCA.

dp2[i][j] stores the number of requested ancestor from i to i's (2^j-1) parent.

Any node u is a requested ancestor if it occurs in request of some i.

Now just do LCA type skipping between the requested ancestor of every i by taking difference of their levels(They can be in different sub trees too, that is why we need to check at last that the skipping leads to same requested ancestor) and also the sum the path , this will tell us whether their are no nodes in between which are requested ancestor. Just check it for all that it is possible to have A[i] as the ancestor.

If yes sort the requested ancestors on the basis of decreasing levels ( Take an example you will understand why).

18476129

It would really be helpful, if the setter/tester code given in Editorial had meaningful variable names. E.g. Problem D have array names inA, a, r which are hard to follow and understand.

Also, few one line comments would also be helpful.

I would be very thankful, if the moderator/setter/tester can please put effort in this direction,

can anybody

helpme improve my code ofproblem Cits inpython 2. i am gettingtime limit exceeded in test 26. 18502038The operation of remove min that you have is O(n) That is to say, every time you remove a min, you perform an scan through the whole list ( min(n) ) in orther to find the minimum and then remove it.

The thing is that your algotirthm is O(n^2) which is a high complexity for the size of n (10^5).

I recommend you to read about priority_queue datastructure and it's implementation through a binary heap and not an array (as you do). The binary heap perform removeMin operation in O(logn) time. So if you use it, your algorithm would be O(nlogn) which is acceptable.

https://en.wikipedia.org/wiki/Heap_(data_structure)

EDIT: I also append the time complexity of the operations in python

https://wiki.python.org/moin/TimeComplexity

Hope it helps :)

Thanks a lot. Was thinking same , actually i have recently learned python and wanted to give it a try.Thanks for the link to time complexity page.Was completely unaware of time complexities of different functions in python.

for div2D http://codeforces.com/blog/entry/45404?#comment-299935

what does this mean?? " 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. " please elaborate someone?

I will never love geometry >_>

ScreenshotProblem E:I have seen some accepted codes as well as the code given in the tutorial. But one thing I am not understanding why I have to calculate the angle using both asin and acos. Whats the difference? For example (tutorial code)-I also didn't get it. If someone could explain why divide in two cases, it would be of great help.

Ah, I get it now.

The two cases are: when the range will be determined by the lines tangent to the cirumference which pass through the cockroach's starting point and when the range will be determined by the lines which pass through the cockroach's starting point and the points of intersection between the two circumferences. You can determine which case is this by comparing the length of the segment from the point of tangency to the cockroach's starting point (tLen) and r0.

In the first case, the angle can be determined through triangle similarity. In the second case, you may derive the equation from the triangle formed by the center of both circumferences and a point of intersection.

then what about this line, please help me understand it

Problem C :Can anyone please explain why am I getting WA on testcase 10 http://codeforces.com/contest/681/submission/18620917My code is giving tle on using normal for loop. But, replacing the same with "for(auto& p : ans)" gets the code accpeted.

My code:

Please Help.

is slow, because it flushes stdout each time used.

But should that be the reason for tle??

I have a problem with precision on problem E. I get WA on test 3. I have done it by hand, and it's ok, all the angles are fine. But apparently the precission is a little off...What would be the cause?

http://codeforces.com/contest/681/submission/19056708