Trying to speed up cube to O(1)

Правка en2, от polosatic, 2023-02-04 18:37:15

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.

Теги math, formula, problem

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en16 Английский polosatic 2023-02-07 09:55:02 82
ru18 Русский polosatic 2023-02-07 09:54:01 93
ru17 Русский polosatic 2023-02-07 05:28:56 129
en15 Английский polosatic 2023-02-07 05:27:56 131
en14 Английский polosatic 2023-02-07 05:25:34 35 Tiny change: 's together, then the' -> 's together and their product remains the same, then the'
ru16 Русский polosatic 2023-02-06 19:10:33 6
en13 Английский polosatic 2023-02-06 19:09:11 4916 Tiny change: ' < b`, let`s swap the' -> ' < b`, let's swap the'
ru15 Русский polosatic 2023-02-06 18:23:23 26 Мелкая правка: 'реугольник. Ясно, чт' -> 'реугольник второго типа. Ясно, чт'
ru14 Русский polosatic 2023-02-06 17:59:05 5245 Мелкая правка: 'видно.\n\n### Нако' -> 'видно.\n\n\n**UPD5:**\n### Нако'
en12 Английский polosatic 2023-02-05 15:32:48 368
ru13 Русский polosatic 2023-02-05 15:32:17 368
ru12 Русский polosatic 2023-02-05 14:43:45 5 Мелкая правка: 'm\n{\n ld x0 = 0, x' -> 'm\n{\n int x0 = 0, x'
en11 Английский polosatic 2023-02-05 14:43:27 5 Tiny change: 'm\n{\n ld x0 = 0, x' -> 'm\n{\n int x0 = 0, x'
en10 Английский polosatic 2023-02-05 14:39:44 22 Tiny change: '* (b - 1)`\n' -> '* (b - 1)`, but it was obvious.\n'
ru11 Русский polosatic 2023-02-05 14:38:59 53 Мелкая правка: 'е нашел :(\n' -> 'е нашел :(, кроме `x2 = b * (b - 1)`, что и так было очевидно.\n'
en9 Английский polosatic 2023-02-05 14:38:03 123 Tiny change: 'nything :(\n' -> 'nything :( except that `x2 = b * (b - 1)`\n'
ru10 Русский polosatic 2023-02-05 14:34:51 107
ru9 Русский polosatic 2023-02-05 14:31:11 1617 Мелкая правка: ' b ^ 2`.\n**UPD4:*' -> ' b ^ 2`.\n\n**UPD4:*'
en8 Английский polosatic 2023-02-05 14:29:36 1612
en7 Английский polosatic 2023-02-05 13:13:18 14 Tiny change: 'stand why interpolation doesn't w' -> 'stand why the formula doesn't w'
ru8 Русский polosatic 2023-02-05 13:12:54 71
en6 Английский polosatic 2023-02-05 13:11:58 81 Tiny change: 'tion doesn`t work wit' -> 'tion doesn't work wit'
en5 Английский polosatic 2023-02-05 13:08:43 2 Tiny change: ' use `ai >= b ^ 2`.\n' -> ' use `ai > b ^ 2`.\n'
ru7 Русский polosatic 2023-02-05 13:08:28 1 Мелкая правка: 'вать `ai >= b ^ 2`.\n' -> 'вать `ai > b ^ 2`.\n'
ru6 Русский polosatic 2023-02-05 12:46:30 1100 Мелкая правка: 'n\nТеперь у могу испо' -> 'n\nТеперь я могу испо'
en4 Английский polosatic 2023-02-05 12:41:12 1081 Tiny change: '}\n }\n return ans' -> '}\n }\n return ans'
ru5 Русский polosatic 2023-02-04 20:45:05 204
en3 Английский polosatic 2023-02-04 20:43:23 188 Tiny change: ', a > 1.\n**UPD:**' -> ', a > 1.\n\n**UPD:**'
ru4 Русский polosatic 2023-02-04 18:38:00 100
en2 Английский polosatic 2023-02-04 18:37:15 106
ru3 Русский polosatic 2023-02-04 18:36:35 4 Мелкая правка: ') = 2 * a * a - 4`, a >' -> ') = 2 * a ^ 2 - 4`, a >'
ru2 Русский polosatic 2023-02-04 18:24:17 107 Мелкая правка: 'for the nuber of rig' -> 'for the number of rig'
en1 Английский polosatic 2023-02-02 16:59:49 2162 Initial revision for English translation
ru1 Русский polosatic 2023-02-02 16:29:41 2268 Первая редакция (опубликовано)