### fcspartakm's blog

By fcspartakm, history, 17 months ago, translation,

Hello, Codeforces!

I'd like to invite you to Codeforces Round #592 (Div. 2). It'll be held on Sunday, October 13 at 12:05 MSK. Note that round starts in the unusual time!

The round will be rated for the participants with rating lower than 2100. The statements will be available in Russian and English.

This round is held on the tasks of the regional stage All-Russian Team Olympiad of Informatics 2019/2020 year in city Saratov. The problems were prepared by Ivan BledDest Androsov, Vladimir vovuh Petrov and me.

Great thanks to Ivan isaf27 Safonov for helping in preparing the contest, to Mike MikeMirzayanov Mirzayanov for the great Codeforces and Polygon platform and to Ivan CaseRuten Khudoshin, Ivan Ivan19981305 Georgiev, Leonid Peinot Mironov, Anton anon20016 Lebedev, Ksenia Pavlova Pavlova and Dmitriy dmitrii.krasnihin Krasnihin for writing solutions.

You will be given seven problems and two hours to solve them. The scoring distribution will be published soon. Good luck everyone!

UPD The scoring distribution 500-1000-1500-1750-2500-2500-3000

UPD Editorial

• +305

 » 17 months ago, # |   +125 I wish the round be nice without any DDOS attack, in queue or without any delaying, best of lucks.
•  » » 17 months ago, # ^ | ← Rev. 2 →   +120
•  » » » 17 months ago, # ^ |   +59 Thank you. Today there is no Queueforces, no DDOS attack, all statements are clear and also problems are good.
•  » » » » 17 months ago, # ^ |   -21 The only thing bad is your rank :P
•  » » » » » 17 months ago, # ^ |   0 Yeah, I make a lot of mistakes. But I am sure I will be learning a lot from them. Thanks.
•  » » 17 months ago, # ^ | ← Rev. 2 →   -36 ()
•  » » » 16 months ago, # ^ |   0 too koonet
•  » » » » 16 months ago, # ^ |   0 :|
•  » » 17 months ago, # ^ |   -28 Is it rated?
•  » » » 17 months ago, # ^ |   +31
 » 17 months ago, # |   0 Too early, again... But i_love_Vovuh
 » 17 months ago, # |   0 unusual time!
 » 17 months ago, # |   +37 A friendly time to Chinese.Hope this round will no DDOS.
•  » » 17 months ago, # ^ |   +1 Yep,but for me it is a right time to have supper,so maybe I'll be hungry solving the problems.
•  » » 17 months ago, # ^ | ← Rev. 2 →   +138 Even I'm Chinese, I still want the round to be later. The darkness has given me dark eyes, but I use them to find bugs.
•  » » » 17 months ago, # ^ |   -7 China is a good country...
•  » » » » 17 months ago, # ^ |   +1 I think so.
•  » » » 17 months ago, # ^ |   +4 Sounds interesting, but maybe you can change it into darkness...XD
•  » » » » 17 months ago, # ^ |   +10 Thanks. It's my fault.
•  » » » 17 months ago, # ^ |   0 I agree
•  » » 17 months ago, # ^ |   0 Thanks to the time,I can participate for an official contest after a long period of time.Thanks to the contest writers.
 » 17 months ago, # |   +20 Contest with unusual time, keeps the hackers from the crime <3. Hope a great contest for everyone!!
 » 17 months ago, # |   +1 Short problem statements, please!
 » 17 months ago, # | ← Rev. 2 →   +14 A friendly time … Hope this round will no DDOS. no queue & Compact statement.
 » 17 months ago, # |   -10 Hope this round will be no DDOS attack.
 » 17 months ago, # |   +12 Rated Div.2 and a friendly time to Chinese again!!!
 » 17 months ago, # |   +13 When contest will be start,open some problem in new window..May be it will be useful if DDOS attack happend.
•  » » 17 months ago, # ^ | ← Rev. 2 →   +12 You can simply just open the "Complete Problemset" page!
•  » » » 17 months ago, # ^ |   0 I was not familiar with this "Complete Statement" option.Thnx Bhi.
 » 17 months ago, # |   -6 Wish me good ratingI wish you all too.
•  » » 17 months ago, # ^ |   0 you too
 » 17 months ago, # |   +16 Score distribution?
 » 17 months ago, # |   +8 The Saratov olympiads are popular on Codeforces :)
 » 17 months ago, # |   +8 Score........... :3
 » 17 months ago, # |   -19 The comment removed because of Codeforces rules violation
 » 17 months ago, # |   0 How to solve B?
•  » » 17 months ago, # ^ | ← Rev. 2 →   +5 The solution is max{N, 2 * (N — positionOfTheFirstStaircase), 2 * (positionOfTheLastStaircase + 1)}
•  » » » 17 months ago, # ^ |   0 Is N really needed in the maximum comparison?
•  » » » » 17 months ago, # ^ |   +4 If there is no staircase the solution is N
•  » » » 17 months ago, # ^ |   0 Isn't answer for following 14? 12 000001100000 
•  » » » » 17 months ago, # ^ |   0 Actually, nevermind.
•  » » 17 months ago, # ^ |   0 I used BFS and start point is (floor,room)=(0,0)(0,s.size()-1)(1,0)(1,s.size()-1)
•  » » » 17 months ago, # ^ | ← Rev. 2 →   +1 No need to use BFS or DFS actually, the solution is always fixed, you can use two pointers on each end of array, then you decrease the n, when you see 1's on either side you do the followings;10000 or 00001 -> If 1's is at first or last means = n*2 (where n is array size)In other situations like following, answer is always decreasing;initially n = 5;00010 -> n = 4 here, ans = 2*n = 800100 -> n = 3 here, ans = 2*n = 601000 -> again n = 4 here, ans = 2*n = 8It does not matter how many 1's we have, the point is we need to have at least one 1's and position of 1's01110 -> again n = 4 here, ans = 2*n = 8
•  » » 17 months ago, # ^ |   0 there are only two possible cases either you start from leftmost room and use rightmost stair or start from rightmost room and use leftmost stair. ans is maximum of these two cases.
•  » » 17 months ago, # ^ |   -10 int t, n; string room; cin >> t; for (int i = 0; i < t; i++) { cin >> n; cin >> room; bool in = false; for (int i = 0, j = room.size() - 1; i <= j; i++, j--, n--) { //cout << "i: " << i << " j: " << j << endl; if (room[i] == '1' || room[j] == '1') { cout << n * 2 << endl; in = true; break; } } if(!in) cout << room.size() << endl; } 
 » 17 months ago, # |   +14 What on earth is test case 5 for C
