C2221 - 巧克力金币金字塔

Test Cases 1-2 (10%)

$N \le 6$, $R \le 9$

A simple observation is that $a_i \le R$. Therefore, a brute-force solution can be used to generate all arrays satisfies $a_i \le R$ in $O(NR^N)$. Then for all such arrays (there are $R^N$ of them), use $O(N)$ to check if it satisfies the required limitations.

Time Complexity: $O(NR^N)$

Test Cases 3-5 (15%)

$N \le 10^3$, $R \le 10^3$

Another observation is that when constructing an element in the array, only the preceding element is considered. Therefore dynamic programming can be used to tackle this problem.

Define $dp[i][j]$ to be the number of arrays that can be constructed, with length $i$ and with $a_0 = j$. Then the recurrence relation is $dp[i][j] = \sum\limits_{d|j} dp[i-1][d]$.

Number of states is $O(NR)$, transition time complexity is $O(\log{R})$. Total time complexity: $O(NR\log{R})$.

Test Cases 6-10 (25%)

$N \le 10^6$

Again, another observation is that there is at most $O(\log{R})$ distinct elements in any satisfied array, and it must be non-increasing. Combinatorics can be used to solve this problem.

(below is by sunny who has no time)

C2222

Method 1: Small-to-large merging
Time complexity: $O(n\log^2n)$
Space complexity: $O(n)$
code credits: justin, i changed 1 line of his code to make tle becomes ac
Method 2: Implicit segment tree merging
Time complexity: $O(n\log n)$
Space complexity: $O(n \log n)$
code credits: me

C2223

Method 1: direct bitwise dp
Time complexity: $O(nmk2^m)$
Space complexity: $O(nk2^m)$
code credits: justin
Method 2: plug dp
Time complexity: $O(nmk2^m)$
Space complexity: $O(mk2^m) $
coed credits: me

C2224

Method 1: enumerate the boxes and binary search
Time complexity: $O(\log n \cdot \sum b_i + n \log n + \sum (b_i \log b_i))$ Space complexity: $O(n + \max b_i)$ code credits: henry

Credits

snuny: q2-q4 cases, q2-q3 idea
herny: q2-q4 translation, q4 idea and wrong code
jutsin: q1 idea and cases, q1-q4 testing
joon: system error and 404 not found