Hello, Codeforces. Recently I invented a problem. Consider a set of points (x, y) with integer coordinates, 0 <= x < a и 0 <= y < b. We want to know the number of acute triangles with vertices at given points.
Trying to interpolate
We can write function f(a, b) which finds the answer and works in (ab) ^ 3
. I suggested that it is a polynomial of two variables with degree <= 6. I tried to interpolate it using this theorem. But my code finds non-zero coefficients with monoms with degrees > 6, so my hypothesis was not confirmed. I also failed with right triangles.
This code finds a coefficient with a ^ (C1 - 1) * b ^ (C2 - 1)
What I would like to know:
- can this problem be solved faster than O(stupid(a, b))
- can this problem be solved in O(1)
- maybe, someone knows problems with difficult to find formulas and this method can help to find them?
UPD: Found formula for the number of right triangles with b = 2: f(a, 2) = 2 * a ^ 2 - 4
, a > 1.
UPD2: Many thanks to bronze_coder for finding O(1)
solution for constant b: OEIS A189814.
Interpolation should use ai > b ^ 2
.
UPD3: Finally wrote a O((ab) ^ 2)
solution.
Now I can interpolate using bigger values of a
and b
.
But it is quite strange for me that the number of right triangles is directly proportional to (ab) ^ 2
instead of (ab) ^ 3
. Now I will try to understand why the formula doesn't work with ai <= b ^ 2
.
UPD4: Code that finds a formula for f(a, b) for a > b ^ 2
and works in O(b ^ 6)
:
I used OEIS to find a regularity between the coefficients of P, but i didn't find anything :( except x2 = b * (b - 1)
, but it was obvious.
UPD5:
Finally found a formula and solution in O(min(a, b) ^ 6)
If a < b
, let's swap them. Now we need to solve it in O(b ^ 6)
. If a <= (b - 1) ^ 2 + 1
, we can run solution in O((ab) ^ 3)
= O(b ^ 6)
. Now we need to solve it for a > (b - 1) ^ 2 + 1
.
Definitions
Consider all right triangles and divide them into 3 types:
triangles without any vertices on the line
x = a - 1
triangles with some vertices on the line
x = a - 1
and with two sides which are parallel to the x-axis or y-axisother triangles
Obviously, third type triangles have exactly one vertex on the line x = a - 1
. Let C(a)
be the number of third type triangles (some function).
The number of second type triangles is (a - 1) * b * (b - 1) / 2 * 4
:
By definition, for every vertex (x, y) of first type triangles, 0 <= x < a - 1
and 0 <= y < b
, then the number of the triangles is f(a - 1, b)
, by definition of f
.
Well, f(a, b) = f(a - 1, b) + (a - 1) * b * (b - 1) / 2 * 4 + C(a)
Let's prove that C(a)
for every a > (b - 1) ^ 2 + 1
has same values.
C(a)
is a constant. Let c
be this constant.
Well, f(a, b) = f(a - 1, b) + (a - 1) * b * (b - 1) / 2 * 4 + c
. After some transforms, we get a formula for f(a, b)
using f((b - 1) ^ 2 + 1, b)
.
Unfortunately, the value of c
is different for different values of b
and I could not find a regularity between them. Interpolation and OEIS did not help me. There are some things I should do:
- Express
c
throughb
, after allc
depends onb
only - Solve the problem for
a <= (b - 1) ^ 2
faster - Solve the problem for acute triangles.
It will be hard.
UPD6: We can speed up the solution to O(b^5)
using this idea