•  » » 17 months ago, # ^ |   0 :(
•  » » 17 months ago, # ^ |   +4 I can totally feel you bro... i wrote a solution which worked for 10^6 test cases that I randomly generated using Chelper and my code passed without any error, but this case 5 totally took my life.
•  » » 17 months ago, # ^ | ← Rev. 2 →   +35 try this if you use exgcd approach:1000000000000 90000000000000007 100000 77777Answer should be899999922230 99991 99999977779My exgcd template failed on this because of long long overflow when multiplying
•  » » » 17 months ago, # ^ |   0 Nice catch! I got -1 in my implementation...
•  » » » 17 months ago, # ^ |   0 I am getting correct answer on your case, but still wa on 5 :(
•  » » » 17 months ago, # ^ |   0 Thanks for your sample so much. And how to use __int128 without Compilation error in Codeforces?
•  » » » » 17 months ago, # ^ |   0 me,too.I also got a Compilation error when I used __int128 to avoid the overflow with exgcd.And I also want to konw can we use __int128 in Codeforces?
•  » » » » 17 months ago, # ^ |   -8 Codeforces runs on 32-bit system so __int128 is not supported.In this problem __int64 is enough to get accepted, where an extra mod should be added. Here is my code. LL cal(LL a, LL b, LL c) { LL x, y; LL gcd = exgcd(a, b, x, y); if(c % gcd) return -1; b /= gcd; // x *= c/gcd; // wa x *= (c/gcd%b); // ac LL ans = (x%b+b)%b; return ans; } 
•  » » 17 months ago, # ^ |   +29 If you really want to solve that equation, maybe you could try something like this:The goal is to find the smallest possible $y$ such that $wx+dy=p$.We could first divide both $w$, $d$ and $p$ by $gcd(w, d)$ then $w$ and $d$ become coprimes.We take $mod\ w$ and the equation becomes something like $dy=p \ (mod\ w)$. Thus $y=p\times {d}^{-1}\ (mod\ w)$. For coprimes, modular inverse always exists and could be found by extended euclidean algorithm.
•  » » » 17 months ago, # ^ |   +1 So nice!It fits well with the data range.Perhaps cuz I am too inflexible when learning euclidean algorithm.
•  » » » 17 months ago, # ^ |   0 Really nice I was really confused about how to solve that diphonite equation.thanks mate
•  » » » 17 months ago, # ^ |   0 Why we need to find the smallest value of y? I get all of your explanation except that smallest y part. Please help me out.
•  » » » » 17 months ago, # ^ |   0 Maybe you would like to check this out.
•  » » » » » 17 months ago, # ^ |   0 Thanks
•  » » » 16 months ago, # ^ |   0 Will this solution work if the value of w and d is big (1e9) ?
•  » » » » 16 months ago, # ^ |   0 I believe so (as 1e18 could still be handled by long long). But it may require more careful implementation.
 » 17 months ago, # |   +11 What is C's solution?I solved A,B and D, but I could't solve C.:(
•  » » 17 months ago, # ^ | ← Rev. 2 →   +1 first check if the (p % (gcd of(w,d) != 0) then the answer -1.then you should know the min number of draw matches you need cuz of (d
•  » » » 17 months ago, # ^ |   +4 Thank you for the easy-to-understand explanation!
•  » » » 17 months ago, # ^ |   +1 Why condition (p % (gcd of(w,d) != 0) is correct? I think its correct if w and d can be <0. But in our task we have to find >= 0 multipliers. For example, n = 100(its doesnt matter), p = 17, w = 7, d = 6 (answer = -1, but the condition passes it). So, can someone explain me why do we need this condition?
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   +1 it is correct in all situations.I didn't say it's the only condition.it just to make the approach faster.after calculating the answer check if the values are valid, that's mean ((a+b)<=n &&(a>=0)&&(b>=0))your example : 17 7 6 def = 17 % 7 = 3Mod[0]=0Mod[1]=6Mod[2]=5Mod[3]=4Mod[4]=3Mod[5]=2Mod[6]=1Mod[def] = Mod[3] = 4so the numbers of draw matches are 4then the winning matches are equal to (p-(Mod[def]*d))/w .which is (17-(4*6))/7=(-7)/7 = -1 .(a<0) is not valid value.then the answer is (-1) .
 » 17 months ago, # |   +3 What is Approach for C??
 » 17 months ago, # |   +19 So weak at number therory, How to solve C...
