44 and 2 for me

Same energy

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

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 <bits/stdc++.h>
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;
}

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

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.

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 .

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 seconds before the contest ended XD.

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.

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

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

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.

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.

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

Do you mean the clarifications?

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.

Multiply input values by 10^4 and do everything in long long. Here's a submission that works (unfortunately after contest T_T).

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

Output all numbers a[i]!=x

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.

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

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

What is the idea for the solution of D?

It's up now.

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

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.

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

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)

Yes bro

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

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.

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.

after taking r as input, just add this code:-r+=1e-14;