Блог пользователя YouKnowCipher

Counting Incongruent Triangles from Sequential Sticks in O(1)
Автор YouKnowCipher, история, 3 недели назад, По-английски

Problem statement: You are given an integer $$$n$$$. There are n sticks of length $$$1, 2, 3, ..., n$$$. You find to find out how many incongruent triangles can be formed by using three of the given sticks. Output the result modulo $$$10^{12} + 9$$$.

Constraint: $$$4 < n < 10^{12}$$$, where $$$n$$$ is a positive integer.

My idea: I analyzed some base cases. After that, I transformed the problem into an equation with a nested loop. After resolving the nested loop, I determined the number of triangles, denoted as $$$x$$$, to be,

$$$x=\sum_{i=1}^{n} \left\lceil i \cdot \frac{i+1}{2} \right\rceil + 2 \cdot \sum_{i=1}^{n} \left\lceil \frac{i+1}{2} \right\rceil - \sum_{i=1}^{n} \left\lceil \frac{i+1}{2} \right\rceil^2 - n(n+1) $$$

I can't optimize it for the ceiling function. It is working on $$$O(n)$$$. But the constraint of the problem is: $$$4 < n < 10^{12}$$$. Therefore, we can't iterate over n. However, Can it be simplified? (Can we express this equation without using the summation sign?)

Thanks in advance for your assistance.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
3 недели назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Doing it with $$$O(1)$$$ !!! It seems impossible to me.

→ Ответить
»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

$$$i(i+1)/2$$$ is an integer, as one of either $$$i$$$ or $$$(i+1)$$$ must be even, so the ceiling function essentially disappears and you can use the usual formulas for $$$\sum i$$$ and $$$\sum i^2$$$.

For the remaining ones, notice that the pattern of $$$\lceil (i+1) / 2 \rceil$$$ is $$$1, 2, 2, 3, 3, 4, 4, \dots$$$. You can infer some formulas from here based on whether $$$n$$$ is odd or even.

→ Ответить