No problem was specially taken from "Wikipedia". For me it's really hard to understand, that problem "B" was there.
If the lengths of 2 strings aren't equal — that means "NO". We try to find the positions in strings, where chars are different. If there 1 or more than 2 such positions — "NO". After that we swap 2 characters in the first string, and check for their equality.
- We can see, that we can do all in integers, because k is integer number of percent.
- For each dwarf we should find his optimal strategy — to check 2 strategies with speed.
- We should sort them.
A (Div 1). (Idea : Aksenov239, realization : Aksenov239, code : 1652592) Let's propose, that after the i-th year, there is x triangles up and y triangles down. After another iteration we can see, that amount of triangles became — 3x + y up and x + 3y down. Let's see the difference between them: at the i-th it's x - y and at the i + 1-th — it's (3x + y) - (x + 3y) = 2 * (x - y). We can see, that difference between amount of triangles grown up by 2. Because on the i-th year the difference became 2i and all amount of triangles is 4i. We can see, that on the i-th year the number of our triangles is . That can be computed by modulo p using the fast-power algorithm.
Prove: . (This is AM-GM inequality. Link for whom don't know it.)
The equality becomes only, when .
And you should check on zeroes. If a = b = c = 0 — you can choose any good answer — x + y + z ≤ S.
C (Div 1). No comments. :-)!
This is number theory problem.
I'm trying to explain it step by step:
1) Let's prove, that LCD is maximum 2.
Let . Squaring both sides we get , but we want to . This means, that d can be only 2.
2) Let's make this lenghty product simplier.
We can count this by modulo p fast, and divide it by 2r - l, if k is odd.
3) There is many interesting things in this solution.
Firstly, it doesn't work, when p = 2 — but it can easily done by you.
The other problem is harder, what if , this means that for each i ≥ l : , and this mean,
that for each i ≥ l : k2i + 1 ≡ p2. And the product by modulo p is equal to 2r - l + 1.
This problem wasn't taken to ROI, because of that I gave it here. This is pretty hard problem. I can't now realize, what cerealguy wrote, but his solution is O(nlogn) — without binary search. For me it's quite hard to understand, because my first solution was with binary search. And there were solutions, that has a worse asymptothic, but they run faster.
Because of that I can only give you key ideas, that can help you. (afterwards you can see the code of cerealguy)
- Let's find for each person the nearest subway point for them. It can be done in nlogn with use of segment tree or something else.
- We can see, that if one person goes to subway, the others, which distance to subway is smaller, can go to subway too — it doesn't affect the answer. Because of that we sort all persons by their distanse to subway.
- The area of the person, where he can come in t seconds, is romb. And we can intersect all rombes in O(n) — the intersection is like rectangle.
- Let's make the first intersection. When nobody goes to subway. We get a rectangle.
- The main idea, that for this rectangle — the nearest subway becomes always the same. We go throught people in sorted order, we can fast recalculate this small rectangle — and because of that we can fast recalculate the answer.
And we get a solution in O(nlogn) time. Ta-dams.
Thank you all for your attention. I'm deeply sorry about the problem "C".