1
\$\begingroup\$

Consider an \$n \times n\$ grid of integers which is part of an infinite grid. The top left coordinate of the \$n \times n\$ grid of integers is \$(0, 0)\$.

The task is to find a circle which when overlaid on the grid gives the largest sum of values inside it. The constraints are:

  • The circle has its centre at \$(x, x)\$ for some value \$x\$ which is not necessarily an integer. Notice that both dimensions have the same value.
  • The radius of the circle is \$r\$ and is not necessarily an integer.
  • The circle must include the point \$(0, 0)\$ within it.
  • All points outside of the \$n \times n\$ grid contribute zero to the sum.
  • The center of the circle can be outside the \$n \times n\$ grid provided the other conditions are met.

Here is a picture of a \$10 \times 10\$ grid with two circles overlaid.

enter image description here

The larger circle has its center at \$(-20, -20)\$.

The two parameters are therefore \$x\$ and \$r\$. Although there are in principle an infinite number of options, in fact only a finite subset are relevant.

The matrix in this case is:

[[ 3 -1  1  0 -1 -1 -3 -2 -2  2]
 [ 0  0  3  0  0 -1  2  0 -2  3]
 [ 2  0  3 -2  3  1  2  2  1  1]
 [-3  0  1  0  1  2  3  1 -3 -1]
 [-3 -2  1  2  1 -3 -2  2 -2  0]
 [-1 -3 -3  1  3 -2  0  2 -1  1]
 [-2 -2 -1  2 -2  1 -1  1  3 -1]
 [ 1  2 -1  2  0 -2 -1 -1  2  3]
 [-1 -2  3 -1  0  0  3 -3  3 -2]
 [ 0 -3  0 -1 -1  0 -2 -3 -3 -1]]

The winning criterion is worst case time complexity as a function of \$n\$. That is using big Oh notation, e.g. \$O(n^4)\$.

\$\endgroup\$
8
  • \$\begingroup\$ Is centroid on (x,x) or (x,y), requiring two axis be same? \$\endgroup\$
    – l4m2
    Commented Jan 7 at 14:46
  • \$\begingroup\$ @l4m2 The center of the circle has to be at (x, x). That is (-4, -4), (1, 1) etc. Does that answer your question? \$\endgroup\$
    – Simd
    Commented Jan 7 at 14:50
  • \$\begingroup\$ OK. It's just not that reasonable so I confirm. so a circle cover (x,y) iff it cover (y,x) \$\endgroup\$
    – l4m2
    Commented Jan 7 at 14:56
  • 2
    \$\begingroup\$ @NickKennedy It's just based on coverage of the grid points. \$\endgroup\$
    – Simd
    Commented Jan 7 at 17:35
  • 1
    \$\begingroup\$ If you replaced the hard boundary with a Gaussian kernel weighting, you could maybe do gradient descent. the problem kind of reminds me of SVMs. \$\endgroup\$
    – qwr
    Commented Jan 21 at 4:19

1 Answer 1

1
+200
\$\begingroup\$

Python 3, O(n^4)

def CPos(x1, y1, x2, y2):
	return (x1*x1-x2*x2+y1*y1-y2*y2)/2/(x1-x2+y1-y2)

def f(A):
	Ret = A[0][0]
	n = len(A)
	for baseY in range(n):
		for baseX in range(n):
			if baseY == 0 and baseX == 0:
				continue
			dBase = abs(baseX - baseY)
			Sum = 0
			Buf = [[[CPos(baseX, baseY, 0, 0), 1], 0, 0]]
			for y in range(n):
				for x in range(n):
					d = abs(x - y)
					if x+y <= baseX+baseY:
						Sum = Sum + A[y][x]
						if d > 0 and x+y < baseX+baseY:
							Buf += [[[CPos(baseX, baseY, x, y), 2], -A[y][x]]]
					else:
						if d < 0:
							Buf += [[[CPos(baseX, baseY, x, y), 0], A[y][x]]]
			Buf = sorted(Buf, key=lambda k: k[0]) # Radix sort
			i = 0
			if Ret < Sum:
				Ret = Sum
			while len(Buf[i]) < 3:
				Sum = Sum + Buf[i][1]
				if Buf[i][0] != Buf[i+1][0]:
					if Ret < Sum:
						Ret = Sum
				i = i + 1
	return Ret

Try it online!

For each point assume the circle go through it(Base[XY]), then radius decrease from infinity. Store when the points enter/leave circle, sort it and only consider these step.

\$\endgroup\$
1
  • \$\begingroup\$ This is very cool. I will try to understand what your method is exactly. \$\endgroup\$
    – Simd
    Commented Jan 15 at 14:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.