chokudai's blog

By chokudai, history, 2 years ago,

We will hold AtCoder Beginner Contest 191.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

• +6

| Write comment?
 » 2 years ago, # | ← Rev. 2 →   +5 I will record a screencast and an editorial and publish them on my YT channel shortly after the contest. Screencast will be here once processed, and there won't be an editorial because I don't want to look at these problems ever again.
 » 2 years ago, # |   +82 Geometry... XO
•  » » 2 years ago, # ^ |   +18 44 and 2 for me
•  » » 2 years ago, # ^ |   0
•  » » 2 years ago, # ^ |   0
•  » » 2 years ago, # ^ |   +3 Relatable :P
•  » » 2 years ago, # ^ | ← Rev. 2 →   -30 Here is my solution below which I came up after contest. In general, the key for AC is to translate the entire problem to discrete space by multiplying input by 10000. Moreover, even after multiplying long double by 10000, you can not just assign it to int64_t. You should use llroundl instead. #include using namespace std; using lli = int64_t; using ld = long double; lli g = 10000; lli dist(lli x1, lli y1, lli x2, lli y2) { return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); } lli bsearch(lli x, lli y, lli r, lli y1, lli l, lli h, bool fl) { lli ans = LLONG_MAX; while (l <= h) { lli mid = l + (h - l) / 2; mid -= mid % g; if (dist(x, y, mid, y1) <= r * r) { ans = mid; (fl ? l : h) = mid + (fl ? g : -g); } else (fl ? h : l) = mid + (fl ? -g : g); } return ans; } lli calc(lli x, lli y, lli r, lli y1) { lli rx = x; rx -= rx % g; lli mid = LLONG_MAX; if (dist(x, y, rx, y1) <= r * r) mid = rx; else if (dist(x, y, rx + g, y1) <= r * r) mid = rx + g; if (mid == LLONG_MAX) return 0; lli rl = x - r; lli rr = x + r; rl -= rl % g; rr -= rr % g; rr += g; lli l = bsearch(x, y, r, y1, rl, mid, false); lli h = bsearch(x, y, r, y1, mid, rr, true); return (h - l) / g + 1; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); ld xd, yd, rd; cin >> xd >> yd >> rd; lli x = llroundl(xd * ld(g)); lli y = llroundl(yd * ld(g)); lli r = llroundl(rd * ld(g)); lli ans = 0; for (lli y1 = y - y % g; y - y1 <= r; y1 -= g) ans += calc(x, y, r, y1); for (lli y1 = y - (y % g) + g; y1 - y <= r; y1 += g) ans += calc(x, y, r, y1); cout << ans << endl; return 0; } 
 » 2 years ago, # |   +140 I hope whoever set today's contest doesn't set any Atcoder Beginner Contests for a while...
•  » » 2 years ago, # ^ |   0 @ScarletS Will you upload the unofficial editorial this time? Would be very helpful for us. Thanks
•  » » » 2 years ago, # ^ |   0 Usually I only write one if I AK the contest, but unfortunately I suck at geometry problems :/ Someone else has made a good one here which might help you :)
 » 2 years ago, # | ← Rev. 3 →   +22 How to solve C ? Please also explain the problem statement (maybe by taking few examples) .
