polosatic's blog

Trying to speed up cube to O(1)
By polosatic, history, 23 months ago, translation, In English

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.

code (for 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.

Code

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

Spoiler

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:

  1. triangles without any vertices on the line x = a - 1

  2. triangles with some vertices on the line x = a - 1 and with two sides which are parallel to the x-axis or y-axis

  3. other triangles

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:

Proof

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.

Proof

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

Transforms
Implementation

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:

  1. Express c through b, after all c depends on b only
  2. Solve the problem for a <= (b - 1) ^ 2 faster
  3. Solve the problem for acute triangles.

It will be hard.

UPD6: We can speed up the solution to O(b^5) using this idea

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

Comments Comments (11)
| Write comment?
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by polosatic (original revision, translated revision, compare)

→ Reply
»
23 months ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

The right triangle problem is OEIS A077435

EDIT: OEIS A189814 gives the answer for rectangles.

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

    Thank you! I was quite sure that problem with right triangles can be solved in O(a * b) But unfortunately, f(n, n) also is not a polynomial of one variable.

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

    OMG! I used too small ai for interpolation with constant b, so it didn't work. After using ai >= b ^ 2 everything works!

    → Reply
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Very nice

→ Reply
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

A not-implemented solution: let the triangle be tree vectors $$$a,b,c$$$.brute force $$$b-a$$$, and you will get $$$\dfrac{c-a}{|c-a|}$$$(which is rotate it for 90 deg(you can asumme ccw or cw))(In program, you can do it by a ). then you can brute force $$$c-a$$$ by $$$O(a + b)$$$. Then the problem is:

find how many triangles with vector $$$b-a=v$$$ and $$$c-a=w$$$?

which is trival.

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    If I understand you correctly, I have already implemented this solution in UPD3 of this blog

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

      No. This solution is $$$O(ab(a+b))$$$.

      UPD3 is Brute force b-a and c-a, find if b-a ⊥ c-a and find how many triangles with vector b-a and c-a.

      But we can just brute force $$$|c-a|$$$(The length of c-a). the angle of $$$c-a$$$ is found by rotate $$$b-a$$$.

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

        Wow! Good idea! Thank you.

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

          why $$$O(a^2b^2(a+b))$$$ is $$$O(b^5)$$$? may $$$a \gg b^2$$$.

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

            The solution in UPD5 needs to calculate

            f((b - 1) ^ 2 + 1, b) and f((b - 1) ^ 2 + 2, b) to calculate f(a, b), it works in O(b ^ 6), but can be optimized to O(b ^ 5) using your method.

            → Reply