SYury's blog

By SYury, history, 13 months ago, ,

Hello!

Codeforces Round #514 (Div. 2) will start tomorrow, October 05, 17:35 (UTC+3). This round will be rated for the second division (with rating lower than 2100).

Many thanks to KAN for his help with the problems and round coordination, Aleks5d and Um_nik for testing this round, and MikeMirzayanov for his awesome Codeforces and Polygon platforms.

There will be 5 problems for 2 hours. The scoring distribution will be announced later.

UPD: the scoring distribution will be 500-1000-1500-2000-2500

UPD2: Congratulations to the winners!
Div. 2:
1. UoA_ZQC
2. PaidySung
3. Hyperbolic
4. thinfaifai
5. reku

Both divisions:
2. UoA_ZQC
3. natsugiri
4. nuip
5. PaidySung

UPD3: editorial

Good luck!

• +293

 » 13 months ago, # |   +14 gl hf
 » 13 months ago, # | ← Rev. 2 →   +67 Wow, that's by far the shortest announcement in a while.
•  » » 13 months ago, # ^ |   +50 Plus, It thanked MikeMirzayanov for his awesome Codeforces and Polygon platforms. :)
 » 13 months ago, # |   +1 Back to back contest...ohhh Yessss...
 » 13 months ago, # |   +3 Finally, a regular Codeforces round is here after a week of waiting. I love Codeforces.
 » 13 months ago, # |   +5 That will be first time ever in my life, I will face 2 consecutive contests in almost 6 hours.ACM ICPC Dhaka Regional Site Online Preliminary contest — (BD time) — 03.00 PM to 8.00 PM.Codeforces Round #514 (Div. 2) — (BD time) — 08.35 PM to 10.35 PM.Thanks :) SYury
•  » » 13 months ago, # ^ |   0 How many did youb solve in the icpc preli?
•  » » » 13 months ago, # ^ |   +8 We did bad in ICPC Preli. Unfortunately we solved only 2 problems. In Problem C and D, we got TLE. WA in Problem J.
•  » » » » 13 months ago, # ^ |   0 It's okay. We didn't do much better either. Solved 3, got AC in J. Which year are you in?
 » 13 months ago, # |   -35 Shortest announcement... Not good.
 » 13 months ago, # |   +17 Hope the problem statements will be as short as the announcement :) .
 » 13 months ago, # |   0 Round #514 reminds me of Round #114
 » 13 months ago, # |   +2 So concise description.
 » 13 months ago, # |   +2 It is an unforgetable experience to start a contest at midnight.I love Codeforces.
 » 13 months ago, # |   +15 A red problem setter and just div2, it's gonna be hard contest.
•  » » 13 months ago, # ^ |   +14 It has just 5 problems, so yeah, it's gonna be hard.
 » 13 months ago, # |   0 I wish everyone gets positive rating changes.
•  » » 13 months ago, # ^ |   +21 That's quite not possible.
 » 13 months ago, # |   +3 I hope that lack of div.3 contests means that the next gonna be amazing
 » 13 months ago, # |   +11 Score distribution !!?? 
 » 13 months ago, # |   +9 there're only 5 problems prepared by a red problem setter? gonna be a hard contest
•  » » 13 months ago, # ^ |   0 guess you were wrong...
 » 13 months ago, # |   0 I just logged in late. Why am I unable to register now?
 » 13 months ago, # |   -26 B must candidate to the "worst problem on the year" !
•  » » 13 months ago, # ^ |   -10 Yes, I can not understand the statement of problem B. Kind of shit!
•  » » » 13 months ago, # ^ |   0 the problem for me was that he didn't say that we shouldn't include empty cells in the sides of chosen rectangles .
 » 13 months ago, # |   +25 What is test 4 of D problem?
