overwrite's blog

By overwrite, history, 12 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
  • +20
  • Vote: I do not like it

»
12 days ago, # |
  Vote: I like it -8 Vote: I do not like it

up

»
11 days 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.

  • »
    »
    11 days 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.

    • »
      »
      »
      11 days 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
      • »
        »
        »
        »
        11 days 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.

        • »
          »
          »
          »
          »
          11 days 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.

          • »
            »
            »
            »
            »
            »
            11 days 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.

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

                Yes, I understood and then deleted the comment.

»
11 days 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;
}
  • »
    »
    11 days 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?

    • »
      »
      »
      11 days 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.

    • »
      »
      »
      11 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
11 days ago, # |
Rev. 3   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* of L multiplied by 4.

(*) Edit: this should say the integer length of L multiplied by 4.

  • »
    »
    11 days 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?

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

      Hi, I got quite interested in this problem! I'll try to prove that 4*(int)(n*sqrt(2)) always gives the right answer!

      Consider P1=(A,A) as the largest integer pair that lies within the circle bounded by n. The diagonal drawn between the origin and (A,A) with magnitude n will be somewhere on the segment between (A,A) and (A+1,A+1). Then, depending on whether the points P2 and P3 also lie inside the circle our final answer to this problem can be written down as either 4*(2A) or 4*(2A+1). (This is found by counting the dots around the circle)

      Previously I proposed drawing a line L from the positive to the negative diagonal. The end points of L lie on the circle with radius n, and the length of L is exactly L=n*sqrt(2.0). As n crosses the mid-point of the cell (A+0.5,A+0.5) the integer value of L (i.e rounded down) will go from 2A to 2A+1. This is exactly what we need for the answer.

      However, if we think about this carefully, there appears to exists a problematic region between the straight line from P2 to P3 and the arc bounded by those two points. If n where to lie in this region we would definitely get the wrong answer because L would evaluate to 2A+1 where we would want 2A.

      It wasn't actually at all obvious to me why n will never be in this region, but I think I've found a way to show that it cannot exist here.

      To be in this region n would simultaneously have to satisfy 2*n*n > (2A+1)*(2A+1) to lie beyond the line (this is the magnitude of L at the center of the cell), and n*n < (A+1)*(A+1)+A*A to lie within the arc (or circle) (the magnitude taken either at point P2 or P3). The two inequalities can be rewritten as n*n-(2A*A+2A) > 1/2 and n*n-(2A*A+2A) < 1 respectively. For integer values of n and A, the smallest possible positive difference for n*n-(2A*A+2A) is 1, which means both expressions can not be simultaneously satisfied. Therefore, proves that n can never lie inside this region. And further 4*(int)(n*sqrt(2)) (as long as we have accurate floating point calculations) is always a correct solution.