Actually, there should be no difference for you: in which round to participate. Except the fact, that if you'll write official one, you'll have chances to pass to the next round.

Bro! it's round 409 actually. :D All the Best

Именно так.

And the F1 Grand Prix!

You can win wildcard round, similar to winning Europa League for League Champions ticket :)

I'm glad that man utd won otherwise i would have regret missing the contest. GGMU

You are lucky :P

yes

All three rounds last 2 hours, and all are rated.

You did it!

Click the third "Before contest"'s "Register now »" to join it. Have fun!

May be you are out of contest....:)

I was trying to find the bug of someone's code but I couldn't find it :(

How to solve D?

I think the writer's goal is to increase letters V and K as he can :D

Binary Search

Imagine that there is no charger. Then your answer would be the min(b[i] / a[i]). (The one that finishes faster).

But the charger makes you able to add this b[i]. So Binary Search the answer.

When you are checking if they can last x seconds or not, you will need to sum needed = sum(max(0, x — (b[i] / a[i])) * a[i]), which is the energy needed by everyone to last x seconds. and if needed <= stay * p then you can charge them and make them last <= x seconds.

BTW max(0, x — (b[i] / a[i])) is the how much time we need to add to the ith device to complete at least x seconds.

Point-line distance

Binary search on the time. Calculate how much under 0 each device will go if it runs without charger for t seconds.

If the sum of these values that go under is less than or equal to the capacity of the charger * t then that time is valid and you should try a higher one. Otherwise go lower. At least I think that'll work.

How did you find it?

Imho, that problem differs from today's very much

this happened because someone hacked it before u and was waiting in the queue for a longer time than u were. u didnt get negative because the problem was already hacked by someone else before so ur hack was not taken into consideration

True

I did nearly the same and passed pretests. Did you consider n,1,2 and n-1,n,1?

Maybe you have forgotten about first and last points, because my solution is same.

You also need to to halve the distance between two consecutive points.

Edit: That distance is actually never optimal. Explanation Here.

If it's point i, then you have to check it's distance from the line (i-2, i-1) and (i+1,i+2) line also. I did it, maybe it's still not sufficient, or my implementation was bad, but I failed on pretest 4.

You also have to take the minimum of half of each polygon side lengths. Because if somehow the radius is bigger than half of a side, you can move two ends of that segment making the polygon intersect itself.

Edit: forget it.

I binary searched the answer, checking if its possible the same way as you described. At least it passed pretests)

P.S. Maybe you forgot about p[0], p[n — 1], p[n — 2] or smtj like that?

I did the same thing and it passed. Maybe you initialized the answer wrong. The maximum possible distance was 10^9*sqrt(2)/2.

Probably precision issues. I did the same, for some reason it was accepted after I output the answer with "cout << setprecision(10) << ans << endl;".

By default, cout outputs 6 digits after the decimal point, which I thought would be just enough, so I'm not sure why this changed the verdict though...

thanks for replies, guys :)

I was considering i, (i + 1) % n, (i + 2) % n, so indexes are not the case. Well, now I am confused, might be precision issues, but at least I know the approach wa correct)

Mine failed pretests with double, but passed with long double in C++11.

https://math.stackexchange.com/questions/2149600/prove-ax-equiv-b-mod-m-iff-b-equiv-0-mod-gcdm-a/2149624

You can go from a prefix product x to some other prefix product y if and only if gcd (x, M) | gcd (y, M). (that is, there exists a number z so that x * z % M = y if this condition holds). Now, for each value d | M, you can keep cnt[d] the number of numbers q that have gcd (q, M) = d and do not appear in the given list and some dynamic programming. If we write down the numbers gcd (prefix_product[i], M), we'll get some clusters (contiguous groups with the same value). You can keep dp[d] the maximum length of an array whose last element q has gcd (q, M) = d. There are few divisors for M<=200.000 (160 in worst case), so we can compute the dp in complexity O(number_of_divisors^2). In order to get some z for given x and y so that (x * z) % M = y, you should use modular inverse. To better understand it, look at the numbers' decomposition. Take care at the fact that the modular inverse of a number t is defined if and only gcd (t, M) = 1

First try to find max prefix modulo sequence. Prefix modulo should hold condition that gcd(pre[i],m) is divisible by gcd(pre[i-1],m)

Using that condition,by dp we can find prefix modulos and then some inverse modulo operations on it gives the sequence

Here is my submission

on both languages!

same

In Div1 D, I finished coding but the first example didn't work. After contest I found that I calculated G(0) + G(1) + ... + G(999999) instead of G(0) ^ G(1) ^ ... ^ G(999999)..........

the cf is too hate you

Maybe you need better online judge！

Do u know any reason y??

It doesn't look so. What will be the chain of factors for this input:
3 10
2 9 1

It's interesting that how he can be in same room with his fake account, is it just coincidence or there is a trick :D ?

I think it should be around max(n)*max(initial_power). I dont have a proof but I generated some test cases and they gave me this idea

I used 10^20, it was enough. I think the bound is somewhere like 10^10, if you consider that all n (10^5) devices lose 1 power per time unit, (goes out after 10^5) then it's 10^5*10^5=10^10.

KK

Instead of f(S)=x consider f(S) ># x where a ># b off a's i-th digit is larger or equal to B's i-th digit for every i. To compute it and to get actual result from this auxiliary results do something similar to Fast Subset Convolution.

Zoomed screen 300%, still can't see picture :D

Думаю это из-за right-left>eps.

У тебя бесконечный цикл.

Div.1 — A. Test — 74 :(