Hi everyone. I'm trashfirstsearch, and I used to be blue...

Anyways, Codeforces Round #370 (Div. 2) will take place on 10 September 2016 at 19:35 MSK. As usual, Div.1 participants can join out of competition.

Much thanks to GlebsHP for helping me with preparing the contest, MikeMirzayanov for the Codeforces and Polygon platforms, and minimario and MCSPVMTT for testing problems.

This will be my first contest prepared on Codeforces, and I have prepared all the problems with the intent of making them interesting for everyone. It is, as usual, **strongly advised to read all the problems**.

Good luck, and I hope you will gain rating(and force someone else to lose it >:) ).

**Update**: Congratulations to the winners:

Div.1

Div.2

Here is the editorial.

I sincerely apologize for the problems during the contest. However, I hope everyone found the problems interesting! Thanks to everyone who participated and helped with the problems!

Round 370 clashes with Topcoder Wildcard Round and Round 372 clashes with Topcoder SRM 698. ;(

Oh come on! after long time we're having a CF contest and now it conflicts with another contest! such life! -_-

TOP 1 — CleverCoder 100 % INFO

TOP 2 — CleverCoder 100 % INFO

Good luck and high rating to all.....

Hope you prepare problems better than solve them

Brutal

Savage

Rekt

I want to upvote you again.

Bad luck For You :P

Good luck, and I hope you will gain rating(and force someone else to lose deep blue >:) ).

That one brought to you by the letter S, as in Snap!

Then we'll see if you can solve them all :)

He didn't participate. But he has more likes on his comment than the whole blog post. :P

Your face. God damn

Sadistic

"

and I used to be blue" is pretty unnecessary. everyone had a higher rating once (well, except tourist )Subregional ACM-ICPC in Brazil will be in same time ;(

i hope high ratings for all :)

at last a cf contest ):

It will be interesting to solve interesting problems with interesting solutions.

:DI love you, minimario :)

this contest will be good because minimario is test the problems :)

huh?

I love minimario too

I hope one day i can be a problem setter too :) :)

nowadays, anybody can be a problem setter (wish you be one :) )

Best of luck to all

I hope to be a pupil in this round XD

hope problems will be interesting ：）

After a long time.Hope everybody will increase rating.

better their rating should be increased who worked hard in this gap period..

.

Fuck ! why so much voting down !

Because you are suggesting the Setter to Set the problems. Well if you really want to assure that

Then please help the Setter and Make yourself an Unrated Contestant.

hope I can solve problem A & B this time

hope you solve A to D! a strong start!

Hope the queue will not be working slowly like on some previous contests

Well After A long time CF Today! Have to do Something Good B-)

Hi, for a few weeks the page is showing me this js errors:

enter:399 Uncaught SyntaxError: Unexpected token <

jquery-1.8.3.js:4680 Uncaught Error: Syntax error, unrecognized expression: href=#

or on anaother page:

contests:297 Uncaught SyntaxError: Unexpected token <It makes difficult to log in (once you are logged out), as the js stops to work, I had to submit the login form from js console manually.

Please also let me know where is better place to discuss such issues.

yes it happened with me also

strongly advised to read all the problems :) :)

After a long time there is back to back 3 CF rounds on 10,13 and 17 :)

I am back in business.

Whats the time duration for the contest?

2 hours, according to the contests page.

370 div 2 — (one hour + 5 minute)

Looking forward to interesting problems~ good luck && have fun!

+1s

I like the line "Hi everyone. I'm trashfirstsearch, and I used to be blue..." I hope that I will be blue after today's contest.

EDIT:I still wish to be BLUEI hoped about being purple. I almost got it but then the round was declared unrated.

I hope one day be a problem setter and say this sentence " Hi everyone. I'm

, and I used to be red :D ... "Ahmed Samyexcited for the roundAh

Delayed 10 Minutes

Unrated! ): I was doing pretty well this time too.

Old but goldOpen questions:

1) is P!=NP ?

2) What is the fastest algorithm for multiplication of two n-digit numbers?

3) Can the rotation distance between two binary trees be computed in polynomial time?

4) Will a day come in future that Codeforces server problems be permanently solved?

i don't know the answer for 1 & 2 & 3 but the last one my answer is impossible

CF issues aside, the problems were quite nice and interesting

Good luck, and I hope you will gain rating(and

force someone else to lose it)UnratedCan someone explain B?

take the count of l,r,d,u.

if((l+r+d+u)%2==1) ans is -1.

else

ans is (abs(l-r)+abs(u-d))/2;

Thanks! Awesome solution

why did you divide by two!

`(abs(l-r)+abs(u-d))/2;`

To me, just`abs(up-down) + abs(right-left)`

makes more sense! Any idea?!UPD: I got the idea, sorry for the inconvenience!

Assume that an L is a -1 while a R is a +1. Similarly for D and U. Find the absolute net vertical movement and the absolute net horizontal movement. There is three cases. Let vert = abs of vertical. hor = abs of horizontal then 3 cases are:

Case 1) vert==horizontal: Swap all horizontal to vert or all vert to horizontal, so answer is horizontal =vert Case 2) vert>horizontal: Two cases. Vert-horizontal is even or odd. If it is odd then answer is -1 because you can't make the odd go back to the origin. if they are even then the answer is (vert-horizontal)/2 + horizontal Case 3) Similar as case 2 but horizontal>vert. same logic.

Isn't it simpler just to output (

vert+hor) / 2 when the sum (vert+hor) if even, and output - 1 otherwise? In fact, solution is equal to yours, but a little bit shorter.Round is very very exiting, thanks! Only I hate probability in fifth task :P

P.S. I think I won't return in div 1 soon :D

Haven't solve problems for a week and did a bad job in this round. Luckily it's unrated.

Regardless of the server issues and the round being unrated, I have to say, the problemset is really interesting....

How to solve D? I managed to come up with DP solution but it was too slow(by factor of k) and I couldn't get the complexity down.

use partial sum

UPD: This approach will get TLE. I didn't pay attention to complexity. My bad.

Let

dp[i][j] be the number of ways of playingiturns such that first player receives atleastjextra points than second. Clearly answer would bedp[turns][b-a+ 1].For negative j, you can have another array

dp2.See my code

Okay, I did my dp iteratively and I guess by doing that I made too many unnecessary caluclations, but I tried doing it the same way, thanks!

isn't this

O(t*k*sum) ? Won't that be too slow?tags : offline increment, dp

let

`dp[i][j]`

be number of ways to gey sum`j`

after`i`

increments. for every`dp[i][j]`

we mast increment from`dp[i + 1][j - k]`

to`dp[i + 1][j + k]`

by`dp[i][j]`

. how to do it quicly in O(1). offline increment. just inc`dp[i + 1][j - k]`

and dec`dp[i + 1][j + k + 1]`

by`dp[i][j]`

. then for every`j (j > 0)`

`dp[i + 1][j] += dp[i + 1][j - 1]`

.so we have dp for

`A`

and for`B`

now let's find the answer. let's brute possible`A`

after`t`

increments and`if (dp[n][A] > 0) ans = ans + pref[A - 1] * dp[n][A]`

, where`pref[i]`

is prefix-sum of`dp[n]`

for`B`

that is all. so it works in

`O(t * mx)`

where mx is`t * k`

thank you for explanation. I didn't understood the editorial, but your solution seemed easier to understand

This is what I did; let me know if you need any clarifications: http://codeforces.com/contest/712/submission/20515549

It was a nice round.

I think that there should have been a testing round after changing the data center.

Problem A is harder then usually

First of all, contest frequency has greatly reduced. If CF is conducting a round after 10 days, then atleast there should be both Div1 and Div2 contests. The questions were really very nice. I didn't expect the quality to be this good. Hope to see more contests from you @trashfirstsearch.

why it is not rated it should be rated because the technical error involved all participants???

No, I don't think so. For example, when I can load problem A, contest has started more than 10 minutes and a lot of participants AC two first problems!

I want to share one amazing solution for the third task :

20512612

can u please explain it?

I can not explane, I got two unsaccessful hacks on it :D

but it is amazing!

Then how did it came to your mind? :/ I mean what was the approach?

That's not his solution.

Some people still upvoted his comment.

I do.

Let's invert the process and go from small triangle to big one.

Proposal: If we can go from (y,y,y) triangle to (p,q,r) in T steps, andmin(p,q,r) ≥x, then we can go from (y,y,y) to (x,x,x) in T steps (or less).Let's use following greedy strategy: if we have triangle (

a,b,c),a≤b≤c, we will change it to (b,c,b+c- 1).Proposal: if we start from (y,y,y) and use this strategy, afterT≥ 1 steps we will have (F_{T}(y- 1) + 1,F_{T + 1}(y- 1) + 1,F_{T + 2}(y- 1) + 1) (F_{T}being Fibonacci sequence). Proof: by induction.So when we reach

min(a,b,c) ≥x? Whenf_{T}(y- 1) + 1 ≥x. Asf_{T}is integer, we want . Linked solution finds exactly such T.Cool proof !

I understood relation wih Fibonnaci sequence very fast, but I couldn't put - 1 in any of my formulas :)

Basically all +1 and -1 are due to triangle inequality

