Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

chokudai's blog

By chokudai, history, 7 months ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
7 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

»
7 months ago, # |
  Vote: I like it +82 Vote: I do not like it

Geometry... XO

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    44 and 2 for me

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Relatable :P
  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it -30 Vote: I do not like it

    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;
    }
    
»
7 months ago, # |
  Vote: I like it +140 Vote: I do not like it

I hope whoever set today's contest doesn't set any Atcoder Beginner Contests for a while...

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
Rev. 3   Vote: I like it +22 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    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
    • »
      »
      »
      7 months ago, # ^ |
      Rev. 3   Vote: I like it +1 Vote: I do not like it

      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 .

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 .

»
7 months ago, # |
  Vote: I like it +131 Vote: I do not like it
»
7 months ago, # |
  Vote: I like it +56 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is it using binary search?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
7 months ago, # |
  Vote: I like it +7 Vote: I do not like it

C and D were quite tough

»
7 months ago, # |
  Vote: I like it +62 Vote: I do not like it

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

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      I multiplied everything by $$$10^4$$$ and converted everything to int64_t but still didn't get the AC...

      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I multiplied by 10^6 after that, used int128_t and got AC :) but after the round :(

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 3   Vote: I like it +3 Vote: I do not like it

        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
        
        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      C was confusing

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Is that a valid test case ? Following the statement there's no path from the middle '.' to the outer ones.

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              Okkk , Thanks

            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it +5 Vote: I do not like it

              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

              • »
                »
                »
                »
                »
                »
                »
                »
                7 months ago, # ^ |
                  Vote: I like it +5 Vote: I do not like it

                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.

»
7 months ago, # |
  Vote: I like it +67 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

520 pages of D WA

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So, a not horizontal, not vertical line of black cells. Is the one side or multiple sides?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Ewwwww Geometry

»
7 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +25 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Is there somewhere I can see the test cases?

      Why does this fail on some cases?
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Tweak your epsilon until it passes

»
7 months ago, # |
  Vote: I like it +2 Vote: I do not like it

How to solve B?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Output all numbers a[i]!=x

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank You! B looks very tough for me. Ok, How to solve A?

      • »
        »
        »
        »
        7 months ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        if v*s<=d and d<=v*t print "No"

        else print "Yes"

        code

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Wow! nice solution. How to solve C?

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh, I didn't know that, thanks!:D

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What is wrong with my C? Did i misunderstand or something?

C

What I did was count the borders, if any set of points are collinear then dont increment the line counter else increment and push the last 2 points again.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    Code

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you all ill check where I made mistake

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to approach for problem C ?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i counted the no of corner points for C.....am i missing something?

»
7 months ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it
Sad :(
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +21 Vote: I do not like it

How to solve F?

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it +45 Vote: I do not like it

    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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.....

  • »
    »
    7 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it
  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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!

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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)

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

#include <bits/stdc++.h>
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?

»
7 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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 <cstdio>
#include <cmath>
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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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
        
        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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!

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Why does adding 1e-14 to the value of r after taking input, removes the precision errors? What concept is this?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Yes, I have the same doubt. Is it some common technique?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
7 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

Words hiding behind each problem

A
B
C
D
E
F
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      AC at last! Thx for teaching me this useful technique.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes. It increases precision. I too learnt this through this problem.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the editorial of this round be uploaded?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone know how to solve F...

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone stuck or interested to see explanation on problem C. Here is one.

»
7 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

»
7 months ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

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.

Spoiler
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I got 44 AC but 2 WA for 5 consecutive times even with minor adjustments lol

https://atcoder.jp/contests/abc191/submissions/20002757