Hello!

Tomorrow (the 3rd of November) will held the Nothern Subregion Quarterfinal 2012 in the Northeastern European Region.

I think, it will be very interesting to watch the "battle" between teams, because in our quarterfinal participate 3 persons from the top10 in Codeforces rating. And jury made all to make this quaterfinal very interesting and unpredictable.

Also, don't forget, that you can participate in Yandex.Contest.

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

Hello everybody! There is less than 3 hours before my second codeforces round, in which I participating as author. (The first one was — Codeforces Beta Round 56.) It will be llok like the previous one. (That was not bad, I wish. :-)!) I wish, you like today's contest.

I'm the author of this round, except one problem, which was proposed by Gerald.

In preparing this round was participating : Gerald (He always makes problems better.), cerealguy (Who helps in preparing, i think, the hardest problem of this round. He had solved the first version of round — and think, that it's easy.), Delinur (Who translate the problems). And also it was done with help of "Polygon" and "Codeforces".

I wish, you luck in this contest and to have high rating.

Problem scores will be as always. I wish, that problems are sorted well.

UPD: I'm very bad man, and have written wrong solution in problem "C". Problem under investigation.

Hi, all!

I'm the author of today's contest. On today's contest you will meet with a big amount of funny persons (or not only persons; :-)!), who had problems, and you should try to help them.

This Round was prepared with help of Rakhov Artem and Maria Belova.

Solutions.

I wish you high ratings!