•  » » 17 months ago, # ^ |   +1 Diophantine equations i guess.
•  » » » 17 months ago, # ^ |   0 I implemented Extended Euclidean alg and got one of the solutions of the eqnx*w + y*d = p and then the general soln for this eqn is x = x0 + k*(d/g) and y = y0 -k*(w/g). So I ran a loop for k from 0 to 1000000 and found if x+y<=n if yes then I print x y and n-x-y. But this is giving me wrong ans on test 4. :(
•  » » » » 17 months ago, # ^ |   0 k may be less than 0, but on test 4 it doesn't matter:( I tried the same way as you.
•  » » » » » 17 months ago, # ^ |   0 I missed this case when k<0 shit. Thank you
•  » » » » » » 17 months ago, # ^ |   0 Even when k varies from -1e6 to 1e6 ; this does not help... I did the same mistake in contest and then got help from a friend to figure out that k can be huge too...Reason — your x0 and y0 will always be less than d ( or w ; which ever you use to find particular solution ) ;and then x = x0 + k * (d/g) when k has upper bound = 1e6 can only take you somewhere upto 1e11 even in best case.Then how would you ( and also I will )find solutions whose actual answer is something like ( 1e16 , 0 , 0 )
•  » » » » » » » 17 months ago, # ^ |   0 Yeah, this is not a good way.
•  » » » » » » » 17 months ago, # ^ |   0 Reason — your x0 and y0 will always be less than d ( or w ; which ever you use to find particular solution ) ; This is only true for y. You need the possibility to decrease the number. Only possible when transforming $w$ draws into $d$ wins not vice-versa.
•  » » » » » » » » 17 months ago, # ^ |   0 So do you mean we can vary k from -1e6 to 1e6 finding x0 first and then y0 ; And then vary k again from -1e6 to 1e6 in case we don't get a (x,y) ; but this time find y0 first and use it to find x0 ?
•  » » » » » » » » 17 months ago, # ^ | ← Rev. 2 →   0 hey guys what about this solution xw+yd = p , x+y+z = n, so (w-d)x = d*(p-n)+z , we know that w-d > 0 must d*(p-n) + z > 0 , x = (d*(p-n) + z )/(w-d) we know x will integer so z = (d*(p-n))%(w-d);then x = (d*(p-n) + z )/(w-d) ; y = n -y — z;
•  » » » » » » » » » 17 months ago, # ^ |   0 sorry i just have made the wrong equation
•  » » 17 months ago, # ^ |   +7 I have tried the diophantine equation but no luck. What a bad problem for C..
•  » » » 17 months ago, # ^ |   0 same here but could not cross test case 5
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   +7 try this test: 4 7 3 2answer: 1 2 1your answer might be: -1
•  » » » » » 17 months ago, # ^ |   0 i've got WA 5 too.tried it but my aswer is 1 2 1
•  » » » » » 17 months ago, # ^ | ← Rev. 2 →   +3 No, my solution gives 1 2 1 but failed at test case 5.Edit: Overflow seems to be the issue.
•  » » » » » » 17 months ago, # ^ |   0 Overflow was not an issue, I used big integer library and diophantine function still it did not cross test case 4.
•  » » » » » » » 17 months ago, # ^ |   0 i think that the case 4 is not about overflow
•  » » » » » 17 months ago, # ^ |   0 me,too. my answer is also 1 2 1 but I failed.
•  » » » 17 months ago, # ^ |   +1 Same here. Stuck on test case 7.
•  » » 17 months ago, # ^ |   0 I tried to solve it using extended GCD algorithm. This helps you to find (x, y) such what:wx + dy = p, though after finding a initial value of (x, y) you need to somehow convert it into a valid solution (Here is where I got totally stuck)
•  » » 17 months ago, # ^ |   0 You can use extended Euclidean algorithm to find x and y(keep in mind there can be more than one solution to the linear combination, so you need to take the one where y is minimal while still being >= 0).
•  » » 17 months ago, # ^ |   +9 brute force would work cuz small contraints on w or d
•  » » » 17 months ago, # ^ |   0 I used brute force but got TLE on test 66
•  » » » » 17 months ago, # ^ |   0 Me too. It was enough to check if the solution exists by checking divisibility of p by gcd(w,d)...
•  » » 17 months ago, # ^ |   0 binary search and binary search and more binary search... no number theory no nothing only binary search... at least that's how I did it
•  » » » 17 months ago, # ^ |   0 could you explain your approach ??
•  » » » » 17 months ago, # ^ |   +2 First I search for an x(number of wins) such that there "may" exist a possible y(number of draw) value so that x*w + y*d = p. (if n = 30, p = 60, w = 3, d = 1, and you pick x = 1, even y = 29 won't be enough to get 60 points and if x = 30 you are way over 60 point mark and there does not exist a way to reduce points.) Notice the "may"? because even you pick a valid x, then remaining points you need to gain is rem = p-(x*w), and if (rem%d != 0) then there does not exist any y for which you can gain p points (because there won't exist a y for which rem = y*d). But d <= 1e5. So all we need is pick some x such that rem%d = 0. how to pick such x? brute force. start from the initial x that we found. then run loop for (x+i) where (i runs from 0 to 1e5). and another similar loop for (x-i).
•  » » » » » 17 months ago, # ^ |   +1 I_love_Kim_Dahyun coudnt understood this part "So all we need is pick some x such that rem%d = 0. how to pick such x? brute force. start from the initial x that we found. then run loop for (x+i) where (i runs from 0 to 1e5). and another similar loop for (x-i)" Can you explain? Thanks :)
•  » » » » » » 17 months ago, # ^ |   0 I assume you understood the part why we need such x such that rem%d = 0. The explanation of the next part is: say you have a number a <= 1e5. Now from any number x to x + 1e5, (that is x, x+1, x+2....x+1e5)it's guaranteed that there exists at least one such number c within this range that is a multiple of a. Now if you will consider only the multiples of some number b, that is you want to find one multiple of a from x, x+b, x+2b... then your search space should be x to x+ b*1e5. that's what I did, start from x and go to x+1e5. In the meantime see how rem changes. rem = p -x*w(initially). then rem = (p-x*w) -x, (p-x*w)-2*x, (p-x*w) — 3*x...(as you increase x by 1 every time, you are only considering multiple of x). Now if I run this loop till x = 1e5, then I traverse a range from rem to rem — x*1e5. And if that does not give us any multiple of 'd', then we won't find any even if we continue searching. Here We need to consider both increase and decrease of x. because maybe if you keep increasing x you may find x*w > p , before you have reached a multiple of d. But if you decrease the value of x, you will find one correct multiple of d.
•  » » » 17 months ago, # ^ |   0 can you please explain your approach?
•  » » 17 months ago, # ^ |   0 well let i be the win count then draw cound d would be = (Points — i * winPoint) / drawPoint ....(1)we know drawCount + winCount >=0 && drawCount + winCount <= totalGamessubstitute result (1) into the condition and you will get the minimum win count and maximum win count now all you need to do is find a value in this range such that (Points — i * winPoint) is divisible by drawPoint and that's the answer.
•  » » 17 months ago, # ^ |   +3
•  » » 17 months ago, # ^ |   0 After contest, I solve F and G by myself, so C is the hardest for me...
 » 17 months ago, # |   +8 Was E not a greedy solution?
•  » » 17 months ago, # ^ | ← Rev. 3 →   +19 We ca use Binary Search to find minimum difference, The Min. element or Max. element in the final array after applying operations will be from the original array.
•  » » » 17 months ago, # ^ |   0 can you please briefly explain, how can binary search be applied on E?
•  » » » » 17 months ago, # ^ |   +9 We can do binary search on the ans(i.e minimum possible difference between max and min element). let's say we want to find if it is possible to apply <=k operations such that difference is less than equal to X. we can traverse the array and for ith element we can assume it to be the min. element than max. value must be a[i]+X; so now all the values less than a[i] must be made equal to a[i] and all values greater than a[i]+x must be made equal to a[i]+X, so we can find number of operations required to achieve this if we sort the original array and keep prefix sum, similarly we will assume the ith element to be max. value in array and min. value will then be equal to a[i]-X. and then find number of operations required. we will finally keep the min. number of operations required after traversing the array so if this value is less than equal to k than do right = X-1; else left=X+1;
•  » » » » » 17 months ago, # ^ |   0 can you please explain with a very small example?
•  » » » » » 16 months ago, # ^ | ← Rev. 2 →   0 How can you be sure that the min/max number will always be present in the original array ? Since you are assuming a[i] to be min/max element.Can you please explain in detail ? I saw your code, but didn't get it.
•  » » 17 months ago, # ^ |   0 I guess, E is ternary search within binary search.
•  » » » 17 months ago, # ^ |   0 Yes it worked for me.
•  » » » 16 months ago, # ^ |   0 Can you explain please?
•  » » 17 months ago, # ^ | ← Rev. 2 →   +20 i solved it greedyincrease / decrease elements which frequency is less to the next element
•  » » 17 months ago, # ^ |   0 I solved it by greedy.I hope it passes the main system cases too!
•  » » » 17 months ago, # ^ |   +3 It will surely pass Bro!!!
 » 17 months ago, # |   +59 Solutions of other participants and tests are locked for the next 30 minutes, since there is an onsite competition using the same problems. When it finishes, we will open the data for everyone.
•  » » 17 months ago, # ^ |   0 We also need 30 more minutes to submit more problems :)
•  » » 17 months ago, # ^ |   +1 so is the system testing delayed by 30 minutes or it'll start normally?
 » 17 months ago, # |   +1 how to solve C??
•  » » 17 months ago, # ^ |   +109 We can employ brute force. Iterate over all possible numbers of draws from zero to $W-1$. We can easily compute the number of wins necessary with a given number of draws and whether this configuration is possible (this requires that $P = Di$ mod $W$, where $i$ is the number of draws, and that $(P - Di) / W + D$ is at most $N$, since we need to have an integer number of wins and can have at most $N$ wins and draws). As soon as we find a working configuration, just print it and exit.We now prove that this is optimal--in other words, this will find a solution if one exists. Note that if there exists a solution $(x, y, z)$ with $y \geq W$, $(x+D, y-W, z)$ is also a valid solution. Moreover, the total number of wins and draws in the second solution is lower than in the first, meaning the second solution is more likely to fit within our $N$ game limit. Thus, any optimal solution will have $0 \leq y < W$, as desired, so our solution will find a solution if one exists.
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 How one can prove that number of draws must be below $W$? I iterated to 10^7 but couldn't prover that it's correct.
•  » » » » 17 months ago, # ^ |   0 As shown in the proof above, if there exists a solution with at least $W$ draws, there also exists one with $W$ fewer draws than this solution, so by this logic, we can reduce the number of draws by $W$ until it's less than $W$.
•  » » » » » 17 months ago, # ^ | ← Rev. 2 →   0 I musunderstanded. Thought that $y$ is number of losses. And I iterated over $z$ instead of $y$. But pretests has been passed. Thanks.
•  » » » » 17 months ago, # ^ |   +5 You can transform $W$ draws into $D$ wins.
•  » » » 17 months ago, # ^ |   0 I dont quite understand the notation you wrote, is W is as same as w in problem (same with D)?
•  » » » » 17 months ago, # ^ |   0 Yes.
•  » » » 17 months ago, # ^ |   0 I really liked your solution. Above all its simplicity. Very good idea
•  » » » 17 months ago, # ^ |   0 Tank you Sir!That helps me a lot,and when I passed this problem I konw that the exgcd is not unique to solve problems like this.It is only faster than O(N).There's only one things you didn't mention that we must let P>=Di or we'll WA62,but anyway there maybe only me who don't think about it!
•  » » » 17 months ago, # ^ |   0 maybe $(P-Di)/W + D$ is at most $N$should be $(P-Di)/W + i$ is at most $N$.Am I right?
 » 17 months ago, # |   +4 Finally a successful round with no delay,queue and most importantly no DDOS
 » 17 months ago, # |   0 I think C can be done using Linear Diophantine Equation, but I don't know how to find x, y, z so that x+y+z = n is satisfied. Any hints?