•  » » 2 years ago, # ^ | ← Rev. 3 →   +1 iterate in normal fashion, but maintain whether for previous cell you have considered a side or not. So let me show an example: ..... .#.#. .###. ..... Here, there are 8 sides. We maintain for each cell, whether we have considered white cell that is $L, R, U, D$ to it. So for black cell at $(1,1)$, we have white cell at left, therefore for black cell $(2, 1)$ we will not consider left white cell as a side. Example image
•  » » » 2 years ago, # ^ | ← Rev. 3 →   +1 In the problem is it possible that polygon can be concave or will it be always convex ? And for single black cell in whole grid , will it be polygon with 4 sides or zero sides ?UPD : It can be concave . lemongrab edited his comment after i made this comment .
•  » » » » 2 years ago, # ^ |   +1 I'm pretty sure it can be concave (and have holes). I think a single black cell would have 4 sides.
•  » » » » » 2 years ago, # ^ | ← Rev. 3 →   0 "we can travel between any two squares painted white by repeatedly moving up, down, left, or right while going through only white squares. (Note that the outermost squares in the grid are all painted white.)"Doesn't this mean the polygon has no holes, since if it has one or more holes, the outer white boarders can't connect to those holes?
•  » » » » » 2 years ago, # ^ | ← Rev. 3 →   0 Man i coded the bfs on the grid for this problem but forgot to consider the case when it has holes . SHIT , I will see a good negataive though my account is new. 5 5 ..... .###. .#.#. .###. ..... The output is 8, but how , There is no way to go from other white to the one in middle.
•  » » » 2 years ago, # ^ |   +3 What is defined to be a "side" in this problem? Clearifications made it worse.
•  » » » » 2 years ago, # ^ |   +6 It looked like the clarifications were just google translated from Japanese to English.
•  » » » 2 years ago, # ^ |   0 The statement was a bit confusing as I was treating a triangle to have 3 sides instead of 8
•  » » 2 years ago, # ^ |   0 You will just have to know one thing that you have new side in left if the one above you doesn't have side in left and same if for right . And you have a side above if one to left of you doesn't have a side above you and same for down . JUST traverse the array and do the above mentioned operation .
 » 2 years ago, # |   +131
 » 2 years ago, # |   +56 What was the point of setting X, Y and R to real numbers instead of integers? It's useless complications and I'm sure many contestants solved the problem but did not get accepted because of precision issues
•  » » 2 years ago, # ^ |   0 Is it using binary search?
•  » » 2 years ago, # ^ |   0 Seriously!! I was wondering what had gone wrong. Turned out I was comparing A < B instead of A — B < epsilon. Luckily, got AC 3 seconds before the contest ended XD.
•  » » » 2 years ago, # ^ |   +3 I wasn't so lucky :(
•  » » 2 years ago, # ^ |   0 Probably because it would be too easy if all the input is integer. I think the author of problem D wants us to know how to deal with precision issues.PS: I couldn't solve it during contest too... xD But at least I learn something new after I finally make it AC.
 » 2 years ago, # |   +7 C and D were quite tough
 » 2 years ago, # |   +62 Huge thanks to ABCs for letting me become sooooooo aware of floating point errors! I was never so afraid of them before.
 » 2 years ago, # | ← Rev. 2 →   0 Anyone else getting TLE for 1 test case using Djikstra on E!? https://atcoder.jp/contests/abc191/submissions/20001075 my code
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 No, did you use priority queue or the one with V^2 complexity? Passed easily in python (PyPy 3) with the priority queue.
•  » » » 2 years ago, # ^ |   0 i used priority queue
•  » » » » 2 years ago, # ^ |   0 Did you submit using Cpython?
•  » » 2 years ago, # ^ | ← Rev. 3 →   +1 Replace the priority_queue with multiset, my runtime was reduced by an entire order of magnitude. I don't know why though.
•  » » » 2 years ago, # ^ |   0 still tle :(
•  » » » » 2 years ago, # ^ |   +1
•  » » » » » 2 years ago, # ^ |   +1 oh so you were talking abt replacing priority queue..my bad! sorry
 » 2 years ago, # |   0 How do you guys who got ac deal with decimal precisions in D?
