### chokudai's blog

By chokudai, history, 3 months 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

 » 3 months 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 months ago, # |   +82 Geometry... XO
•  » » 2 months ago, # ^ |   +18 44 and 2 for me
•  » » 2 months ago, # ^ |   0
•  » » 2 months ago, # ^ |   0
•  » » 2 months ago, # ^ |   +3 Relatable :P
•  » » 2 months 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 months ago, # |   +140 I hope whoever set today's contest doesn't set any Atcoder Beginner Contests for a while...
•  » » 2 months ago, # ^ |   0 @ScarletS Will you upload the unofficial editorial this time? Would be very helpful for us. Thanks
•  » » » 2 months 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 months ago, # | ← Rev. 3 →   +22 How to solve C ? Please also explain the problem statement (maybe by taking few examples) .
•  » » 2 months 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 months 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 months ago, # ^ |   +1 I'm pretty sure it can be concave (and have holes). I think a single black cell would have 4 sides.
•  » » » » » 2 months 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 months 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 months ago, # ^ |   +3 What is defined to be a "side" in this problem? Clearifications made it worse.
•  » » » » 2 months ago, # ^ |   +6 It looked like the clarifications were just google translated from Japanese to English.
•  » » » 2 months ago, # ^ |   0 The statement was a bit confusing as I was treating a triangle to have 3 sides instead of 8
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 if(v[i][j] == '#') { if(v[i][j-1] == '.' && a[i-1][j] == 0 && a[i+1][j] == 0) ++ans; a[i][j] = 1; } etc
•  » » 2 months 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 months ago, # |   +131
 » 2 months 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 months ago, # ^ |   0 Is it using binary search?
•  » » 2 months 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 months ago, # ^ |   +3 I wasn't so lucky :(
•  » » 2 months 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 months ago, # |   +7 C and D were quite tough
 » 2 months 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 months 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 months 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 months ago, # ^ |   0 i used priority queue
•  » » » » 2 months ago, # ^ |   0 Did you submit using Cpython?
•  » » 2 months 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 months ago, # ^ |   0 still tle :(
•  » » » » 2 months ago, # ^ |   +1
•  » » » » » 2 months ago, # ^ |   +1 oh so you were talking abt replacing priority queue..my bad! sorry
 » 2 months ago, # |   0 How do you guys who got ac deal with decimal precisions in D?
•  » » 2 months 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 months ago, # ^ |   0 oh no, I never read that part. I was trying everything to increase precision but it always gave wa
•  » » » 2 months ago, # ^ |   +15 I multiplied everything by $10^4$ and converted everything to int64_t but still didn't get the AC...
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 I multiplied by 10^6 after that, used int128_t and got AC :) but after the round :(
•  » » » » 2 months ago, # ^ |   0 I did the same, How do you convert to int64_t? Try round(x * 10000)
•  » » » 2 months ago, # ^ |   +1 Didn't you use doubles at all? like for square root for example
•  » » » » 2 months 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 months 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 months 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 months 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 months 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 months 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 months ago, # ^ |   0 Problem C was nice. D was painful because of unnecessary complications
•  » » » 2 months ago, # ^ |   0 C was confusing
•  » » » 2 months 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 months ago, # ^ |   +1 Is that a valid test case ? Following the statement there's no path from the middle '.' to the outer ones.
•  » » » » » 2 months 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 months 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 months ago, # ^ |   +5 Okkk , Thanks
•  » » » » » » » 2 months 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 months 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 months ago, # ^ |   0 Thanks Got it :)
•  » » » » » » » » » 2 months ago, # ^ | ← Rev. 3 →   0 ,.....
 » 2 months 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 months ago, # |   +8 520 pages of D WA
 » 2 months 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 months ago, # ^ |   0 Do you mean the clarifications?
 » 2 months 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 months 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 months ago, # ^ |   0 So, a not horizontal, not vertical line of black cells. Is the one side or multiple sides?
•  » » » » 2 months 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 months ago, # |   0 Ewwwww Geometry
 » 2 months ago, # |   +1 Ok! that's enough geometry for few months atleast.
 » 2 months 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 months 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 months 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<
•  » » » » 7 weeks ago, # ^ |   0
•  » » 2 months 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 months ago, # ^ |   0 Tweak your epsilon until it passes
 » 2 months ago, # |   +2 How to solve B?
•  » » 2 months ago, # ^ |   0 Output all numbers a[i]!=x
•  » » » 2 months ago, # ^ |   0 Thank You! B looks very tough for me. Ok, How to solve A?
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   0 if v*s<=d and d<=v*t print "No"else print "Yes"code
•  » » » » » 2 months ago, # ^ |   0 Wow! nice solution. How to solve C?
•  » » » » » 2 months ago, # ^ |   0 One suggestion in your template:You can totally substitute min4, min3 with std::min({a, b, c, d, ..}) by wrapping those variables around an intializer list.You can totally substitute max4, max3 with std::max({a, b, c, d, ..}) by wrapping those variables around an intializer list.
•  » » » » » » 2 months ago, # ^ |   0 Oh, I didn't know that, thanks!:D
 » 2 months ago, # | ← Rev. 2 →   0 What is wrong with my C? Did i misunderstand or something? C//Think simple yet elegant. #include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define x first #define y second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i points,f,s; bool check(){ double slope; int i,ix=100,iy=-100,j; if(points[0].y==points[1].y) slope=1e9; else{ ix=(points[0].x-points[1].x); iy=(points[0].y-points[1].y); } //cout<> h >> w; char g[h][w]; for(i=0;i> g[i][j]; } int cnt=0; for(i=0;i=0;--j){ if(g[i][j]=='#'){ s.pb({i,j}); break; } } } int line=1; //cout<2 && !check()){ // cout<<"xd"; ++line; points.clear(); points.pb(f[i]); points.pb(f[i-1]); } } //cout<2 && !check()){ ++line; points.clear(); points.pb(s[i]); points.pb(s[i-1]); } } line+=2; cout<
 » 2 months ago, # |   0 How to solve E? I used dijkstra and it was pretty bad complexity, failed with TLE and also WA.
•  » » 2 months 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 months ago, # ^ |   +3 Dijkstra works. When you visit the starting node, just update the answer for that node.Code
•  » » 2 months 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 months 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 months 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 months 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 months ago, # ^ |   0 thank you all ill check where I made mistake
 » 2 months ago, # |   +5 How to approach for problem C ?
•  » » 2 months 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 months ago, # |   0 Today I learnt how to parse 5 digits + 4 decimals :D
 » 2 months ago, # |   0 i counted the no of corner points for C.....am i missing something?
 » 2 months ago, # | ← Rev. 3 →   +1 Sad :(
 » 2 months 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 months ago, # ^ |   0 What is the idea for the solution of D?
 » 2 months 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 months ago, # |   0 I cant find test cases after ABC 188. When will it be uploaded?
•  » » 2 months ago, # ^ |   +1 It's up now.
 » 2 months ago, # |   +21 How to solve F?
•  » » 2 months 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 months 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))?
 » 2 months ago, # | ← Rev. 2 →   0 .....