•  » » 17 months ago, # ^ |   0 the z is variable, u should just minimize y due to w > d (it should be correct, but i had wa5 too :(
•  » » » 17 months ago, # ^ |   0 yeah i know, z is variable. but i didnt know how to use Linear Diophantine Equation to find such x and y so that z can be obtained which satisfies x+y+z = n.
•  » » » 17 months ago, # ^ |   +3 You can just brute force on y, because it's at most W — 1, because you can always replace W draws with D wins and minimize it.
•  » » 17 months ago, # ^ |   0 find solution with minimum x+y such that x,y >= 0.
•  » » 17 months ago, # ^ | ← Rev. 4 →   0 It is the core part of my submission code with some comment. due to overflow issue, you should use python.if n-(x+y)<0: //n-(x+t*d/g + y-t*w/g) >= 0 //n >= (x+y)+t(d-w)/g //(n-(x+y))*g/(d-w) <= t (inversed ineq because d-w<0)t=(n-(x+y))*g//(d-w) + (0 if (n-(x+y))*g%(d-w)==0 else 1);x+=t*d//g;y-=t*w//g;
•  » » 17 months ago, # ^ |   -8 I have an solution: the problem can become this: xa+yb=c (a&b&c are known) And make y+x as minimum as possible (z = n-x-y)to achieve this we must let y as small as possible (since a>b) ,so (c-yb)%a=0because y must
 » 17 months ago, # | ← Rev. 2 →   +96 No DDOS attack No in queue, Finally codeforces was back.Thanks to MikeMirzayanov and every on works in this awesome platform ^_^UPD: WOW and Fast system test !!
 » 17 months ago, # |   +44 Problem C makes me feel like I'm in ICPC onsite, instead of Codeforces. （╯＾╰）
•  » » 17 months ago, # ^ |   0 Yes it troubles many people!
 » 17 months ago, # |   0 How to solve D?
•  » » 17 months ago, # ^ |   +15 First, the answer is $-1$ unless the tree is a line (i.e. all vertices have degree $2$, except for two, which have degree $1$). Proof: suppose vertex $A$ is connected to vertices $B, C,$ and $D$. By considering the paths $B-A-C$, $C-A-D$, and $D-A-B$, we see that all four of these vertices must have different colors, but with only three colors, this is impossible.If the tree is a line, then there are six possible configurations, each of which results from fixing the colors of one of the endpoints and the vertex adjacent to it. We can simply brute-force all six configurations and print the best one.
•  » » » 17 months ago, # ^ |   0 Thanks for proof.
•  » » 17 months ago, # ^ |   +3 The tree has to be a straight line to have any solution, since if it has more than 2 degree it can't be satisfied with 3 colors. After that the color has only 6 possibility: $[1,2,3,1,2,3,..]$ $[2,3,1,2,3,1,..]$ .. and all other permutations of $(1,2,3)$ repeated
•  » » » 17 months ago, # ^ |   +1 wow! thanks.
•  » » » 17 months ago, # ^ |   0 something wrong in my solution, but idea was the same(
•  » » » » 17 months ago, # ^ |   +2 Couple small corrections and it passed: res += cost[v][opt[i%3]];  int resIdx = opts[bestOpts][revidx[i]%3] + 1; https://codeforces.com/contest/1244/submission/62530591
•  » » » » » 17 months ago, # ^ |   0 Thanks!!
 » 17 months ago, # | ← Rev. 2 →   0 Problem C was rough.
•  » » 17 months ago, # ^ |   0 me too. i used a formula that involves max to solve b. i failed. haven't touched c, my heart is too broken to solve it. d, e, f are out of my realm of knowledge.i fucked up bad. can you, a fellow failed contestant, console me?
•  » » » 17 months ago, # ^ |   0 I think e is possible
 » 17 months ago, # |   0 What's the approach to solving E?
•  » » 17 months ago, # ^ |   +16 We employ a greedy approach. Start by sorting the data. Then, until we're out of moves and in increasing order of $i$, increase elements $0$ through $i$ to the value of element $i+1$ and decrease elements $N-1$ through $N-1-i$ to the value of element $N-2-i$.On our first iteration our answer decreases by one with each of our moves (since we are increasing/decreasing the minimum/maximum with every move), on our second iteration our answer decreases by one after every other move (since we need to increase the lowest two elements now each time we want to raise the minimum, and similarly for the maximum), and so on. It's relatively easy to see that we can't do any better, since at each step we're choosing the most efficient possible way of closing the gap.
•  » » » 17 months ago, # ^ |   +5 can you please explain with a small example?
•  » » » » 17 months ago, # ^ |   0 In sample case one, the sorted data is $1, 3, 5, 7$, and we have five moves. First, when $i=0$, we use our first two moves to increase the $1$ to $3$ and the next two moves to decrease the $7$ to $5$. Thus, we have one move left and have the array $3, 3, 5, 5$. Now, we have $i=1$, and we want to increase the first and second elements to the value of the third. With only one move, the closest we can get is the array $3, 4, 5, 5$ which has range $5-3=2$.
•  » » » » » 17 months ago, # ^ |   0 Thanks, Now the approach is clear to me.
•  » » » » » 17 months ago, # ^ |   0 Geothermal Nice approach, I came up with same solution but messed up implementation. two pointers implementations are tough for me :(
•  » » » 17 months ago, # ^ |   +3 Can anyone find the mistake with my algorithm? I WA on pretest 8.I defined Lcost(i) to be the cost to make subarray [1..i] equal to a[i] and Rcost(i) to be the cost to make subarray [i..n] equal to a[i]. Then used two pointers: For each l such that a[l] < a[l+1], let r be the minimum r such that Lcost(l) + Rcost(r) <= k. Since Lcost is increasing, r will be increasing as we iterate over l. Finally, we have some extra moves we are allowed to make: extra = k — Lcost(l) — Rcost(r). First, if r = l+1, then we can decrease the gap by floor(extra/min(l, n-r+1)). If r > l+1, then we try to fill the two gaps greedily: if l < n-r+1, then try to increase l first, then decrease r. Otherwise, do the opposite. There is an edge case which is we constrain l to increase by no more than a[l+1]-a[l] (this should not be necessary for r).I return the minimum of the answers for each valid l.
•  » » » 17 months ago, # ^ |   0 I have understood the greedy solution, I am wondering, can we apply binary search to the problem E?
 » 17 months ago, # |   0 what's the pretest 8 in E ? my program received wrong answer. https://ideone.com/DxJoFl
 » 17 months ago, # |   0 I started solving C before thinking that I can totally solve C fast. But a very very wrong decision :( from my side. And now I am totally going down in rating.
 » 17 months ago, # |   0 Is it possible to solve problem C using binary search?
•  » » 17 months ago, # ^ |   0 I tried Binary Search for y inside a binary search for x .. i got a WA on test 4 :\
•  » » » 17 months ago, # ^ |   0 Binary search cannot work because of the boundary not being clearly defined. A y may not satisfy the equation due to divisibility but y-1 may.
•  » » » 17 months ago, # ^ |   0 I tried binary search for both x and y... bot got WA on test 5 :\
 » 17 months ago, # |   0 Solution for C: Assume, that you have $X$ won, $Y$ draw games. Say, that you won't take $y$ more, that $w$, beacause, in other way we will get $(w + (y\mod{w})) * d + x * w\leftrightarrow w*(x+d) + d * (y\mod{w})$, and y will be less, that w. If we know Y, we can get X: $(p-y*d)\div{d}$ check, that this answer is correct, and print it, if true.
 » 17 months ago, # | ← Rev. 3 →   0 D was very interesting problem, how to solve it?
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 Observation: If there is a node with more than/equal to three edges, whatever you paint you will get a path of three nodes with "only two" colours. So any valid painting must be a list/degenerate tree. The colour pattern must be a sequence of "RGB"/"RBG"/...
•  » » » 17 months ago, # ^ |   0 Thanks, now I understand my mistake.
•  » » 17 months ago, # ^ |   +1 tree is a line if not answer = -1. After that you calculate all case and chose a best case =))
•  » » » 17 months ago, # ^ |   0 Thanks.
 » 17 months ago, # |   +4 RIP testcase 5 for C
 » 17 months ago, # |   0 Could someone tell what was the use of small constraints of w,d in C. How was it useful for brute force and when will the answer be -1?
•  » » 17 months ago, # ^ |   0 For number theory solution, one may need to solve a diophantine equation $xw + yd = p$. Take mod and we have $yd=p$ mod $w$. This "small" constraints enable brute force solving but not taking modular inverse.
 » 17 months ago, # |   0 problem C really difficul with me :((
 » 17 months ago, # |   +8 What is pretest 8 for E??
 » 17 months ago, # |   0 I tried to solve C but I Got Wa on test 5 using Binary search I don't know why my idea is wrong, anyone can help ?I was searching for number of wins so my start = 0, end = n, them (n — mid) will be number of draw matches, So total points so far = mid * w + (n-mid)*d, Now the idea,if total points < p, I should win more matches, So start = mid + 1 and continue searching.if total points == p, So I can win with this number of wins and this number of draws with 0 lose matches.if total points > p, (rem now is the number of draw matches),I will try to make the team lose from o to rem matches using the same idea(binary search) if I found at sometime I can make the same exact point this will be answer otherwise I will continue searching using the same idea of binary searchcode: 62490213
•  » » 17 months ago, # ^ |   0 That will not work.
•  » » » 17 months ago, # ^ |   0 Why? I Tried a lot of cases and it works,please can you explain ?
•  » » 17 months ago, # ^ |   0 tyr out this one 30 60 9 4 one of the answer would be 4 6 20
 » 17 months ago, # |   0 I can't solve problem A
•  » » 17 months ago, # ^ |   0 I don't like this round
•  » » » 17 months ago, # ^ |   +16 poor you :)
•  » » 17 months ago, # ^ |   0 If you don't have atleast ceil(a/c)+ceil(b/d) instruments the answer is -1 else one of the possible ans is ceil(a/c) && ceil(b/d).
 » 17 months ago, # |   0 Great round, make more rounds like this!
 » 17 months ago, # | ← Rev. 2 →   +13 Please don't just shove a bunch of div2Cs in a row in div2s. Come on, even div2s got some dignity :|Too many shit problems in a single div2 nowadays :|
•  » » 17 months ago, # ^ | ← Rev. 2 →   -8 ??
•  » » » 17 months ago, # ^ |   +3 What @maxorand implies is not that he can't solve the problems, but that he thinks that the problem are too easy (too many problems with the difficulty of a Div2 C).
•  » » 17 months ago, # ^ |   0 +1. DEF are all at same level.
 » 17 months ago, # |   +9 I am glad that the round passed without DDoS attack :)
 » 17 months ago, # |   +2 C is more difficult than D, E and F.Unfortunatly did read E and F after contest :/
•  » » 17 months ago, # ^ |   -8 I think you misread E. E was not easy
•  » » » 17 months ago, # ^ |   0 You are right, implementation is not that simple as I thought first.
 » 17 months ago, # |   +3 In C you can just brute force on Y from 0 to 1234567, it's work but don't know why, can somebody explain?
•  » » 17 months ago, # ^ |   0 $Y$ can be at most $w - 1$, if its more than $w$, then transform them to $d$ wins instead of $w$ draws.
•  » » » 17 months ago, # ^ |   0 thank you
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 the (p — d * i) % w will form a cycle and you just need to find the i that (p — d * i) % w equal to zero
•  » » » 17 months ago, # ^ |   0 cycle with at most w elements, because only w reminders exist, so if it is'n good i in first w tries output is -1
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 why it doesn't work for 100000, it is given in problem that w is max 100000.
•  » » » » 17 months ago, # ^ |   0
•  » » » 17 months ago, # ^ |   0 I did exactly same but got wrong answer on test case 62
•  » » » » 17 months ago, # ^ | ← Rev. 2 →   0 same here
•  » » » » 17 months ago, # ^ |   0 you missed cases like the one given in below comments: 2 1 5 3
•  » » » » » 17 months ago, # ^ |   0 Bro the mistake was that, i didn,t checked that (p — d * i) >= 0
•  » » » » » » 17 months ago, # ^ | ← Rev. 2 →   0 damn it! it is working now!, lol can't believe so many participant forgot that myself included.
 » 17 months ago, # |   0 Most system fail in today's Div 2 C. I wonder why they keep such weak pretests?
