YouKnowCipher's blog

Counting Incongruent Triangles from Sequential Sticks in O(1)
By YouKnowCipher, history, 3 weeks ago, In English

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.

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

»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply