No problem was specially taken from "Wikipedia". For me it's really hard to understand, that problem "B" was there.

A (Div 2). (Idea : Gerald, realization : Aksenov239, code : 1670635)

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.

B (Div 2). (Idea : Aksenov239, realization : Aksenov239, code : 1670637)

1. We can see, that we can do all in integers, because k is integer number of percent.
2. For each dwarf we should find his optimal strategy — to check 2 strategies with speed.
3. 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 2ⁱ and all amount of triangles is 4ⁱ. 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.

B (Div 1). (Idea : Aksenov239, realization : Aksenov239, code : 1652597) This problem was made by my love to inequalities. :-)! The answer for this problem is .

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. :-)!

D (Div 1). (Idea : Aksenov239, realization : cerealguy, Gerald, Aksenov239, code : 1652604)

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 2^r - 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 : k²ⁱ + 1 ≡ _p2. And the product by modulo p is equal to 2^{r - l + 1}.

E (Div. 1) (Idea : Aksenov239, relization : cerealguy, code : 1652611)

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)

Ideas:

1. 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.
2. 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.
3. 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.
4. Let's make the first intersection. When nobody goes to subway. We get a rectangle.
5. 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".