We will hold AtCoder Beginner Contest 191.

- Contest URL: https://atcoder.jp/contests/abc191
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210206T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 6
- Writer: evima, Eugle_na, kyopro_friends, QCFium, tatyam, tozangezan
- Rated range: ~ 1999

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

We are looking forward to your participation!

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.

Geometry... XO

44 and 2 for me

Same energy

Me,too. The solution used double and the solution used long double.

Relatable :PHere 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 multiplyinglong double by 10000, you cannotjust assign it to int64_t. You should usellroundlinstead.I hope whoever set today's contest doesn't set any Atcoder Beginner Contests for a while...

@ScarletS Will you upload the unofficial editorial this time? Would be very helpful for us. Thanks

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 :)

How to solve C ? Please also explain the problem statement (maybe by taking few examples) .

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 imageIn 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 .

I'm pretty sure it can be concave (and have holes). I think a single black cell would have 4 sides.

"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?

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.

What is defined to be a "side" in this problem? Clearifications made it worse.

It looked like the clarifications were just google translated from Japanese to English.

The statement was a bit confusing as I was treating a triangle to have 3 sides instead of 8

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 .

I_HATE_GEOMETRY

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

Is it using binary search?

Seriously!! I was wondering what had gone wrong. Turned out I was comparing A < B instead of A — B < epsilon. Luckily, got AC 3

secondsbefore the contest ended XD.I wasn't so lucky :(

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.

C and D were quite tough

Huge thanks to ABCs for letting me become sooooooo aware of floating point errors! I was never so afraid of them before.

Anyone else getting TLE for 1 test case using Djikstra on E!? https://atcoder.jp/contests/abc191/submissions/20001075 my code

No, did you use priority queue or the one with V^2 complexity? Passed easily in python (PyPy 3) with the priority queue.

i used priority queue

Did you submit using Cpython?

Replace the priority_queue with multiset, my runtime was reduced by an entire order of magnitude. I don't know why though.

still tle :(

Sure?

oh so you were talking abt replacing priority queue..my bad! sorry

How do you guys who got ac deal with decimal precisions in D?

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.

oh no, I never read that part. I was trying everything to increase precision but it always gave wa

I multiplied everything by $$$10^4$$$ and converted everything to

`int64_t`

but still didn't get the AC...I multiplied by 10^6 after that, used int128_t and got AC :) but after the round :(

I did the same, How do you convert to int64_t? Try round(x * 10000)

Didn't you use doubles at all? like for square root for example

I don't think we need sqrt, the condition to check if a point is inside a circle would be

Oh so you use binary search instead of computing the answer in O(1) to save precision. I see that's clever thank you!

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.

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.

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.

Unfortunately C with low quality. The selection for D was doubtful last week. I hope we will get back to usual quality soon.

Problem C was nice. D was painful because of unnecessary complications

C was confusing

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 pathIs that a valid test case ? Following the statement there's no path from the middle '.' to the outer ones.

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.

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.

Okkk , Thanks

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

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.

,.....

I don't like D. In my opinion, it does not fit the other AtCoder's values that I noticed in other contests.

520 pages of D WA

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).

Do you mean the clarifications?

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.

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.So, a not horizontal, not vertical line of black cells. Is the one side or multiple sides?

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 vertical

Then you have to find minimum n such that this is a polygon..

Ok! that's enough geometry for few months atleast.

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 ... :(

Multiply input values by 10^4 and do everything in

`long long`

. Here's a submission that works (unfortunately after contest T_T).Is there somewhere I can see the test cases?

Why does this fail on some cases?https://www.dropbox.com/sh/nx3tnilzqz7df8a/AAAYlTq2tiEHl5hsESw6-yfLa?dl=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

Tweak your epsilon until it passes

How to solve B?

Output all numbers a[i]!=x

How to solve E? I used dijkstra and it was pretty bad complexity, failed with TLE and also WA.

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.

Dijkstra works. When you visit the starting node, just update the answer for that node.

Code

Yes, use dijkstra for every node. Just take care not to assign dis=0 to the node from where you are starting dijkstra.

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

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].

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

thank you all ill check where I made mistake

How to approach for problem C ?

Count corners, number of corners is number of edges. Just keep in mind that there can be concave as well as convex corners.

Today I learnt how to parse 5 digits + 4 decimals :D

Sad :(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.

What is the idea for the solution of D?

A, B, C, E : soso

D : get f**ked by precision issues

F : didn't get to see it after 10 WA @ D

(still getting WA on D btw sending HELP)

I cant find test cases after ABC 188. When will it be uploaded?

It's up now.

How to solve F?

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 array

Complexity: $$$O(n^2\log A)$$$ where A is the max number in the array

"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))?

why should we generate all divisors when we can do the following :

for(int i=0;i<n;i++){

for(int j=i+1;j<n;j++){

}

}

.....

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

...

Is this test case possible?Here we can't move from every white point to every white point.

No it is not possible , I misunderstood it.

Why in problem D

This doesn't work https://atcoder.jp/contests/abc191/submissions/20010273

But this works https://atcoder.jp/contests/abc191/submissions/20010300

exactly that happened . I still don't understand why !

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 functionThanks so much!`nextafter()`

and why I got WA? Or can you please give me a test case that can make my first solution wrong?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)

gand-phati-rating-giri

Yes bro

So regarding D I have the following dummy "solution":

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?

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:

For context, here's the accepted solution: https://atcoder.jp/contests/abc191/submissions/20017357.

OK, rubber duck: I guess it's because "313.9385" is not actually representable in double :(

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?

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.

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!

Why does adding

`1e-14`

to the value of r after taking input, removes the precision errors? What concept is this?Yes, I have the same doubt. Is it some common technique?

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.

Oh yes! I got it. Thank you so much.

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.

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.

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)

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?

after taking r as input, just add this code:-

`r+=1e-14;`

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?Yes. It increases precision. I too learnt this through this problem.

I attempted the problems after the contest (solving A-E), and uploaded my stream here: https://youtu.be/d5FaKqYwLzY

In particular, I implemented D without floating-point numbers, which may be of interest.

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.

SpoilerIn problem F

according 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 ?

in problem f

why this code get AC but this code get WA although they are same ?