Aksenov239's blog

By Aksenov239, 12 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +34
  • Vote: I do not like it

By Aksenov239, 13 years ago, translation, In English

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

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

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

Full text and comments »

  • Vote: I like it
  • +53
  • Vote: I do not like it

By Aksenov239, 13 years ago, translation, In English

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.

Full text and comments »

  • Vote: I like it
  • +26
  • Vote: I do not like it

By Aksenov239, 14 years ago, translation, In English
Problem A. Solution - O(n2)
We take phrase and parse it. Mark all cells, that obviously didn't match - O(n). In the end we go through the array and count all unmarked cells.
If 0 - we print "-1", else - amount of unmarked cells.

Problem B. Solution - O(k × n × m)
We start BFS from given point. Go from cell to all 6 directions. The answer - number of visited cells.

Problem C. Solution - O(27 × n2)
We can see, that in connected component - if we know 1 number - then we know all others in component, because in each pare we know minimal and maximal
power of each primes. Because number of different primes in one number " <  = 1000000" is less, than 7, we can look over all possibilities of 1 number in connected compoment - and for each number, that we get, we check, that it suits.

How to check? We can notice, that if we know a, (a, b), [a, b], then , start DFS and check.

Problem D. Solution - O(max numebr).
We can notice, that each beautiful triplet has form - (x2 - y2, 2xy, x2 + y2). Now we can gen all such triples. For each triple, we watch - if we have more than 1 number in given set - we union them.

How to gen all the triples?

x > y.
. This means, that .
Now for gen all this triples we an take - и . The number of iterations - .

what means - "union"?
We take a data structure named DSU. If two number belong to one beautiful triple - they are connected with edge, in our situation - we can union corresponding to them unions.

Problem E. Solution - O(n + log(xy)).
We can see, that after one minute the sum changes - it multiply on 3, and substract first and last elements of sequence. Because of that we can count of sum with help of power of matrix.

What happens after sorting.

First number stay on his place. On the last place - Fxan + Fx - 1an - 1. Where n - number of elements, ans Fx - x Fibonacci number - with F - 1 = 0 and F0 = 1.

This means - that we can count the last number with matrix too.

After that we use the first idea.

If you have questions - ask them.

Full text and comments »

  • Vote: I like it
  • +66
  • Vote: I do not like it

By Aksenov239, 14 years ago, translation, In English

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!

Full text and comments »

Announcement of Codeforces Beta Round 56
  • Vote: I like it
  • +153
  • Vote: I do not like it