•  » » 13 months ago, # ^ |   0 I have the same problem.
•  » » 13 months ago, # ^ |   +2 2 -10000000 1 10000000 1
•  » » » 13 months ago, # ^ |   0 The lack of setprecision makes WA then? :)
•  » » » » 13 months ago, # ^ |   +3 Actually the most common problem was too low binary search upper bound.
•  » » » » » 13 months ago, # ^ |   0 Ye ye already got it thats the second,bigger issue.
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   0 Yeah and also the radius is huge so you can't just start your binary search at 1e7I found a solution that didn't take care of precision and searched from [0.2..1e15] and lucked out of that pretest (for now... pending system tests) but anyone who went from [0..1e15] with the same precision problem will fail it.
•  » » » 13 months ago, # ^ |   +5 Thx, max-radiuos ~ 10^14 !!!!
•  » » » 13 months ago, # ^ |   0 It will be nice, if D statement was added hint about this restriction, or limitation of x,y coordinates. This is div2 problemset -).
•  » » » » 13 months ago, # ^ |   +6 h = abs(y - r); sqrt( r * r - h * h ) ---> WA4sqrt( 2*r*y - y*y) - AC ! 
 » 13 months ago, # |   +1 By any chance is D first ternary searching for x coordinate of center and then binary searching for the y coordinate of the center? If not can someone give any hint on how to approach.
•  » » 13 months ago, # ^ |   +3 This solution does not fit the time limit restriction.
•  » » 13 months ago, # ^ |   +23 I solved it by binary search on radius R: then for a fixed R for each point you can calculate the interval of the x coordinate of the center of the circle (by pen, paper, math). Then you need to check whether all n these intervals have an intersection.
•  » » » 13 months ago, # ^ | ← Rev. 3 →   0 We only obtain two possible points for the center of circle(since it has to lie on the line y=R) while checking it for each given point,right? Why do we get intervals instead of two points?Got it.I thought that all the points needed to be on the circle boundary.
 » 13 months ago, # |   +22 Building a neat binary search solution for D, with all those precision handling and everything, and still got a WA at pretest 4.This is just plain sadistic... :<
•  » » 13 months ago, # ^ |   0 what was ur greedy after the binsrch on answer?!
•  » » » 13 months ago, # ^ |   +5 I didn't do greedy.My logic: for each radius r being checked (obviously the y-coordinate of the circle's center will be r), traverse through every points and find the leftmost and rightmost x-coordinates that the circle's center's will be not-further-than-r distant to that point with its x-coordinates lying between the leftmost and rightmost.If all intervals intersects somewhere, then r is one answer (might not be the optimal one, that will be solved with further binary searching).
•  » » » » 13 months ago, # ^ |   +3 what is your output if the points are (-1e7,1) (+1e7,1) ?
•  » » » » » 13 months ago, # ^ |   +3 Got my issues now. The upper bound of my binary search was too low (heck, it's insanely high to be honest).Thanks! :D
•  » » » » » » 13 months ago, # ^ |   +6 I dont know how to handle this extreme high cases either. the radius of curvature is too high. and squaring it will exceed variable limits. Hence i cant take distances between two points. This is why i couldn't do it either incontest.
•  » » » » » » » 13 months ago, # ^ |   0 I just figured out a way btw :D bet it'd pass all tests in practice :DI'll binary search everything in long double, and to counter precision issues (to break the binsearch loop properly), I'll calculate the absolute/relative error of the lower bound and the upper bound and see if it is low enough.(The function is given in the statements itself, and it's easy enough to implement :D )
•  » » » » » » » 13 months ago, # ^ |   +16 The following formula helps to keep calculations <= 1e18.sqrt(A * A - B * B) = sqrt((A - B) * (A + B)).
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 I also got WA on pretest 4. But I overcame it after increasing the number of iterations of the binary search (unfortunately I got TLE on later tests and didn't have time to optimize the algorithm :( )edit: nvm, my algorithm was not the same as yours
•  » » » 13 months ago, # ^ |   0 What was ur algorithm btw?
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   0 Binary searching for the point of tangency. Given a point of tangency, you can compute in O(n) minimum radius and you have that the optimal tangency point can not be farther away from the point that is on the boundary of the minimum circle on the current tangency point.
 » 13 months ago, # |   0 howto solve C ?
•  » » 13 months ago, # ^ |   +15 HINT: Remove numbers at an odd position's, until there more than 3 elements.
 » 13 months ago, # |   0 What is the pretest-6 of C?
•  » » 13 months ago, # ^ |   +2 As I guess: 6Answer would be: 1 1 1 2 2 6 
•  » » » 13 months ago, # ^ |   0 How do we compare it with 1 1 1 1 3 6?
•  » » » » 13 months ago, # ^ |   +1 Your answer is lexicographically smaller (the 4th element is 1, while the optimal one's is 2).
•  » » » » » 13 months ago, # ^ |   0 But according to the given statement, j=2(0-based indexing) then a[i]>b[i] is not satisfied for i>j.
•  » » » » » » 13 months ago, # ^ |   0 You got it wrong. The criteria is like, the lexicographical order is determinded by the leftmost element that differs between two answers.So, we'll determine j = 3 (0-based) only.
•  » » » 13 months ago, # ^ |   0 The last one is special.
 » 13 months ago, # |   +3 Previous contest haven't got any Editorial even till now. I hope this contest gets an Editorial soon enough.
 » 13 months ago, # |   -81 I hated this crap.A was stupid subtraction with confusing intervals, B was ad-hoc (and a terrible one at that), C was math, D was geometry and I didn't even read E after so much frustration with the other 4 garbages.
•  » » 13 months ago, # ^ |   +14 Problem D was one of the best problem I have ever tried but missed to submit, i just needed 10 seconds, found a little bug in last moment (-_-).I tried only problem D in 2 hours.
•  » » » 13 months ago, # ^ |   -38 Probably would have got WA on Test 4, so why bother?Geometry can never be fun. End of story.
•  » » » 13 months ago, # ^ |   -22 Want fun? Solve some string matching problem, a range query problem, or a nice DP one. Let geometry for math geeks and masochists.
 » 13 months ago, # |   0 How to solve C? I was thinking of finding the number of coprimes for each number in range 1 to n and then greedily removing the number having largest number of coprimes. But couldnt implement. Is this right? Please share your approaches.
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 my pretest passed solution:initially current_gcd = 1, then remove every even index (1-indexing) if n is even, or remove every odd index if n is odd from the original sequence so we can get larger gcd faster, except when n = 3 we just remove index 1 and 2 because its better.
•  » » 13 months ago, # ^ |   +2 The idea was the following: Initially the gcd is 1 and this needs to be increased to some g>1. Consider the smallest prime factor of g (say p). To increase the gcd from 1 to g we need to remove at least all the numbers which are not divisible by p. We need to minimize the number of numbers not divisible by p, which is same as maximizing the number of numbers divisible by p.It can be observed that except for n=3 in all other cases, p=2 (We can hard code the solution for n<3). After removal of "bad" numbers, all the remaining numbers will be the first floor(n/2) multiples of 2. Now it is possible to recursively build the solution, by solving for n=floor(n/2) and multiplying the resulting sequence by 2 elementwise.
 » 13 months ago, # |   0 I'm gonna be green like a String in the wind
 » 13 months ago, # |   -34 It'd be nice to see a Segment Tree problem once in a while, a DSU, or even a DP. It seems all we see now is math, math and more math. Go to IMO if you want math.
•  » » 13 months ago, # ^ |   0 Problem C was not Math, just IQ test. Don't be tricked by GCD !
•  » » » 13 months ago, # ^ |   0 I was wondering how to do that...
•  » » » 13 months ago, # ^ |   -21 Ahhhhhhh, I didn't know this was an IQ test, dude. I thought we were in a programming competition!
•  » » » » 13 months ago, # ^ |   +58 Most competitve programming problems are not only about "Please implement this algorithm/that data structure", but also at requiring you to make certain observations. And that is the part when your IQ is needed.
•  » » » » » 13 months ago, # ^ | ← Rev. 2 →   -17 Yeah, I accept that part of also requiring you to make certain observations.I just utterly detest it when the whole problem is about making observations and/or math calculations, with little to no programming technique or data structure.But why bother discussing? Everyone will see I'm cyan and you're red, so they're gonna downvote me and upvote you. Whatever.
•  » » 13 months ago, # ^ |   0 You got E for dp today.
•  » » » 13 months ago, # ^ |   0 DP?I did a solution for E using binary jumps, but for some bogus reason I got TLE on Test 24, when all the previous test cases had at most 150 ms. I don't care anyway, the contest's over.
•  » » » » 13 months ago, # ^ |   0 I remembered the minimum number of paths for the subtree and the possible paths ending in the root (in that minimal splitting). These paths had a structure that the sum of values was increasing, but the length of the path was decreasing (otherwise it is not profitable to store other paths).I do not know how to prove that the number of such paths will be reasonable (maybe it won't and my solution should tle) but it passed. While merging these paths, merge smaller set to larger.Then try to extend every path with the value of the new root. If you can't, start a new path in the root.
•  » » » » » 13 months ago, # ^ |   0 That sounds way too complicated and too much thought involved for a problem that doesn't require any thinking, just implementation of a technique.
•  » » 13 months ago, # ^ |   0 I solved E in 200 lines using 3 segment trees and dp.
•  » » » 13 months ago, # ^ |   0 Really?!It's a simple binary jumps + binary search with much less than 100 lines and only two data structures (one for ancestors and one for sum of weights).
•  » » » » 13 months ago, # ^ | ← Rev. 2 →   +5 If you want dp you think dpAlso, you just need to maintain the stack of vertices in a dfs and do bsearch over it, no need for LCA stuff.
•  » » » » » 13 months ago, # ^ | ← Rev. 2 →   0 Would the above ideas pass this test?Edit. Yes, they should.
•  » » » » » » 13 months ago, # ^ |   0 Yes, my code got 2 as answer.
 » 13 months ago, # |   0 how to solve B and E?
•  » » 13 months ago, # ^ | ← Rev. 2 →   +5 B find every cell which is surrounded by ‘#’， when found one，copy these '#'s to another graph(initialized by ‘.’). compare two graphes，judge whether they match. I don't know how to solve C，(((QAQ ORZ
•  » » » 13 months ago, # ^ |   0 and sorry for the vote...I clicked it accidently.(QAQ
•  » » » 13 months ago, # ^ |   +6 C can be solved recursively. The base cases are (1, 2, and 3) for which the answers are given in the sample itself. For all other cases remove the odd ones first and then divide the array by 2 and it again becomes the same problm. The only thing you should take care of is that we are dividing it 2 but it is not actually the case so, at the time of printing we have to print the actual values itself. Hope it helps!
•  » » 13 months ago, # ^ |   -18 I didn't even read E during the contest because all the other bullshit took away my time, but after reading it now, I think it can be solved with prefix jumps over ancestors and binary search, but I still have to test my solution.I'll see if I'm right once the turtle finishes system testing all solutions for this sorry excuse for a contest.
 » 13 months ago, # |   -8 I spend an hour understanding problem C i still don't get it Can someone PLEASEEEEEEE.... tell me what the hell does it mean?????? :( ;(
 » 13 months ago, # | ← Rev. 2 →   +92 I'm don't know if I'm too easy-going, but 80% of time when I think the problemset is good, I read the comment section and seeing everyone else bashing it...
•  » » 13 months ago, # ^ |   -33 You thought THIS was good?Well, yeah bro..... you're either too easy-going or you're a math freak. Choose whichever you like.
•  » » » 13 months ago, # ^ |   +25 I registered for the contest late and ended up did not even touched ABC (since I can't submit them in the first 10 minutes even if I implemented them fast enough), only focused on D and E, and both of them seems OK so far.
•  » » » » 13 months ago, # ^ |   -20 D was not that bad, considering it's geometry, and all geometry is boring and confusing. Except for the part that my idea is correct and I get WA on Test 4. Let's see what happened after System Test.E was nice I think, but all the other bullshit took away my time during the contest, so I didn't even read it.
•  » » » » » 12 months ago, # ^ |   0 all geometry is boring and confusing What lol?
•  » » » » » » 12 months ago, # ^ |   0 What you just read pal. Geometry is simply not of my liking.I solved D in the end (after the contest...), but that doesn't mean I enjoyed doing it. Thinking a solution for a geometry problem is not fun, and coding it is a pain the ass.Formulas like asin/acos/atan and all that stuff that I never remember which one is what without Google, cross product, neverending variables for something as simple as a line intersection... and all that without even mentioning precision errors. A correct solution can get WA for something as insignificant as replacing "double" with "long double".
•  » » » » 13 months ago, # ^ |   0 can you please share the idea for E?
•  » » » » » 13 months ago, # ^ |   +3 I could not solve E in the contest :(
•  » » » » » » 13 months ago, # ^ |   0 Too nud dude. Come to me with pen and paper, I will tell you how to do that.
•  » » 13 months ago, # ^ |   +20 I actually really liked the problems, especially B and C, and I think I have an idea for E...
•  » » 13 months ago, # ^ |   +34 Problems are more enjoyable to one when one has managed to solve them.
 » 13 months ago, # |   +8 Is E something like finding the topmost vertex you can reach from each vertex, and then starting from the leaves?Forgive if grossly incorrect.
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 Well I got AC with that idea (at least on pretests).
•  » » » 13 months ago, # ^ |   0 can you please explain the idea a little bit more?
 » 13 months ago, # | ← Rev. 2 →   0 How 1e9 computations are possible in 2s on CodeForces (as http://codeforces.com/contest/1059/submission/43853124)? Shouldn't it timeout.
•  » » 13 months ago, # ^ |   0 1e9 pure computations only take about 0.2-0.4s for C/C++ solutions. Other languages (Java, Python, etc.) will surely get TLE for that.
 » 13 months ago, # |   +1 It's a little weird of today's problems :)
 » 13 months ago, # |   0 Is solution for C something like, remove elements from odd places in the current list in each round, where each round has only half the list compared to previous round? Therefore the answer is like, about n/2 times 1 followed by about n/4 times 2 followed by about n/8 times 4 and so on?
•  » » 13 months ago, # ^ |   0 Almost, except one exception.If there are only 3 elements remaining, remove the 2 smaller ones (like in my comment with test n = 6).
•  » » » 13 months ago, # ^ |   +3 Yeah, saw your answer for n=6 and figured that.
 » 13 months ago, # |   0 WA at 8.What is the no 8 pretest for problem C?
•  » » 13 months ago, # ^ |   0 Akikaze has given a case above.
•  » » » 13 months ago, # ^ |   0 My code giving me right output for that case.
 » 13 months ago, # | ← Rev. 2 →   0 http://codeforces.com/contest/1059/submission/43847734 Whats wrong with my submission for C?
 » 13 months ago, # |   0 How do you solve D?
 » 13 months ago, # |   +4 How fast system testing is done today. WoW.
 » 13 months ago, # |   0 Hint for problem D https://www.geogebra.org/graphing/gqhms2jk
 » 13 months ago, # |   -21 Problem E was BY FAR easier than B, C and D. After reading it, I instantly thought "Binary jumps + binary search", and that was it. Coded it in over 10 minutes and got Accepted after fixing a stupid bug of not stopping iterations of marked vertices at root of tree.Come on, let the downvotes rain!
•  » » 13 months ago, # ^ |   +36 Looking through all of your comments so far... you seem to be a very, very angry man
•  » » » 12 months ago, # ^ |   0 Looking at your avatar, you seem to be a mouse. Are you one?
•  » » » » 12 months ago, # ^ |   +1 Yes
 » 13 months ago, # |   +2 Anyone have any idea what was systems test 18 on B (It's m = 900 and n = 999 or something so I can't copy see the whole of the test case)? 43842790Bye bye expert :'(
•  » » 13 months ago, # ^ |   0 I think that test case has all value dot(.).if no any # is present then answer is yes
 » 13 months ago, # |   0 share approach for problem B plz ? thanks in advance ..
•  » » 13 months ago, # ^ |   0 My approach = Question says center of square 3*3 will not be painted rest all elements of 3*3 grid will be painted,so center of matrix can be (2,2) to (n-1,m-1). So for every possible center check for all 8 side boxes and if none of the neighboring cell contains '.' then assign a certain fixed value to all neighboring cells. Repeat this process for whole matrix and at last check this matrix with actual matrix ( i.e if matrix[i][j]=='#' && value not assigned). If both are same then "Yes" else "No".
 » 13 months ago, # | ← Rev. 2 →   +13 Some submissions work with greedy passed problem E may get wrong with this data:4 4 6 1 2 4 31 2 2the answer is 2 but some submissions output 3This kind of submissions start from leaves and go up as far as possible greedily, and continue with a process like topological sort
•  » » 13 months ago, # ^ |   0 I think it will be more fair to rejudge E with stronger data.
•  » » 12 months ago, # ^ | ← Rev. 3 →   0 The idea of starting from leaves and going as far as possible each time is correct. It could time out with strong tests if done naively (i.e. simple dfs), but the answer should be correct.The key is to try to go up as far as possible for all leaves, even if there's a middle vertex that's already included in another path from another leaf. For the sample test you provided, a correct greedy solution would do the following... Process node 3 and make path (3,2) with total weight 6. Process node 4 and make path (4,2,1) with total weight 6. Skip node 2 because it's already included in a path. Skip node 1 because it's already included in a path.
•  » » » 12 months ago, # ^ |   0 The key is to try to go up as far as possible for all leaves, even if there's a middle vertex that's already included in another path from another leaf. why?
•  » » » » 12 months ago, # ^ |   0 Because there can be a case where you try to go up from one leaf and go to a certain vertex v because including the next one would surpass the limit, but the next leaf to the right has a lower value, so you might go up some more ancestors from this one.
•  » » » » » 12 months ago, # ^ |   0 but then you have to disinclude the earlier path, right?
•  » » » » » » 12 months ago, # ^ |   0 Yes, if the problem asked you for the actual paths, you'd need to check what leaf each node corresponds to, but it only asks you the total number of paths.
 » 13 months ago, # | ← Rev. 2 →   0 It is a nice problem set. D is really nice. But i implemented it in a binary search fashion along with the computation of distance square from the given point to the center of circle using euclidian distance. I just used long double and i din check for any precision error. Although I think the error may come in line number 25 and line 38 and 39 in my implementation. I believe there could be more precision checking test cases. Here is my submission https://ide.geeksforgeeks.org/5vmRXdAzE0. Anyhow sincere thanks for the great problem set.
 » 13 months ago, # | ← Rev. 3 →   0 Can anybody help me with D? I know the solution is using ternary search but I can't figure out why my own solution is incorrect or why it is having precision issues.43867521I have done bs over radius and in my check function I have tried to find whether there exists a value of x for this radius.
 » 13 months ago, # | ← Rev. 2 →   +4 Oh my god question D was very very unlucky for me. Take a look at these 2 submissions:The only difference is what you choose to start your binary search from. The AC one has high=1e16, the WA one has high=1e15. The algorithm and formulas are otherwise entirely the same. However #43848961 is JUST outside the precision bounds.I spent the whole contest debugging my code and finally changed my formula to be more numerically stable, but just changing the bound a bit would have AC'd.Plenty of people got AC first try but I see plenty who got WA with the EXACT same formula and just chose an unlucky bound, so it didn't pass pretest 4 (and only pretest 4) due to precision.TLDR; I think the precision for problem D is too tight and a bit unfair.
•  » » » » 12 months ago, # ^ |   0 Something else I'd like to point out: in all of these solutions that you linked, there's a common pattern. The number you take the sqrt out of is computed like this r * r - (y - r) * (y - r), but going an extra step, this can be rewritten as y * (2 * r - y), which is relevant because now you are doing operations on numbers of lower magnitude, therefore reducing the chance for precision errors (which a good programmer will know; as someone else said, this is a programming contest, not a maths contest).As proof, this simple modification on your WA code turns it into AC, with an answer of 49999999999272.4042434692 on test 4, which is orders of magnitude closer to the actual answer than the 50000049523832.28391265869140625000 of your AC solution.
•  » » » » » » » 12 months ago, # ^ | ← Rev. 2 →   0 The problem happens because larger doubles have worse precision. When sqrt(r*r-(r-y)*(r-y)) is calculated, r*r and (r-y)*(r-y) is often is quite large (1e18*1e18) but with a small y value they are too large for the small result to be precise enough.So rearranging the equation to avoid needing r*r is possible: r*r - (r-y)*(r-y) = (r + (r-y)) * (r - (r-y)) If y is in the circle, then it must be true that 2r-y >= 0 and so: sqrt((r + (r-y)) * (r - (r-y))) = sqrt(r+(r-y)) * sqrt(r - (r-y)) = sqrt(2*r-y) * sqrt(y) This way the largest intermediate value used is 2r-y which is no larger than like ~2e18, much better than 1e36 and will have enough precision.