ARC110D

Thoughts.
- With N=2000, O(N^2) would be fine.
- With M=10^9, it seems impossible to do dynamic programming like “the first one is x and the rest are M-x”.
  - Viewing field hockey stick identity → Looks different
- If B is smaller than A, it is zero and can be ignored.
- Distribute the remaining $R = M - \sum A_{i}$ among 2000 boxes
- Since there are about $(R 2000 + R)$ of individual events, they cannot be calculated individually and added together in time.
  - → should be able to be bundled and calculated by some formula transformation.
  - View [binomial coefficient formula
  - Vandermonde’s identity
- $\sum_{i = 0}^{k} (i n) (k - i m) = (k n + m)$
  - It’s a product of binomial coefficients into a single binomial coefficient, which is close to the objective.
  - Adding a lower value is also close to the objective of being constant
  - Cannot be used directly because the value above changes.
  - There must be a formula like a variant of this → let’s find it.
- Write a code to naively calculate $f (A, B, K) = \sum_{i} (i A + i) (K - i B + K - i)$ that you want to get and observe : | 1 | 1 | 1 | 4 | 4C1 | | — | — | — | — | — | | 1 | 1 | 2 | 10 | 5C2 | | 1 | 1 | 3 | 20 | 6C3 |
  - → $f (A, B, K) = (K A + B + K + 1)$
- In the case of Section 3.
  - $\sum_{ij} (i A _{1} + i) (j A _{2} + j) (R - i - j A _{3} + ( R - i - j )))$
  - $= \sum_{i + j} (i + j A _{1} + A _{2} + ( i + j ) + 1) (R - ( i + j ) A _{3} + ( R - ( i + j ))))$
  - $= \sum_{k} (k A _{1} + A _{2} + k + 1) (R - k A _{3} + ( R - k )))$
  - $= (R A _{1} + A _{2} + 1 + A _{3} + R + 1)$
- generally
- $\sum A_{i} + (N - 1) (1 + R)$
  - This is a mistake see addendum A
- Calculating sample 1 with this formula gave 8, but I doubt it because of the messy calculations along the way.
  - I’m supposed to have to come up with all the patterns below R, and I’m using the formula R=1.
- In the first place, R can be about 10^9, so it seems impossible to calculate the binomial coefficient?
  - This is a mistake see addendum B
Official Explanation
- $S = \sum A_{i}$ as $(S + N N + M)$ is the answer
- Since R=M-S $(S + N N + M) = (N + M - R N + M) = (R N + M)$
- Why does this happen?
  - The official explanation in natural language is, in essence, the following formula
  - $\sum_{i} (A i) (B N - i - 1) = (A + B + 1 N)$
- Postscript B
  - Calculation of binomial coefficients
  - I tend to do “create a binomial coefficient table for faster calculation”.
    - I made a library…
  - But when the upper binomial coefficient is 10^9 and the lower is 10^6, as in this case, we should have used $C (n, m) = P (n, m) (m!)^{- 1}$ .
    - This calculation can be done for O(m), so
    - Faster than creating a table of size n
      - Binomial coefficient for huge n
- Postscript A
  - generally
  - $\sum A_{i} + (N - 1) (1 + R)$
    - This is an error.
  - $X = \sum A_{i} + (N - 1) + R$ is correct
    - $R = M - \sum A_{i}$ so $X = M + N - 1$
      - Oh, that one doesn’t fit…
  - This formula only calculates the case where the “value to be assigned” is exactly R
  - The value we want is $\sum_{r = 0}^{R} (r S + N + r - 1)$ - Use field hockey stick identity.
    - $\sum_{i = 0}^{k} (i n + i) = (k n + k + 1)$
  - This increases by 1, and the value we seek is $(R S + N + R)$ .
  - $(R S + N + R) = (S + N S + N + R) = (S + N N + M)$
  - Now we come down to the same formula as in the official explanation.
→ Explanation AC
- formal power series and can be solved by attributing to
- ARC110D_FPS
OEIS
- https://twitter.com/yuruhiya/status/1335222719160315904?s=21
- This time I was judging it by the naked eye, but when I was done, I used OEIS and it was a breeze, so I’ll do that next time.
A path that does not involve “predicting general terms from experimentally constructed sequences.” - I could transform the equation by interpreting it as Collapsing Duplicate Combinations.
- Sort by: ARC110D_nonFPS.

This page is auto-translated from /nishio/ARC110D using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.

🪴 Quartz 4.0

ARC110D

Graph View

Backlinks