### send_nodes's blog

By send_nodes, history, 3 years ago, ,

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!

• +264

 » 3 years ago, # |   +45 Round 370 clashes with Topcoder Wildcard Round and Round 372 clashes with Topcoder SRM 698. ;(
•  » » 3 years ago, # ^ |   +24 Oh come on! after long time we're having a CF contest and now it conflicts with another contest! such life! -_-
•  » » » 3 years ago, # ^ |   -7 TOP 1 — CleverCoder 100 % INFO
•  » » » » 3 years ago, # ^ |   +23 TOP 2 — CleverCoder 100 % INFO
 » 3 years ago, # | ← Rev. 2 →   -19 Good luck and high rating to all.....
 » 3 years ago, # |   +257 Hope you prepare problems better than solve them
•  » » 3 years ago, # ^ |   +106 Brutal
•  » » » 3 years ago, # ^ |   +60 Savage
•  » » » » 3 years ago, # ^ |   +78
•  » » » » » 3 years ago, # ^ |   +15 I want to upvote you again.
•  » » » » » » 3 years ago, # ^ |   0 Bad luck For You :P
•  » » 3 years ago, # ^ |   +18 Good luck, and I hope you will gain rating(and force someone else to lose deep blue >:) ).
•  » » 3 years ago, # ^ |   +5 That one brought to you by the letter S, as in Snap!
•  » » 3 years ago, # ^ |   +108 Then we'll see if you can solve them all :)
•  » » » 3 years ago, # ^ |   0 He didn't participate. But he has more likes on his comment than the whole blog post. :P
•  » » 3 years ago, # ^ |   +5 Your face. God damn
•  » » 3 years ago, # ^ |   0 Sadistic
 » 3 years ago, # |   -58 " and I used to be blue " is pretty unnecessary. everyone had a higher rating once (well, except tourist )
 » 3 years ago, # |   +8 Subregional ACM-ICPC in Brazil will be in same time ;(
 » 3 years ago, # |   0 i hope high ratings for all :)
 » 3 years ago, # |   0 at last a cf contest ):
 » 3 years ago, # | ← Rev. 2 →   0 It will be interesting to solve interesting problems with interesting solutions. :D
 » 3 years ago, # |   -11 I love you, minimario :)this contest will be good because minimario is test the problems :)
•  » » 3 years ago, # ^ |   +49 huh?I love minimario too
 » 3 years ago, # |   +11 I hope one day i can be a problem setter too :) :)
•  » » 3 years ago, # ^ | ← Rev. 3 →   +1 nowadays, anybody can be a problem setter (wish you be one :) )
 » 3 years ago, # |   0 Best of luck to all
 » 3 years ago, # |   0 I hope to be a pupil in this round XD
 » 3 years ago, # |   0 hope problems will be interesting ：）
 » 3 years ago, # |   0 After a long time.Hope everybody will increase rating.
•  » » 3 years ago, # ^ |   0 better their rating should be increased who worked hard in this gap period..
 » 3 years ago, # | ← Rev. 2 →   -63 .
•  » » 3 years ago, # ^ |   -42 Fuck ! why so much voting down !
•  » » » 3 years ago, # ^ | ← Rev. 2 →   -16 Because you are suggesting the Setter to Set the problems. Well if you really want to assure that Problem A should be off Math . Problem B should be off Implementation . Problem C should be off Two Pointer / BS . Then please help the Setter and Make yourself an Unrated Contestant.
 » 3 years ago, # |   +1 hope I can solve problem A & B this time
•  » » 3 years ago, # ^ |   +10 hope you solve A to D! a strong start!
 » 3 years ago, # |   +1 Hope the queue will not be working slowly like on some previous contests
 » 3 years ago, # |   +1 Well After A long time CF Today! Have to do Something Good B-)
 » 3 years ago, # | ← Rev. 3 →   0 Hi, for a few weeks the page is showing me this js errors:enter:399 Uncaught SyntaxError: Unexpected token
•  » » 3 years ago, # ^ |   0 yes it happened with me also
 » 3 years ago, # |   +5 strongly advised to read all the problems :) :)
 » 3 years ago, # |   0 After a long time there is back to back 3 CF rounds on 10,13 and 17 :)
 » 3 years ago, # |   0 I am back in business.
 » 3 years ago, # |   0 Whats the time duration for the contest?
•  » » 3 years ago, # ^ |   +1 2 hours, according to the contests page.
•  » » » 3 years ago, # ^ |   0 370 div 2 — (one hour + 5 minute)
 » 3 years ago, # |   +11 Looking forward to interesting problems~ good luck && have fun!
•  » » 3 years ago, # ^ |   +15 +1s
 » 3 years ago, # | ← Rev. 2 →   +10 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 BLUE
