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

Автор YouKnowCipher, история, 2 недели назад, По-английски

This is the first contest where I solved the full problem set. That's why, to celebrate this achievement, I am writing an editorial about my implementations. If I made any mistakes or typos, please let me know.

1999A — A+B Again?

Hint
Tutorial
Implementation

B — Card Game

Hint
Tutorial
Implementation

C — Showering

Hint
Tutorial
Implementation

D — Slavic's Exam

Hint
Tutorial
Implementation

E — Triple Operations

Hint
Tutorial
Implementation

F — Expected Median

Hint
Tutorial
Implementation

G1 — Ruler (easy version)

Hint
Tutorial
Implementation

G2 — Ruler (hard version)

Hint
Tutorial
Implementation

Полный текст и комментарии »

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

Автор 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
  • Проголосовать: не нравится