•  » » 17 months ago, # ^ |   0 to invite more hacks.
 » 17 months ago, # |   0 Problem C pretest were too weak, constrains were not checked.
 » 17 months ago, # |   +3 OMG!! so many system test fails for C on Test 62.
•  » » 17 months ago, # ^ |   +5 try 2 1 5 3
•  » » » 17 months ago, # ^ |   0 thank you.I've made a mistake in my program.
•  » » 17 months ago, # ^ |   +21 Congrats to Tynoo for the hack creating test 62.
 » 17 months ago, # |   0 Lol, nice system tests on C. What is approach failed?
 » 17 months ago, # | ← Rev. 3 →   0 Powerless to solve problem C when I haven't known diophante before.
•  » » 17 months ago, # ^ |   +24 You dont need it. You can just brute for all number of draws < W. (1e5)
 » 17 months ago, # |   +5 How to solve C?I got a wrong answer on test 62...
 » 17 months ago, # |   +5 It's a good choice to give up C :)
•  » » 17 months ago, # ^ |   +3 It's a good choice,indeed.
 » 17 months ago, # |   +5 So, very nice round)) Everything was cool except C. Only 500+ solutions from more than 1500 have been accepted :(
 » 17 months ago, # |   0 Thanks so much... First time become blue <3 thanks ^^
 » 17 months ago, # |   0 Wow!!!!! Problem C is really strong. Before system testing,my rank is over 1000,but after my rank became 800+. What a clever choice to give up C!
 » 17 months ago, # |   0 what is pretest 6th in d??
•  » » 17 months ago, # ^ |   0 It seemed to be a very large answer. At first,I got a Wrong Answer at the 6th pretest. And then I found my intial value of the answer is too small. So I make it 10^15,then I passed pretests. Hope this can help you.
 » 17 months ago, # |   -6 Loved the contest!
 » 17 months ago, # |   0 what is the core logic behind F?
•  » » 17 months ago, # ^ | ← Rev. 2 →   +3 The observation is if we have a contiguous subsegment of single coloured cells, they would never flip. If we have a contiguous subsegment of alternating black and white cells, the length of this segment would decrease by 2 each time we flip it. (You can view this as the cells on the ends of this segment are absorbed by the single coloured segments adjacent to them). Based on this, we may work out the max possible number of flips each position could do.
•  » » » 17 months ago, # ^ |   0 Okay, I get it. Thank you :)
 » 17 months ago, # |   -37 Excuse me... Why my code get skipped?
 » 17 months ago, # |   -43 The problems of this round are sooooooooooooo hard to implement!
 » 17 months ago, # | ← Rev. 2 →   +3 If you got WA on test case 49 in problem C, you may miswrote p>n*w as p>=n*w in the beginning like me...TAT I submitted it very early and in the rest of competition I did nothing... What a pity!
 » 17 months ago, # |   0 I really liked the problems, but spent too much time on C :(
 » 17 months ago, # |   0 Can someone explain why brute force works on C? I brute forced for values of x between (p-n*d)/(w-d) and p/w. Isn't this still o(P)?
•  » » 17 months ago, # ^ |   +3 p <= 1e17
•  » » 17 months ago, # ^ |   +3 I tried to brute force on x it didn't work .. then i tried to brute force on y i got accepted , can anyone explain please ?
•  » » » 17 months ago, # ^ |   +3 you cant brute force on x cuz it could be between [1,min(n,p/w)]but y can be only between [1,w-1]proof : if y=w then y*d=w*d rewrite it like this y*d=w*(a1) where (a1=d)you can see (a1d)so it's better to consider (a1) winning matches than (y) draw matches
 » 17 months ago, # |   +12 I want to try to solve more problems like C, Kindly can anyone suggest those problems?
 » 17 months ago, # |   +8 Editorials?
 » 17 months ago, # | ← Rev. 2 →   -8 Very sorry to write this, but big downvote for problem C! A well-known problem. The statement itself contains exactly the equation you need to solve (x * w + y * d = p). And you have to deal with int64 overflow when solving it with extended Euclid! (test 7) WTF
 » 17 months ago, # |   +18 More than 10 people in the top 40 did not pass C
 » 17 months ago, # |   0 During the contest, I use exgcd for problem C, then I realized that the answer in problem C may cause longlong overflow, so I tried to use __int128, and thenSo I wonder if it is possible to solve problem C by using exgcd(No matter in python or C++).
•  » » 17 months ago, # ^ |   +6
•  » » » 17 months ago, # ^ |   0 Thanks
•  » » » 17 months ago, # ^ | ← Rev. 2 →   0 What's the idea/observation behind this specific solution? I understood till the line " p /= g, d /= g, w /= g; "What's happening after that?
•  » » » » 17 months ago, # ^ |   +3
•  » » » » » 17 months ago, # ^ |   0 Thanks
•  » » » » » 17 months ago, # ^ |   0 Okay, I have one more question. Does it ensure that x+y will be minimum as I can see you've checked for the only root found from the modInv? Otherwise shouldn't I be looking around for other roots?
•  » » » » » » 17 months ago, # ^ | ← Rev. 2 →   +3 I guess it is minimum. Since $d < w$ and we must use either $wx$ or $dy$ to "fill" $p$, it seems to be optimal to use the smallest possible $y$.And there should only be one $y$ under $w$.
•  » » 17 months ago, # ^ | ← Rev. 2 →   +1 Found a blog-post to overcome the overflow including proof on the comment section. Works fine for this problem as well. Avoid overflow in linear diophantine equation
•  » » 17 months ago, # ^ | ← Rev. 2 →   +1 You can use this BigInt struct.
 » 17 months ago, # |   +6 ???? My rating is lost???