•  » » 3 years ago, # ^ |   +3 I hoped about being purple. I almost got it but then the round was declared unrated.
 » 3 years ago, # |   -20 I hope one day be a problem setter and say this sentence " Hi everyone. I'm Ahmed Samy, and I used to be red :D ... "
 » 3 years ago, # |   0 excited for the round
•  » » 3 years ago, # ^ |   0 Ah
 » 3 years ago, # |   +4 Delayed 10 Minutes
 » 3 years ago, # |   +2 Unrated! ): I was doing pretty well this time too.
 » 3 years ago, # |   +83 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?
•  » » 3 years ago, # ^ |   0 i don't know the answer for 1 & 2 & 3 but the last one my answer is impossible
 » 3 years ago, # |   +16 CF issues aside, the problems were quite nice and interesting
 » 3 years ago, # |   +2 Good luck, and I hope you will gain rating(and force someone else to lose it ) Unrated
 » 3 years ago, # |   +1 Can someone explain B?
•  » » 3 years ago, # ^ |   +2 take the count of l,r,d,u. if((l+r+d+u)%2==1) ans is -1.elseans is (abs(l-r)+abs(u-d))/2;
•  » » » 3 years ago, # ^ |   0 Thanks! Awesome solution
•  » » » 3 years ago, # ^ | ← Rev. 3 →   0 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!
•  » » 3 years ago, # ^ |   +6 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.
•  » » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # | ← Rev. 2 →   +1 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
 » 3 years ago, # |   0 Haven't solve problems for a week and did a bad job in this round. Luckily it's unrated.
 » 3 years ago, # |   +10 Regardless of the server issues and the round being unrated, I have to say, the problemset is really interesting....
 » 3 years ago, # |   +1 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.
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 use partial sum
•  » » » 3 years ago, # ^ | ← Rev. 5 →   -9 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 playing i turns such that first player receives atleast j extra points than second. Clearly answer would be dp[turns][b - a + 1].For negative j, you can have another array dp2.See my code
•  » » » » 3 years ago, # ^ |   0 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!
•  » » » » 3 years ago, # ^ |   +6 isn't this O(t * k * sum) ? Won't that be too slow?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +13 tags : offline increment, dplet 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 Bthat is all. so it works in O(t * mx) where mx is t * k
•  » » » 3 years ago, # ^ |   0 thank you for explanation. I didn't understood the editorial, but your solution seemed easier to understand
•  » » 3 years ago, # ^ |   0 This is what I did; let me know if you need any clarifications: http://codeforces.com/contest/712/submission/20515549
 » 3 years ago, # |   +4 It was a nice round.I think that there should have been a testing round after changing the data center.
 » 3 years ago, # |   0 Problem A is harder then usually
 » 3 years ago, # |   +12 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.
 » 3 years ago, # |   0 why it is not rated it should be rated because the technical error involved all participants???
•  » » 3 years ago, # ^ |   +1 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!
 » 3 years ago, # | ← Rev. 2 →   +23 I want to share one amazing solution for the third task :20512612
•  » » 3 years ago, # ^ |   +3 can u please explain it?
•  » » » 3 years ago, # ^ |   +7 I can not explane, I got two unsaccessful hacks on it :D but it is amazing!
•  » » » » 3 years ago, # ^ |   +1 Then how did it came to your mind? :/ I mean what was the approach?
•  » » » » » 3 years ago, # ^ |   +11 That's not his solution.
•  » » » » » » 3 years ago, # ^ |   0 Some people still upvoted his comment.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +6 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, and min(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, after T ≥ 1 steps we will have (FT(y - 1) + 1, FT + 1(y - 1) + 1, FT + 2(y - 1) + 1) (FT being Fibonacci sequence). Proof: by induction.So when we reach min(a, b, c) ≥ x? When fT(y - 1) + 1 ≥ x. As fT is integer, we want . Linked solution finds exactly such T.
•  » » » » 3 years ago, # ^ |   0 Cool proof !I understood relation wih Fibonnaci sequence very fast, but I couldn't put  - 1 in any of my formulas :)
•  » » » » » 3 years ago, # ^ |   0 Basically all +1 and -1 are due to triangle inequality a + b > c being equivalent a + b - 1 ≥ c in 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).
•  » » 3 years ago, # ^ |   0 Is there ever going to be a -1?
•  » » » 3 years ago, # ^ |   0 If x could be 1, then you could not proceed to any other triangle. But the contraint mentions that its not possible.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 3 years ago, # ^ |   0 I have added explanation below if you are interested.
 » 3 years ago, # | ← Rev. 4 →   0 Nice Problemset but don't like CF server failure :(
 » 3 years ago, # |   +81 Problem E: Quite ironically, 'Memory' couldn't recall its gender