•  » » 2 years ago, # ^ |   +21 I noticed that the decimals had at most 4 digits after the decimal place so I multiplied X Y and R by 10^4 to ensure my code never uses decimal calculations. You do have to be careful with long overflow.
•  » » » 2 years ago, # ^ |   0 oh no, I never read that part. I was trying everything to increase precision but it always gave wa
•  » » » 2 years ago, # ^ |   +15 I multiplied everything by $10^4$ and converted everything to int64_t but still didn't get the AC...
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 I multiplied by 10^6 after that, used int128_t and got AC :) but after the round :(
•  » » » » 2 years ago, # ^ |   0 I did the same, How do you convert to int64_t? Try round(x * 10000)
•  » » » 2 years ago, # ^ |   +1 Didn't you use doubles at all? like for square root for example
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   +3 I don't think we need sqrt, the condition to check if a point is inside a circle would be (x-a)*(x-a) + (y-b)*(y-b) <= r*r 
•  » » » » » 2 years ago, # ^ |   0 Oh so you use binary search instead of computing the answer in O(1) to save precision. I see that's clever thank you!
•  » » 2 years ago, # ^ |   0 I made two changes. Got input as string, then converted to long double. After that, while comparing A < B, I used A-B < epsilon. Not sure if the first change made any difference. I was desperate the last few minutes and tried whatever came to my mind.
•  » » » 2 years ago, # ^ |   0 I also read input as string. I didn't think that would make any difference but it actually made me go from 5 wa to 2 wa.
•  » » » » 2 years ago, # ^ |   0 You are right, it definitely doesn't make a difference. I made a submission which differs from WA submission only in reading the input and it still got WA. So problem is with comparing two floating point numbers directly.
 » 2 years ago, # |   +4 Unfortunately C with low quality. The selection for D was doubtful last week. I hope we will get back to usual quality soon.
•  » » 2 years ago, # ^ |   0 Problem C was nice. D was painful because of unnecessary complications
•  » » » 2 years ago, # ^ |   0 C was confusing
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 Problem C's statement was not clear man.Even the clarification as well. BTW can you tell me that the polygon in C can have holes on not in itself and if yess how is there a way to go from every white vertice to every other white vertice . 5 5 ..... .###. .#.#. .###. ..... answer is 8 , but how is there a path
•  » » » » 2 years ago, # ^ |   +1 Is that a valid test case ? Following the statement there's no path from the middle '.' to the outer ones.
•  » » » » » 2 years ago, # ^ |   0 I too think that it is not valid , but I think the only TC I didn't covered was of holes , Can you link your solution to problem C.
•  » » » » » » 2 years ago, # ^ |   +1 A polygon cannot have holes in this problem, a hole would mean 2 disconnected components of '.', which is not valid.Here is my submission. It counts vertices of the polygon instead of holes.
•  » » » » » » » 2 years ago, # ^ |   +5 Okkk , Thanks
•  » » » » » » » 2 years ago, # ^ |   +5 Can you Please explain your solution why you have you done res&1 and what does at least mean in "How many sides does it have (at least)" in question
•  » » » » » » » » 2 years ago, # ^ |   +5 res&1 checks if res is odd. A convex corner has white on 3 sides and a concave one on 1 side. He has checked for black but it is the same thing.
•  » » » » » » » » » 2 years ago, # ^ | ← Rev. 3 →   0 ,.....
 » 2 years ago, # |   +67 I don't like D. In my opinion, it does not fit the other AtCoder's values that I noticed in other contests.
 » 2 years ago, # |   +8 520 pages of D WA
 » 2 years ago, # |   +1 Why there isn't any pop-up(prompt) on the screen in Atcoder if there is any correction or anything? It is there in the codeforces and even in Atcoder(but only when the contest ends).
•  » » 2 years ago, # ^ |   0 Do you mean the clarifications?
 » 2 years ago, # |   +1 I spent a lot of time trying to decipher the problem statement of problem C and...still have no idea what I'm supposed to do.
•  » » 2 years ago, # ^ |   0 I understand it from this announced clarification:Please consider that square (i, j) occupies the region consisting of the points satisfying i — 1 <= x <= i and j — 1 <= y <= j. For a white square and a black square that are adjacent to each other, we consider the boundary between them to be painted black.The phrase "Consider the part of the grid that is painted black as a polygon" means we consider the polygon such that its interior, including the circumference, matches the part painted black.
•  » » » 2 years ago, # ^ |   0 So, a not horizontal, not vertical line of black cells. Is the one side or multiple sides?
•  » » » » 2 years ago, # ^ |   +3 It's like you are given a figure with some area, take a pen and draw boundary of figure, and it's boundary lines are horizontal and verticalThen you have to find minimum n such that this is a polygon..
 » 2 years ago, # |   +1 Ok! that's enough geometry for few months atleast.
 » 2 years ago, # |   +25 How to handle precision issues in D , I have made 18 wa penalties in D still getting wa on a single test case out of 46 ... :(
•  » » 2 years ago, # ^ | ← Rev. 2 →   +13 Multiply input values by 10^4 and do everything in long long. Here's a submission that works (unfortunately after contest T_T).
•  » » » 2 years ago, # ^ |   0 Is there somewhere I can see the test cases? Why does this fail on some cases?#include using namespace std; const long long int mod = 1000000007; const long long int big = 2999999999999999999; const long long int small = -2999999999999999999; #define ll long long int #define pb(a) push_back(a) #define vll vector #define loop(i, n) for(long long int i=1;i<=n;i++) #define loop0(i, n) for(long long int i=0;i #define vpll vector> ll x, y, r; long double ix, iy, ir; void in2(ll& a, ll& b) { in(a); in(b); } void in3(ll& a, ll& b, ll& c) { in(a); in(b); in(c); } bool inside(ll j, ll i) { return (i-x)*(i-x) + (j-y)*(j-y) <= r*r; } int main() { cin>>ix>>iy>>ir; x = 10000*ix; y = 10000*iy; r = 10000*ir; ll ans = 0; ll st = (y-r)/10000; st *= 10000; for(ll yy = st; yy <= y+r; yy += 10000) { ll left = (x-r)/10000, right = (x+r)/10000; left *= 10000; right *= 10000; ll finalLeft = -1, finalRight = -1; while(left <= right) { ll mid = (left+right)/20000; mid *= 10000; if(inside(yy, mid) && !inside(yy, mid-10000)) { finalLeft = mid; break; } else if(inside(yy, mid) && inside(yy, mid-10000)) { right = mid-10000; } else { left = mid+10000; } } if(finalLeft == -1) continue; left = (x-r)/10000; right = (x+r)/10000; left *= 10000; right *= 10000; while(left <= right) { ll mid = (left+right)/20000; mid *= 10000; if(inside(yy, mid) && !inside(yy, mid+10000)) { finalRight = mid; break; } else if(inside(yy, mid) && inside(yy, mid+10000)) { left = mid+10000; } else { right = mid-10000; } } ans += finalRight-finalLeft+10000; } cout<
•  » » » » 2 years ago, # ^ |   0
•  » » 2 years ago, # ^ |   0 Similar case this side. Looking at the stats for problem D (29 pages of AC, while 565 pages of WA) many faced the same situation :/ Precision > Accuracy XD
•  » » 2 years ago, # ^ |   0 Tweak your epsilon until it passes
 » 2 years ago, # |   +2 How to solve B?
•  » » 2 years ago, # ^ |   0 Output all numbers a[i]!=x
 » 2 years ago, # |   0 How to solve E? I used dijkstra and it was pretty bad complexity, failed with TLE and also WA.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +6 bfs/dijkstra the dist from all cities to all other cities. Then find foreach city the minimum sum of dist from city to any other city and back. Consider selfloops (road from a to a) separate.Be aware that roads are oneway.
•  » » 2 years ago, # ^ |   +3 Dijkstra works. When you visit the starting node, just update the answer for that node.Code
•  » » 2 years ago, # ^ |   +3 Yes, use dijkstra for every node. Just take care not to assign dis=0 to the node from where you are starting dijkstra.
•  » » » 2 years ago, # ^ |   +3 Alternatively, you can take dist[source] = 0 and add a condition while calculating the final answer.See my solution for that. https://atcoder.jp/contests/abc191/submissions/19992934
•  » » 2 years ago, # ^ |   +3 Classic dijkstra for all nodes but make d[s] as inf. Also when going from s(starting node) to any other node, remember to consider d[s] as 0. Finally for s the answer would be d[s].
•  » » 2 years ago, # ^ |   +9 I solved it using Dijkstra as follow :Step 1 : Let's remove multiple edges and self loops If there are multiple edges between A and B, we can just keep the smallest weight . Also, for self loop, ignore them in the graph, but keep a track of them somewhere else. Step 2 : Run usual Dijkstra n times and come up with [n][n] matrix where [i][j] denotes minimum cost of the path i to j. Step 3 : Fill in back self loops and set [i][i] to the lowest self loop if it exists . Step 4 : For each vertex, find another vertex(maybe same) and check for the sum [i][j] + [j][i] . Pick the minimum. Code
•  » » » 2 years ago, # ^ |   0 thank you all ill check where I made mistake
 » 2 years ago, # |   +5 How to approach for problem C ?
•  » » 2 years ago, # ^ |   +2 Count corners, number of corners is number of edges. Just keep in mind that there can be concave as well as convex corners.
 » 2 years ago, # |   0 Today I learnt how to parse 5 digits + 4 decimals :D
 » 2 years ago, # | ← Rev. 3 →   +1 Sad :(
 » 2 years ago, # |   0 God knows when will I learn to handle doubles ;( Can anybody help where might be precision errors in my Solution, I got 2 WA constantly.
•  » » 2 years ago, # ^ |   0 What is the idea for the solution of D?
 » 2 years ago, # | ← Rev. 2 →   0 A, B, C, E : sosoD : get f**ked by precision issuesF : didn't get to see it after 10 WA @ D(still getting WA on D btw sending HELP)
 » 2 years ago, # |   0 I cant find test cases after ABC 188. When will it be uploaded?
•  » » 2 years ago, # ^ |   +1 It's up now.
 » 2 years ago, # |   +21 How to solve F?
•  » » 2 years ago, # ^ | ← Rev. 3 →   +45 Observation #1: Any number resulting in the end should be less or equal to the current minimum.Observation #2: At any given time we can discard all elements of the current list and keep the minimum.You should see now that the answer to the problem is the number of distinct GCD's we can get from subsets the initial array, that are less than the current minimum.Generate all divisors of every number in $O(n\sqrt{n})$ and then save every divisor less or equal to the minimum of the array. Then, for each such divisor, check if the gcd of all its multiples in the array is equal to it. If so increment the answer.We like to assume that each number has roughly $O(\log n)$ divisors so we'll find at most $O(n\log A)$ such divisors where A is the max number in the arrayComplexity: $O(n^2\log A)$ where A is the max number in the array
•  » » » 2 years ago, # ^ |   0 "We like to assume that each number has roughly O(logn) divisors so we'll find at most O(nlogA) such divisors where A is the max number in the array"Can you please explain why we assume that each number has roughly O(logn) divisors? (we are counting only those divisors that are less or equal to the minimum of the array? And why would that be O(logn))?
•  » » » 5 months ago, # ^ | ← Rev. 3 →   0 why should we generate all divisors when we can do the following :for(int i=0;i
 » 2 years ago, # | ← Rev. 2 →   0 .....
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 I don't think there is a way for a polygon to have holes without disobeying the constraints. The example you gave disobeys the constraint:"All dots are connected by going in one of the four directions through only white dots"The dot in the middle is disconnected from the rest
•  » » » 2 years ago, # ^ | ← Rev. 2 →   -15 ...
•  » » 2 years ago, # ^ |   0 Is this test case possible?Here we can't move from every white point to every white point.
•  » » » 2 years ago, # ^ |   0 No it is not possible , I misunderstood it.
 » 2 years ago, # |   +5 Why in problem DThis doesn't work https://atcoder.jp/contests/abc191/submissions/20010273But this works https://atcoder.jp/contests/abc191/submissions/20010300
•  » » 2 years ago, # ^ |   +1 exactly that happened . I still don't understand why !
 » 2 years ago, # |   +8 I tried to solve D but got 3 WA. Here is the submission. Then I found that my solution was very similar to the earliest submission made by one of the writers. The only differences between the two solutions were the first one (my submission) used double but the second one used long double, and the second one used nextafter() but the first one didn't. I changed double to long double but still got 2 WA (and the wrong test cases were different, click here to see it). I added nextafter() to my solution so that I got AC (click here to see it). Then I changed back from long double to double and I still got 4 WA (and the wrong test cases were also different, click here to see it). Can someone please explain the effect of the function nextafter() and why I got WA? Or can you please give me a test case that can make my first solution wrong? Thanks so much!
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 Try:36.0 13.2 40.8 (Answer should be 5222)24.0 29.2 13.2 (Answer should be 549)If you discover what the problem is let me know, my solution using long longs has the same problem, but it works with long double and nextafter. The problem in my case are usually when X coordinate is already a integer (double counting) but I couldn't fix it. (If there is a point which is exactly x^2+(y-yc)^2 == r^2 and X coordinate is integer).EDIT: My AC code was incorrect (output was 548 for case 2)
 » 2 years ago, # |   +8
•  » » 2 years ago, # ^ |   0 Yes bro
 » 2 years ago, # |   0 So regarding D I have the following dummy "solution": #include using namespace std; using ll = long long; using ld = long double; using ull = unsigned long long; #define FOR(i, j, k, in) for (ll i = j; i < k; i += in) #define RFOR(i, j, k, in) for (ll i = j; i >= k; i -= in) #define REP(i, j) FOR(i, 0, j, 1) #define RREP(i, j) RFOR(i, j, 0, 1) ll dist(ll cx, ll cy, ll x, ll y) { return (cx - x) * (cx - x) + (cy - y) * (cy - y); } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll multi = 10000; ld tx, ty, tr; cin >> tx >> ty >> tr; ll x = (ll)(tx * (ld)multi), y = (ll)(ty * (ld)multi), r = (ll)(tr * (ld)multi); ll r2 = r * r; ll xlow = x - r; xlow -= xlow % multi; ll xhigh = x + r; xhigh += multi - xhigh % multi; ll ylow = y - r; ylow -= ylow % multi; ll yhigh = y + r; yhigh += multi - yhigh % multi; ll total = 0; FOR(i, xlow, xhigh + multi, multi) { FOR(j, ylow, yhigh + multi, multi) { if (dist(i, j, x, y) <= r2) total++; } } cout << total << endl; return 0; } What's odd about this is that it differs from accepted solutions of the problem on various inputs like "9646.9314 4394.792 6719.9786". I think that's bad since the code above obviously solves the problem. My assumption is that some of the test cases contain one off errors due to numerical instability of the calculations which can happen with floating point numbers but not with integers. Am I missing something here or is this really an issue?
 » 2 years ago, # |   +11 I spent quite some time trying to upsolve D. After downloading some of the AC solutions and generating random cases against mine, it turns out I got WA in a few random cases because of not using round when converting the radius to integer.I'm still not sure, why is it needed? For example: #include #include using namespace std; int main() { double r = 313.9385; printf("%.6lf\n", r*10000); // ok, prints 3139385.000000 printf("%lld\n", (long long)round(r*10000)); // ok, prints 3139385 printf("%lld\n", (long long)(r*10000)); // ??, prints 3139384 return 0; } For context, here's the accepted solution: https://atcoder.jp/contests/abc191/submissions/20017357.
•  » » 2 years ago, # ^ |   0 OK, rubber duck: I guess it's because "313.9385" is not actually representable in double :(
•  » » » 2 years ago, # ^ |   0 I'm still not sure I understand how does rounding help with that. Also how did you find out that it's not representable as a double?
•  » » » » 2 years ago, # ^ |   +3 I'm still not sure I understand how does rounding help with that. The way I understand it, since the exact value cannot be represented, the value stored is less than what you actually want (something like 313.9384XXX...). You can verify this by printing the result with more decimal points. For example, using "%.18lf" outputs 313.938499999999976353. Thus, the radius you read is actually less than the intended. Multiplying that by a (representable) scale value doesn't really help, since you are still chopping that last digit when keeping the integer part with a simple cast.If the value is representable in first place, round has no effect, because after you multiply by the representable scale, the resulting value is representable and guaranteed to be an integer since the problem says no more than 4 decimal digits. (Example: "313.9384" is representable and round(313.9384 * 10000) == round(3139384.0) == 3139384).If the value is not representable, then round will change it towards the closest representable integer. (Example: "313.9385" is not representable and round(313.938499999999976353 * 10000) == round(3139384.99999999976353) == 3139385). This keeps the original value in the scaled context.Probably other things work as well, such as adding a small epsilon which would not change the values in the scaled context but would have the same effect as rounding towards the nearest integer. Also how did you find out that it's not representable as a double?  string s = "313.9385"; double x = stod(s); cout << (fetestexcept(FE_INEXACT) ? "inexact" : "exact") << '\n'; printf("%.18lf\n", x * 10000); // inexact // 3139384.999999999534338713 
•  » » » » » 2 years ago, # ^ |   +3 Thanks for the detailed explanation! For some reason I naively thought that when one converts to an integer type from a floating point type there is a rounding happening there. Apparently the fractional part gets chopped off and that's it. I didn't even know about "fetestexcept" or the existence of the "FE_INEXACT" flag. Nice job debugging this!
 » 2 years ago, # |   +5 Why does adding 1e-14 to the value of r after taking input, removes the precision errors? What concept is this?
•  » » 2 years ago, # ^ |   +1 Yes, I have the same doubt. Is it some common technique?
•  » » 2 years ago, # ^ |   +4 This solves rounding problems because the rounding errors are smaller than 1e-14. On the other hand, there is no number so near to the desired result that adding 1e-14 would make a change.Actually this is a common technique. On every comparation of values such EPS is added, so that values differing in less than EPS behave like equal values.
•  » » » 2 years ago, # ^ |   0 Oh yes! I got it. Thank you so much.
 » 2 years ago, # |   0 can someone please help me out with problem E, i am getting tle in 6 cases,but my logic seems to be n^2*log(n), like I am doing dijkstra for every node . Here is my submission link(i have made my code clear and easy to read) submission.
•  » » 2 years ago, # ^ |   0 After pop of the node from the queue, you should check if the poped value is the same as the one in the d array.Because if it is not then you can ignore that value, hence do not iterate all adj of that vertex.
 » 2 years ago, # | ← Rev. 2 →   +10 Words hiding behind each problem ASimple physics isn't that hard, is it? BJust Implement what the statement tells you CTry to understand me if you can! DHahaha, yet another geometry problem! you love them, don't you?(Warning: you might see some horrible stuff when submitting for this problem (e.g. AC×45 WA×1)) EI'm S T A N D A R D! FYou expected something easier since D was hard, right?(Quite harder than usual for me, but... OK, that's fine! lol)
 » 2 years ago, # |   0 I am always getting WA of the test cases "handmade_marginal_00.txt" and "handmade_marginal_04.txt" for Prob D. Is there anyone who also had faced the problem and knows how to fix the code?
•  » » 2 years ago, # ^ |   +3 after taking r as input, just add this code:-r+=1e-14;
•  » » » 2 years ago, # ^ |   0 wow man, it really worked. I mean, how and why did it? Is this because it forces our solutions to be extra precise because of the DDDDDD.DDDD0000000001 thing?
•  » » » » 2 years ago, # ^ |   0 Yes. It increases precision. I too learnt this through this problem.
 » 2 years ago, # |   +4 I attempted the problems after the contest (solving A-E), and uploaded my stream here: https://youtu.be/d5FaKqYwLzYIn particular, I implemented D without floating-point numbers, which may be of interest.
 » 2 years ago, # | ← Rev. 7 →   0 Could some one please help in figuring out the mistake in my code in problem D . I have used binary search method and i have multiplied all the input values to $10^4$ . It's giving WA on 5 test cases .UPD : I found my mistake . Don't forget to parse the input i.e try to read it in a way so that there is no precision loss . For example 77706.2925 is stored as 77706.29249999 and if you don't take rounding then it will be stored as 777062924 after multiplying with 1e4. Whereas if you do rounding as given in following spoiler , it will be stored as 777062925. Spoilerll read(){ long double x; cin>>x; return llround(x * 10000); } 
 » 5 months ago, # | ← Rev. 2 →   0 In problem Faccording to this solution in editorial, the time complexity is O(N sqrt(max_Ai)log(max_Ai)).how this time complexity get accepted answer without TLE ?
 » 5 months ago, # |   0 in problem fwhy this code get AC but this code get WA although they are same ?