•  » » 17 months ago, # ^ |   0 Me too, there may be some technical problems.
•  » » » 17 months ago, # ^ | ← Rev. 2 →   +3 :((( the first time I become expert :<<< so sad.. may be it's unrated :(
•  » » 17 months ago, # ^ |   0 Everyone's rating history is lost, as I am not able to see anyone in rating lists. Something wrong with the system.
•  » » 17 months ago, # ^ |   0 It's back :D
 » 17 months ago, # |   0 How to solve E?
 » 17 months ago, # |   +31 is this contest unrated?because a few minutes ago i had updated ratings but now it is back to one which was before the contest
 » 17 months ago, # |   +18 Oh my god , is this round unrated ?I'm a step away from the master .
•  » » 17 months ago, # ^ |   +5 Sorry it is a DDOS attack.
•  » » 11 months ago, # ^ |   0 hiahiahiahia!!!!!
 » 17 months ago, # |   +24 Why after the contest my rating was up, and after 2 hours it was resumed to the previous state?
•  » » 17 months ago, # ^ |   0 Me too.What's going on?
 » 17 months ago, # | ← Rev. 2 →   0 someone, please help why is this wrong for 627936103814 4254617095171609 45205 1927my output = 70349468271 557586601962 33581x+y+z = 627936103814the given answer is 94118284813 15672 533817803329in C problem
 » 17 months ago, # | ← Rev. 2 →   0 RIP my rating. I was racking my brain trying to figure out a counterexample to my heuristic for B but turns out it was just a simple off-by-one bug.Also had no luck figuring out the number theory required to solve C analytically, and missed the brute force solution.
 » 17 months ago, # |   +3 Nice article to read for C.(https://math.stackexchange.com/questions/20717/how-to-find-solutions-of-linear-diophantine-ax-by-c?rq=1)
 » 17 months ago, # |   0 why Y can be atmost W-1 in problem C ?
•  » » 17 months ago, # ^ |   0 If y == w, we can say that we won d matches (y == w -> y*d == w*d)
•  » » » 17 months ago, # ^ |   0 I can't understand.
•  » » » » 17 months ago, # ^ |   0 If y=k*w+r and x=x0 — solution, so: y=r and x=x0+k*d — solution too, because: r + (x0+k*d)
 » 17 months ago, # |   0 Can somebody help me, why am i getting runtime error ? https://codeforces.com/contest/1244/submission/62522364
 » 17 months ago, # | ← Rev. 2 →   +1 C was the only problem out of 7 I couldn't solve myself. Maybe once I will start reading all statements and won't stay on 1 for the whole round :P
 » 17 months ago, # |   +1 Editorial, please?
 » 17 months ago, # |   +27
•  » » 17 months ago, # ^ |   0 I took a lot of time thinking about C and later started solving D. When I finished the code, I saw: "Contest has ended. Thanks for your participation." :'(
•  » » 17 months ago, # ^ |   0 Relatable.
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 Meh, graphs are a weakness for me. E though, I thought I had a chance of solving, but I kept failing at pretest 13edit: And it turns out it's an integer overflow bug. I'm just off my game this round
 » 17 months ago, # |   0 When the editorial will be avialable? C very interesting problem:)
 » 17 months ago, # |   0 How to solve Problem C using Linear Diophantine Equation?Specially after finding x,y by using Linear Diophantine Equation how to maintain x+y<=n?
•  » » 17 months ago, # ^ | ← Rev. 3 →   +3 Once you form equation for x = x1 - k*b/gcd(a,b) and y = y1 + k*a/gcd(a,b). x1 and y1 are two coefficient you get from extended euclid algo. Check which one is negative x1 or y1. From that you can derive one inequality k>=c1. Now known x+y <= n. Plug in equation of x and y in that. Only unknown in that equation is k. Solving this inequality will give you something like k<=c2. All values of k will give you one answer which satisfy above two inequaliteis. k>=c1 and k<=c2PS: This answer helped me understanding solution for Diophantine Equation. https://math.stackexchange.com/questions/20717/how-to-find-solutions-of-linear-diophantine-ax-by-c?rq=1
•  » » » 17 months ago, # ^ |   0 How can you be sure that there(x1 & y1) will always a negative value?And what is c1 and c2?
•  » » » » 17 months ago, # ^ |   0 Its or condition.Not and condition.
 » 17 months ago, # | ← Rev. 2 →   +6 the most difficult problem for me was C, without it or putting it as the last one, the contest could have been a good div3
 » 17 months ago, # |   0 Thanks a lot.The time is friendly to Chinese.And no DDOS attack
 » 17 months ago, # |   0 Since when does E div 2 can be solved using greedy only?
 » 17 months ago, # |   +3 why G problem is not that much hard ?
•  » » 17 months ago, # ^ |   0 I think problem G is very easy,easier than problem D.
•  » » » 17 months ago, # ^ |   +3 Same feeling
 » 17 months ago, # | ← Rev. 2 →   0 My English is not good...In fact problem C is not as hard as you think,you don't need "exgcd" to solve solution.Chinese solutionyou see, $1 \leq d < w \leq 10^5$ .Greedy, $w>d$ ,so we can make $x$ bigger,and you can implementation $d$code: #include #include #include #define ll long long using namespace std; ll n,p,d,w,x,y,z; int main(){ cin>>n>>p>>d>>w; while(y=0&&z>=0) printf("%lld %lld %lld",x,y,z); else printf("-1"); return 0; } 
 » 17 months ago, # |   +3 I felt that the ordering of difficulty of questions in this contest was: A
 » 17 months ago, # |   0 I should have gave up C to have a look at problem E QAQ
 » 17 months ago, # |   0 How to solve E?
 » 17 months ago, # |   0 Hi can anyone please tell me why my solution for D Problem keeps getting Memory Limit Exceeded Verdict ? 62615746. Thank You
 » 17 months ago, # |   0 tutorials?