overwrite's blog

By overwrite, history, 2 days ago, In English

Unfortunately Round #230 does not have not only the editorial but even an announcement and want to know how to solve the following problem.

My approach is as follows: for one quadrant I find number of points with distance d > n — 1 and d <= n that does not lie on the axis. Then I multiply that by 4 (because we have 4 quadrants) and add 4 (because we have 4 points on the axes in total). That seems to be incorrect for n >= 5, I can't get why (for n >= 5 I don't have an integer overflow so the algorithm is incorrect then).

UPD: pranavsindura pointed out why my solution is incorrect. Looking for a correct one.

Thanks.

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

»
41 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

up

»
22 hours ago, # |
  Vote: I like it +6 Vote: I do not like it

Try to manually draw the points on a graph for some small case. Say, n = 3. Mark all the points with euclidean distance at most 3.

Points with distance at most 3

Then, notice that you only need to block the points on the boundary!

Points on the boundary

Here the number of points on the boundary are 16, which is the answer for n = 3.

Also, you can clearly see that it is a symmetric figure so if you can calculate the answer for one quadrant you can find a way to extend it to all the quadrants.

  • »
    »
    19 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for your response.

    But I know all of these, I know that I have to block only boundary points.

    I defined function d(n), which tells me number of points that lie in the circle with center in the origin and radius n.

    From this I get boundary points by d(n) — d(n-1). Which seems to be incorrect. Other info can be found in the original post above.

    • »
      »
      »
      18 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I wrote a simple script that marks all points within the circle. The points marked '5' are in the circle of radius = 5. On top of that the circle of radius = 4 is marked with '4'. Here the boundary of '5's is exactly what d(n) - d(n-1) counts. There are some points which are not on the boundary but are still counted. They are circled red.

      Extra points
      • »
        »
        »
        »
        18 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Do you agree that the answer is (d(n)-d(n-1))*4+4 If I tell you that d(n) is exactly the points in one quadrant that does not lie on axes? That's my approach. See the post above.

        • »
          »
          »
          »
          »
          18 hours ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I dont. It is clear from the image above that d(n) - d(n-1) is not the right way to calculate the boundary points.

          • »
            »
            »
            »
            »
            »
            18 hours ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh, Thanks so much. Now I know why my solution is incorrect. Can you give me any ideas for the correct one? and what about a very simple formula 4*(int)(n*sqrt(2.0))? Can't get why is correct.

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

              (aw i didn't notice that the comment is gone :( )


              Okay, please bear with me. The circle's center is at (0,0) and we will work with integer coordinates. Take point (3,3).

              It does not lie inside the circle of radius = 4, as 3^2 + 3^2 > 4^2.

              It lies inside the circle of radius = 5, as 3^2 + 3^2 <= 5^2. (aw i didn't notice that the comment is gone :( ) (aw i didn't notice that the comment is gone :( ) (aw i didn't notice that the comment is gone :( )

              That means it will be counted in d(5) - d(4), right?

              But do you really need to block it? Once you block (3,4) and (4,3) (which are also boundary points, to the above and right respectively) you no longer need to block (3,3) as it won't be 4-connected with any other point. It is wrong to count it.

              Spoiler
              • »
                »
                »
                »
                »
                »
                »
                »
                17 hours ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Yes, I understood and then deleted the comment.

»
21 hour(s) ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

If you use pranavsindura's idea then sometimes the answer is just 8 times the distance to the point with greatest x-value (x,x). You can find x by x = sqrt(n*n/2)

If (x+1,x) and (x,x+1) are also in the circle you need to add 4 to the answer. One for each of (x,x), (-x,x), (x,-x) and (-x,-x). Check this by (x+1)*(x+1)+x*x <= n*n. Full solution:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
main() {
  ll n, ans;
  cin >> n;
  if (n==0) {
    ans = 1;
  } else {
    ll x = sqrt(n*n/2);
    ans = (x+1)*(x+1)+x*x<=n*n ? 8*x+4 : 8*x;
  }
  cout << ans << endl;
}
  • »
    »
    19 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the response.

    Can you explain why the answer can be as simple as 4*(int)(n*sqrt(2.0))? or at least why my approach is incorrect?

    • »
      »
      »
      18 hours ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      The 4*(int)(n*sqrt(2.0)) is really interesting and nicer than what I had. I think it has something to do with solving for the right-angled triangle n^2 = A^2+A^2 which gives A=n*sqrt(2.0)/2. There are two such pieces per quadrant which suggests multiplying it by 8. But I don't know how it is determined that the int value should be taken at n*sqrt(2.0) exactly.

    • »
      »
      »
      16 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, I figured out this part and posted it separately below!

»
16 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

There's an interesting solution to this problem 4*(int)(n*sqrt(2)), such as here https://codeforces.com/contest/392/submission/96012058

From the diagram we can find L=n*sqrt(2), the answer is the number of integer points on L multiplied by 4

  • »
    »
    15 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "The answer is the number of integer points on L multiplied by 4"

    Why?