•  » » 3 years ago, # ^ |   +5 It's genderfluid, m8
 » 3 years ago, # |   0 Genuinely surprised by the amount of AC's in C and D respectively. It appeared to me that D was much easier 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.
•  » » 3 years ago, # ^ |   +5 Yes. You start backwards from (y,y,y) and take the smallest number and set it to sum of other two numbers-1.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Thanks. Never thought of looking at the problem that way :(
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I agree with you. I think D is much easier than C. Simple solutions aren't necessarily easy.
 » 3 years ago, # |   0 Thank you trashfirstsearch! I like it!
 » 3 years ago, # |   +1 I feel that pretest for C is weak.
 » 3 years ago, # | ← Rev. 2 →   +4 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 :(
 » 3 years ago, # |   0 How much time system testing takes ?
 » 3 years ago, # |   +227 Codeforces servers
•  » » 3 years ago, # ^ |   0 what does this circuit do?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Cooks potatoes
•  » » » » 3 years ago, # ^ |   0 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
 » 3 years ago, # |   +4 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?
•  » » 3 years ago, # ^ |   0 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
•  » » » 3 years ago, # ^ |   0 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.
•  » » » » 3 years ago, # ^ |   0 You should make (x, x, x) from (y, y, y) using triangle inequality, it's a lot easier
•  » » » » 3 years ago, # ^ |   0 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
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +4 It fails for 100000 3Your code : 26Actual : 25
•  » » » » » » 3 years ago, # ^ |   0 Yep, it didn't pass system tests
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 You start backwards from (y,y,y) and take the smallest number and set it to sum of other two numbers-1. :P
•  » » » 3 years ago, # ^ |   0 Why is this correct? I thought of this solution but didn't write it because I couldn't prove it was correct.
•  » » » » 3 years ago, # ^ |   0 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. :)
•  » » » » 3 years ago, # ^ |   +1 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.
•  » » 3 years ago, # ^ |   0 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..
•  » » 3 years ago, # ^ |   +1 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 .
•  » » 3 years ago, # ^ |   0 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
•  » » 3 years ago, # ^ |   +4 It can be solved simply by taking kinda Fibonacci nos. type of approach.Something Like arr[i]=arr[i-1]+arr[i-2]-1It's trivial that a+b
•  » » 3 years ago, # ^ |   0 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>yWe 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.
 » 3 years ago, # | ← Rev. 3 →   +17 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).
•  » » 3 years ago, # ^ |   +3 I can confirm for result.x: _result.x = ax*bx * (1 + (1-bx)*ay + [(1-bx)*ay]^2 + ...)_ which is _result.x = ax*bx * Lim(k-->+inf){ [1-((1-bx)*ay)^(k+1)] / (1-ay+bx*ay) }_ which simplyfies to precisely your formula.
•  » » 3 years ago, # ^ |   0 I can confirm for result.y too, since it is based on the same reasoning for result.x. Nice idea!
 » 3 years ago, # |   +3 bop turad.
 » 3 years ago, # |   0 the problems are very nice,but Unfortunately.it's unrated..what a pity...anyway,thanks for prepare the problems
 » 3 years ago, # |   0 Is it possible to solve 712D - Memory and Scores using Irwin-Hall distribution?
 » 3 years ago, # |   0 When will pending system testing end ?
•  » » 3 years ago, # ^ |   0 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%.
 » 3 years ago, # |   0 I was about to finish writing Sqrt Decomposition solution for E, but I didn't make it. ;(
 » 3 years ago, # | ← Rev. 2 →   0 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.
 » 3 years ago, # |   0 problems was good.. plz post the editorial :)
 » 3 years ago, # |   +1 Can Div2. D be solved using a top-down dp?
 » 3 years ago, # |   0 Auto comment: topic has been updated by trashfirstsearch (previous revision, new revision, compare).
 » 3 years ago, # |   0 Auto comment: topic has been updated by trashfirstsearch (previous revision, new revision, compare).
 » 3 years ago, # |   0 Pretty interesting problems where I have learned a lot. Maybe it will be more funny when it's rated? :)
 » 3 years ago, # |   0 Can someone explain, how's number of games played will be (2*k+1)^(2*t) ??
•  » » 3 years ago, # ^ |   0 It's (2*k+1) choices for every player in every turn. Hence that number.
•  » » » 3 years ago, # ^ |   0 2t because t is 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) ] * ...... t times*2k + 1 * because we must separately count 0.
 » 3 years ago, # |   0 such fucky
 » 3 years ago, # |   0 Can i ask when am i rated? I want to get my color:(