•  » » 2 months 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 months ago, # ^ | ← Rev. 2 →   -15 ...
•  » » 2 months ago, # ^ |   0 Is this test case possible?Here we can't move from every white point to every white point.
•  » » » 2 months ago, # ^ |   0 No it is not possible , I misunderstood it.
 » 2 months ago, # |   0 I got only 3 out of 46 testcases wrong in D. So, close and yet unable to make it full AC.Good to see that atcoder increased it difficulty level
 » 2 months ago, # |   0 For the problem E. Could I solve it by dfs? First I get the minimum cost of the rode for the multipule rode. And then, for each point, use the dfs to find the minimum path, but I get a wrong answer. Is this solution right?
 » 2 months 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 months ago, # ^ |   +1 exactly that happened . I still don't understand why !
 » 2 months 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 months 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 months ago, # |   0 I think problem C and D are quite tough for me, I have no idea about how to solve them. But I think maybe E is quite simple, I used optimized Bellman-Ford algorithm and didn't get any TLEs.
 » 2 months ago, # |   +8
•  » » 2 months ago, # ^ |   0 Yes bro
 » 2 months 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 months 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 months ago, # ^ |   0 OK, rubber duck: I guess it's because "313.9385" is not actually representable in double :(
•  » » » 2 months 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 months 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 months 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 months ago, # |   +5 Why does adding 1e-14 to the value of r after taking input, removes the precision errors? What concept is this?
•  » » 2 months ago, # ^ |   +1 Yes, I have the same doubt. Is it some common technique?
•  » » 2 months 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 months ago, # ^ |   0 Oh yes! I got it. Thank you so much.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Thank you so much as I've been bothered with this 1e-14 for two days!In other words, if any of x, y or r has rounding error so that a grid point is lost, adding 1e-14 to r will take back that point; if no grid point is lost (whether or not there are rounding errors), adding 1e-14 won’t mistakenly add more points (as the precision of x, y and r are so big as 1e-4).Is my interpretation correct?
 » 2 months 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 months 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 months 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 months 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 months ago, # ^ |   +3 after taking r as input, just add this code:-r+=1e-14;
•  » » » 2 months ago, # ^ |   0 AC at last! Thx for teaching me this useful technique.
•  » » » 2 months 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 months ago, # ^ |   0 Yes. It increases precision. I too learnt this through this problem.
 » 2 months ago, # |   0 When will the editorial of this round be uploaded?
•  » » 2 months ago, # ^ |   0 It's up now
 » 2 months ago, # |   0 Anyone know how to solve F...
 » 2 months ago, # |   0 If anyone stuck or interested to see explanation on problem C. Here is one.
 » 2 months 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 months 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); } 
 » 2 months ago, # |   0 I got 44 AC but 2 WA for 5 consecutive times even with minor adjustments lolhttps://atcoder.jp/contests/abc191/submissions/20002757