Всем привет!
Завтра (5 октября, 17:35 (UTC+3)) состоится Codeforces Round #514 (Div. 2). Раунд будет рейтинговым для второго дивизиона (рейтинг ниже 2100). Участники из первого дивизиона могут написать контест вне конкурса.
Выражаю благодарность KAN за его помощь с задачами и координацию раунда, Aleks5d и Um_nik за тестирование раунда и, конечно, MikeMirzayanov за замечательные платформы Codeforces и Polygon.
Вам будет предложено 5 задач и 2 часа на их решение.
UPD: разбалловка 500-1000-1500-2000-2500
UPD2: Поздравляем победителей!
Div. 2:
1. qingczha
2. PaidySung
3. Hyperbolic
4. memopaper
5. reku
Оба дивизиона:
1. Radewoosh
2. qingczha
3. natsugiri
4. nuip
5. PaidySung
UPD3: разбор
Удачи!
gl hf
Wow, that's by far the shortest announcement in a while.
Plus, It thanked MikeMirzayanov for his awesome Codeforces and Polygon platforms. :)
Back to back contest...
ohhh Yessss...
Finally, a regular Codeforces round is here after a week of waiting. I love Codeforces.
удачи всем
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
How many did youb solve in the icpc preli?
We did bad in ICPC Preli. Unfortunately we solved only 2 problems. In Problem C and D, we got TLE. WA in Problem J.
It's okay. We didn't do much better either. Solved 3, got AC in J. Which year are you in?
Shortest announcement... Not good.
Hope the problem statements will be as short as the announcement :) .
So concise description.
It is an unforgetable experience to start a contest at midnight.I love Codeforces.
A red problem setter and just div2, it's gonna be hard contest.
It has just 5 problems, so yeah, it's gonna be hard.
I wish everyone gets positive rating changes.
That's quite not possible.
I hope that lack of div.3 contests means that the next gonna be amazing
there're only 5 problems prepared by a red problem setter? gonna be a hard contest
B must candidate to the "worst problem on the year" !
Yes, I can not understand the statement of problem B. Kind of shit!
the problem for me was that he didn't say that we shouldn't include empty cells in the sides of chosen rectangles .
What is test 4 of D problem?
I have the same problem.
2 -10000000 1 10000000 1
The lack of setprecision makes WA then? :)
Actually the most common problem was too low binary search upper bound.
Ye ye already got it thats the second,bigger issue.
Yeah and also the radius is huge so you can't just start your binary search at 1e7
I 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.
Thx, max-radiuos ~ 10^14 !!!!
It will be nice, if D statement was added hint about this restriction, or limitation of x,y coordinates. This is div2 problemset -).
h = abs(y - r); sqrt( r * r - h * h ) ---> WA4sqrt( 2*r*y - y*y) - AC !``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.
This solution does not fit the time limit restriction.
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.
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.
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... :<
what was ur greedy after the binsrch on answer?!
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).
what is your output if the points are (-1e7,1) (+1e7,1) ?
Got my issues now. The upper bound of my binary search was too low (heck, it's insanely high to be honest).
Thanks! :D
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.
I just figured out a way btw :D bet it'd pass all tests in practice :D
I'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 )
The following formula helps to keep calculations <= 1e18.
sqrt(A * A - B * B) = sqrt((A - B) * (A + B)).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
What was ur algorithm btw?
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.
howto solve C ?
HINT: Remove numbers at an odd position's, until there more than 3 elements.
What is the pretest-6 of C?
As I guess: 6
Answer would be:
How do we compare it with 1 1 1 1 3 6?
Your answer is lexicographically smaller (the 4th element is 1, while the optimal one's is 2).
But according to the given statement, j=2(0-based indexing) then a[i]>b[i] is not satisfied for i>j.
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.
The last one is special.
Previous contest haven't got any Editorial even till now. I hope this contest gets an Editorial soon enough.
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.
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.
Probably would have got WA on Test 4, so why bother?
Geometry can never be fun. End of story.
Want fun? Solve some string matching problem, a range query problem, or a nice DP one. Let geometry for math geeks and masochists.
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.
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.
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.
I'm gonna be green like a String in the wind
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.
Problem C was not Math, just IQ test. Don't be tricked by GCD !
I was wondering how to do that...
Ahhhhhhh, I didn't know this was an IQ test, dude. I thought we were in a programming competition!
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.
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.
You got E for dp today.
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.
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.
That sounds way too complicated and too much thought involved for a problem that doesn't require any thinking, just implementation of a technique.
I solved E in 200 lines using 3 segment trees and dp.
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).
If you want dp you think dp
Also, you just need to maintain the stack of vertices in a dfs and do bsearch over it, no need for LCA stuff.
Would the above ideas pass this test?
Edit. Yes, they should.
Yes, my code got 2 as answer.
how to solve B and E?
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
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!
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.
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...
You thought THIS was good?
Well, yeah bro..... you're either too easy-going or you're a math freak. Choose whichever you like.
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.
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.
What lol?
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".
can you please share the idea for E?
I could not solve E in the contest :(
I actually really liked the problems, especially B and C, and I think I have an idea for E...
Problems are more enjoyable to one when one has managed to solve them.
Is E something like finding the topmost vertex you can reach from each vertex, and then starting from the leaves?
Forgive if grossly incorrect.
Well I got AC with that idea (at least on pretests).
can you please explain the idea a little bit more?
How 1e9 computations are possible in 2s on CodeForces (as http://mirror.codeforces.com/contest/1059/submission/43853124)?
Shouldn't it timeout.
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.
It's a little weird of today's problems :)
http://mirror.codeforces.com/contest/1059/submission/43847734 Whats wrong with my submission for C?
How do you solve D?
How fast system testing is done today. WoW.
Hint for problem D https://www.geogebra.org/graphing/gqhms2jk
Координаторы посмотрите сюда плз 1)http://mirror.codeforces.com/contest/1059/submission/43859812
2)http://mirror.codeforces.com/contest/1059/submission/43864411
3)http://mirror.codeforces.com/contest/1059/submission/43864455 Первый код зашел на контесте но упал во время проверки Второй код отослал после проверки и зашло Третий код отослал после того как зашло и получил ТЛ Код во всех один и тот же
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!
Looking through all of your comments so far... you seem to be a very, very angry man
Looking at your avatar, you seem to be a mouse. Are you one?
Yes
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)? 43842790
Bye bye expert :'(
share approach for problem B plz ? thanks in advance ..
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".
Some submissions work with greedy passed problem E may get wrong with this data:
4 4 6
1 2 4 3
1 2 2
the answer is 2 but some submissions output 3
This kind of submissions start from leaves and go up as far as possible greedily, and continue with a process like topological sort
I think it will be more fair to rejudge E with stronger data.
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...
why?
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.
but then you have to disinclude the earlier path, right?
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.
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.
Когда дадите рейтинг?
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.
43867521
I 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.
Oh my god question D was very very unlucky for me. Take a look at these 2 submissions:
AC: https://mirror.codeforces.com/contest/1059/submission/43867295
WA: https://mirror.codeforces.com/contest/1059/submission/43848961
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.
Well... if you look at the correct answer and compare it to the your program's answer, you'll actually find that it's pretty far off. Quite a bad approximation (even the accepted version barely passes the limit). 1e-6 is a standard precision requirement.
I'd say the implementation could use some work. Most people who got accepted had way better (tighter) approximations. I'd say it's LUCKY that your second submission passed (and not unlucky that the first one didn't).
Also... it doesn't really have anything to do with luck. This particular test is easy to think about, it's obvious that it has the highest probability of introducing precision errors and is also very easily to compute by hand (with pen and paper). Therefore, it should be one of the first cases you'd want to check your program on. Not stress-testing your code is your fault, not anybody else's.
TL;DR: try to analyze your mistakes, improve yourself and work to get better instead of blaming the system :)
I got a bit triggered so I'm going to reply:
Here's a bunch of AC's on just one page (most recent at time of writing) which would fail if 0...1e15 was chosen as the binary search bound. Note that this is just a CURSORY glance looking for exactly what I was talking about:
Original (AC): https://mirror.codeforces.com/contest/1059/submission/43912614 Change bounds: (WA): https://mirror.codeforces.com/contest/1059/submission/43920041
Original (AC): https://mirror.codeforces.com/contest/1059/submission/43913915 Changed bounds: (WA): https://mirror.codeforces.com/contest/1059/submission/43920093
Original (AC): https://mirror.codeforces.com/contest/1059/submission/43916864 Changed bounds (WA): https://mirror.codeforces.com/contest/1059/submission/43920289
Original (AC): https://mirror.codeforces.com/contest/1059/submission/43917464 Changed bounds (WA): https://mirror.codeforces.com/contest/1059/submission/43920315
Original (AC): https://mirror.codeforces.com/contest/1059/submission/43918142 Changed bounds (WA): https://mirror.codeforces.com/contest/1059/submission/4392036
Even Radewoosh's solution (AC): https://mirror.codeforces.com/contest/1059/submission/43841799 Fails from precision just by changing the bounds: https://mirror.codeforces.com/contest/1059/submission/43920454
The exact same solution is everywhere on the leaderboard.
If that many solutions with the same incorrect formula pass simply because the author chose a luckier starting bound for their binary search then that means one of 2 things:
We have 1/2 people AC and 1/2 people stuck the entire contest fixing precision, but all of them have the same solution... is that fair? My point isn't complaining and blaming for not doing well, my complaint is that the tests aren't thorough enough to warrant that precision requirement.
You need to understand that.. for test #4, the problem has exactly one mathematical answer: 50000000000000.5
The fact that these solutions that you linked get AC with answers such as 50000044046781.77815247 is ALREADY pretty generous, I would say. You can see that the answer is pretty far off. Other implementations out there yield results like 50000000000000.4949989318847656, which is miles better. The precision margin is there to allow results like these, which are very close to the actual mathematical results (since computers cannot do real number arithmetic perfectly). Making the margin even more generous would be unfair to these "better" solutions. And again, 1e-6 is the standard error. It's pretty much always this in every contest (even tighter on some problems). What would you have it changed to?
Ok, changing the parameters (like the binary bounds) on a "bad" implementation might make it get accepted, but that's simply by luck. What you SHOULD be aiming for is one of those "better" implementations, not changing parameters on "bad" ones in hope that it gets better.
Also, my point about test #4 being the first test you should stress-test your code on still stands.
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 asy * (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.
I know! I know! None of what you said is wrong, it's just not the point.
I'm saying that there should at least be more tests, OR the precision bound should be higher. I'm not saying that all of these WA's should pass, I'm saying that they should either all pass (which you clearly don't like, that's fine) or all fail.
I also notice this when today I am solving the same problem. I just wonder how to implement this in a better way. Would you like to tell me?
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:
If y is in the circle, then it must be true that 2r-y >= 0 and so:
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.
Oh, get it. Thank you very much!
I think task D was a valid problem, since dealing with real numbers' precision is key in competitive programming. However, I think this is a valid suggestion as well. If the problemsetter's intention was for contestants to figure out a thoroughly precise solution, Why does a weak program pass by fixing small details? As far as I am aware of, a good problem should be able to break any solution that is not the intended one, and this one didn't. Not to mention that this is a two-hour contest, where penalty for wrong submissions and delay is significant. Therefore I do believe it is a bit unfair to leave ambiguous constraints, since people will waste too many points on a solution that isn't even supposed to pass.
Good Contest, Quick testing ,Fast editorial. Day made. Thanks codeforces!
Лол, меня дисквалифицировали. Какие-то чуваки скоммуниздили мой код по С, так как я юзал ideone с паблик кодом(не обращал внимание раньше на эти настройки и не думал, что код могут видеть другие) Забавно, что некоторые даже отправили мой код до меня)) Я случайно, не баньте плиз, больше так не буду
Weak tests in E.
I hacked this solution from Giver with the following test (works locally ~50s):
I wonder whether other solutions fail this test as well.
System test for E is so weak. Many O(n2)(worst cases) approaches pass the test, which is unfair for those who employ a correct algorithm of O(n log n).