Aksenov239's blog

By Aksenov239, 7 years ago, translation, , 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". Tutorial of Codeforces Round #118 (Div. 2) Tutorial of Codeforces Round #118 (Div. 2) Tutorial of Aksay Training Camp Div. 1 - Day 3 Comments (7)
 » For some time links for solutions isn't working. Temporarily:А div. 2 — http://pastie.org/3884140B div. 2 — http://pastie.org/3884143A div. 1 — http://pastie.org/3884145B div. 1 — http://pastie.org/3884147D div. 1 — http://pastie.org/3884149E div. 1 — http://pastie.org/3884152
 » great tutoriAL!!!!!!!!!!
 » I just think cf need to save the draft as I accidently click on some link and the content is lost……I may need to borrow a book about number theory……and at last……I just can't understand the product in C(Div.1) a rookie
•  » » Try this: Multiply LHS by "k^(2^l) — 1" and get: (k^(2^l) — 1) (k^(2^l) + 1) ... (k^(2^r) +1) Repeatedly apply the identity: (a — b)(a + b) = a^2 — b^2 (for every first two terms)
 » (I accdiently posted in russian and I can't see my comment, I'm sorry for people who see this comment twice)I did the math for div 1 B and got: x = (aB/(a+b+c))^(a+b+c) y = (bB/(a+b+c))^(a+b+c) z = (cB/(a+b+c))^(a+b+c)I cant find the movtivation of why we get rid of the power to get the real answer.
 » 4 years ago, # | ← Rev. 5 →   A (Div 1) : simple explain suppose : up -> num of upward triangle and down -> num of downward triangle Initially : up = 1 and down = 0 then up = 3 and down = 1 then up = 10 and down = 6 then up = 36 and down = 28 then up = 136 and down = 120 and so on ... conculsion : each n we split each triangle to 4 triangles it's mean at n we have 4^n triangle we want to want how many of 4^n are upward suppose : a -> num of upward triangle b -> num of downward triangle it's mean a + b = 4^n ----------------------> (1) fact : at n=0 , up = 1 and down = 0 then at n=1 , up = 3 and down = 1 ratio is 3/1 then at n=2 , up = 10 and down = 6 ratio is 5/3 then at n=3 , up = 36 and down = 28 ratio is 9/7 then at n=4 , up = 136 and down = 120 ratio is 17/15 and so on ... conculsion : we see that ration of upward / downward => (2^n)+1 / (2^n)-1 so : a' = [ (2^n)+1 ] , b' = [ (2^n)-1 ] -------> (2) so : a'c + b'c = 4^n ----------------------> (3) such that c is constant we want to know a'c ? also we see that sum of a' + b' = [ (2^n)+1 ] + [ (2^n)-1 ] , a' + b' = [ (2^n)+1 + (2^n)-1 ] , a' + b' = [ 2*(2^n) ] , a' + b' = [ 2^(n+1) ] ------------------> (4) from (2) : a' = [ (2^n)+1 ] , b' = [ (2^n)-1 ] from (3) : a'c + b'c = 4^n we want to know a'c ? [ a' + b' ] * c = 4^n from (4) : a' + b' = [ 2^(n+1) ] [ 2^(n+1) ] * c = 4^n so c = 4^n / 2^(n+1) c = 2^(2n) / 2^(n+1) a'c = [ (2^n)+1 ] * 2^(2n) / 2^(n+1) a'c = [ 2^(3n) + 2^(2n) ] / 2^(n+1) a'c = 2^(2n-1) + 2^(n-1)
 » I solved Div1 B using Lagrange's Multiplier .L(x,y,z,lamda)=x^a*y^b*z^c-lamda*(x+y+z-s) and then partially differentiating w.r.t x,y,z and equating to 0 gives x=a*s/(a+b+c) y=b*s/(a+b+c) z=c*s/(a+b+c)