a+b>cbeing equivalenta+b- 1 ≥cin integer case. Which in turn is equivalent to (a- 1) + (b- 1) ≥ (c- 1). This problem is equivalent to problem when we allow degenerate triangles (e.g.a+b=c) after substracting 1 everywhere, i.e. original problem for (x,y) is degenerate-allowed-problem for (x- 1,y- 1).Is there ever going to be a -1?

If x could be 1, then you could not proceed to any other triangle. But the contraint mentions that its not possible.

When x=1 => y=1 (As area is always positive). Answer=0, right? I know constraints don't have x=y=1, but even if there was, it can't be an invalid transformation.

I have added explanation below if you are interested.

Nice Problemset but don't like CF server failure :(

Problem E: Quite ironically, 'Memory' couldn't recall its gender

It's genderfluid, m8

Genuinely surprised by the amount of AC's in C and D respectively. It appeared to me that D was

mucheasier than C.Does C really feature a simple and elegant solution to it? I feel like a retard looking at the number of successful submissions for this problem.

Yes. You start backwards from (y,y,y) and take the smallest number and set it to sum of other two numbers-1.

Thanks. Never thought of looking at the problem that way :(

I agree with you. I think D is much easier than C. Simple solutions aren't necessarily easy.

Thank you trashfirstsearch! I like it!

I feel that pretest for C is weak.

Another UNRATED contest!

Recent CF server problem is really taking a toll on everything :/ It totally decreases the enthusiasm and interest of the contest. Last few contests were really nice but this server failure is becoming a frequent issue now. I think the CF team should look into the matter and try to solve this quickly :(

How much time system testing takes ?

Codeforces servers

what does this circuit do?

Cooks potatoes

you know that you can use potatoes as a batteries, I once did that on a university project, but the circuit caught me curiosity, I am interested in such things, if you can understand what i mean :3

Can someone explain problem C. I tried a greedy solution but obviously it didn't pass even the third test case given so I didn't submit. Is it solved by DP?

you need the minimum number of steps to transfer an equal sides triangle to another equal sides triangle with length y and it has a greedy solution but in every step you should form a triangle so that a+b>c where a,b,c is the lengths of the sides

I did, but I got the wrong answer for test 3. (22,22,22) to (4,4,4) Using the greedy algorithm I got:

(22,22,22) (4,22,22) (4,19,22) (4,19,16) (4,13,16) (4,13,10) (4,7,10) (4,7,4) (4,4,4) but this solution takes 8 seconds not 6, the optimal solution.

You should make (x, x, x) from (y, y, y) using triangle inequality, it's a lot easier

Not sure if it's right or not but you can pass pretests by using the same approach with all possible values for the first side.

http://codeforces.com/contest/712/submission/20509385

It fails for 100000 3

Your code : 26

Actual : 25

Yep, it didn't pass system tests

You start backwards from (y,y,y) and take the smallest number and set it to sum of other two numbers-1. :P

Why is this correct? I thought of this solution but didn't write it because I couldn't prove it was correct.

once u go from x to y, then u will figure out that this method is reverse of method y to x. it is like greedy. :)

Yeah I was hung up on trying to prove it too & I couldn't, but I wrote it anyway since it felt right. Here's a proof I have afterwards, it's a bit convoluted but main idea is just that each triangle in the reverse process is the biggest possible:

Let's always express a triangle is a triple [a,b,c] with a <= b <= c.

Note first that it doesn't matter which way we go: the optimal number of modifications will be the same going from [x,x,x] to [y,y,y] as with [y,y,y] to [x,x,x].

We'll compute the [y,y,y] to [x,x,x] sequence.

The procedure is to start from [a,b,c] = [y,y,y] and then each step you transform triangle [a,b,c] into [a',b',c'] = [b,c,b+c-1]. You keep going till the maximum side length is >= x. The answer is (# of transformations)+2.

A sequence of modifications that achieves this answer: do the same sequence of transformations, except in the last step, make the largest side x (instead of whatever b+c-1 >= x). Then in additional steps, modify the other 2 sides to equal x.

Proof this answer is optimal:

Property: our transformation [a,b,c]->[b,c,b+c-1] generates the "biggest" of all possible triangle that can result from modifying [a,b,c].

That is, any triangle [d,e,f] that can be produced by legally modifying some side of [a,b,c] is "smaller" than our transformed triangle [b,c,b+c-1]:

d <= b, e <= c, f <= b+c-1.

Formally, this property is true because you're only allowed to change one side per step. So at least two of the the original sides of the triangle must remain in the new triangle: this means d <= b and e <= c. (to be sure of this you can check all three cases: a & b remain, a & c remain, or b & c remain: in any of the cases, the smallest side must be <= b, and the second smallest must be <= c).

To bound f, we can use the triangle inequality & the bounds we have for d & e:

f <= d+e-1 <= b+c-1.

So [b,c,b+c-1] is indeed the biggest possible new triangle.

Applying this property inductively, we see that the triangle produced after k of our transformations from a start triangle [y,y,y] is larger than any other triangle that could have been produced after k modifications from [y,y,y] (any other sequence of k modifications will produce a smaller triangle at each step)

Now we can show that (# transformations)+2 is optimal for [y,y,y] to [x,x,x] with x > y: let k be the number of transformations we did in our process.

By the optimality of the triangle in step k-1, we know that any triangle that is k-1 modifications from [y,y,y] has maximum side < x. This means you need at least (k-1)+3 = k+2 steps to get to [x,x,x]: after any k-1 steps, each side is strictly smaller than x; so then you're going to need at least one extra modification on each side to get to [x,x,x], which is >=3 extra modifications overall; so at least (k-1)+3=k+2 modifications are required to get to [x,x,x], which is what we wanted.

just do brute force...

define all sides=y... increase the smallest sides by maintaining positive area.. while akk the sides are not x, do this operation..thats it..

I did greedy . start with triangle of side Y and in every move pick the shortest side and set it to min(X,sum of other two sides-1) . Break when one of the sides reach X .

Try the greedy solution from backwards.I mean try to get (x,x,x) from (y,y,y). Here is my code : http://codeforces.com/contest/712/submission/20513444

It can be solved simply by taking kinda Fibonacci nos. type of approach.Something Like

arr[i]=arr[i-1]+arr[i-2]-1

It's trivial that a+b<c for a valid triangle, at any time during the transition phase. And, trivially it's observable that whether I go from larger to smaller triangle or vice versa the answer is the same. Hence, if the input is

28 3 The sequence shall be :

3 3 5 7 11 17 28

Rest, is here ..

http://codeforces.com/contest/712/submission/20508329

I don't have formal proof, but, I thought of this in this way.

The problem states that the length of triangle would start from "3".

Suppose if the starting triple is (x,y,z) and basing on triangle inequality, we have, x+y>z y+z>x x+z>y

We took x to be 'y+z-1'

Substituting this value of x in x+y>z and x+z>y, we have 2y+x+z-1>z and y+2z-1>y which will always hold true given the contraints.

and similarly for y and z also.

I think problem E can be solve by SegmentTree. Each node[L, R] consider x is probability dominate [L, R], y is probability to start at R finish by winning at R and never lose at L, then the formula we need to merge two nodes a, b is:

result.x=a.x*b.x/ (1 -a.y+a.y*b.x),result.y=b.y+ (1 -b.y) *a.y*b.x/ (1 -a.y+a.y*b.x).I can confirm for result.x:

which is

which simplyfies to precisely your formula.

I can confirm for result.y too, since it is based on the same reasoning for result.x. Nice idea!

bop turad.

the problems are very nice,but Unfortunately.it's unrated..what a pity...anyway,thanks for prepare the problems

Is it possible to solve 712D - Memory and Scores using Irwin-Hall distribution?

When will pending system testing end ?

If you click on the "problems" tab, the testing progression will show on the right — that should give you some gauge. Generally it also hangs up for a bit when it reaches 100%.

I was about to finish writing Sqrt Decomposition solution for E, but I didn't make it. ;(

I was a bit delayed with DIV2-D because I don't understand the behavior of MOD very well. I initially applied it in cases where it should not be (in some of the intermediate calculations).

Can someone share any resources (or explain themselves) briefly how we should think about MOD-ding results? If there are some clear rules, e.g. "MOD-ding in cases X, Y, Z will affect the final result (e.g. if you just MOD-ded the final result after doing all the calculations, it would be different), so don't do it, but in cases A, B, C it's fine" — those would be helpful to know.

problems was good.. plz post the editorial :)

Can Div2. D be solved using a top-down dp?

Auto comment: topic has been updated by trashfirstsearch (previous revision, new revision, compare).Auto comment: topic has been updated by trashfirstsearch (previous revision, new revision, compare).Pretty interesting problems where I have learned a lot. Maybe it will be more funny when it's rated? :)

Can someone explain, how's number of games played will be (2*k+1)^(2*t) ??

It's (2*k+1) choices for every player in every turn. Hence that number.

2tbecausetis for each player. Therefore, at the end of the game, the number of ways to choose will be like this:[ (2k+1)*(2k+1) ] * [ (2k+1)*(2k+1) ] * ......

ttimes*2k +

1* because we must separately count0.such fucky

Can i ask when am i rated? I want to get my color:(