Does anyone have idea about? Seems to be O(n^2D)

Thank you, sir. This simple example just enlightens me.

Anyone elaborate how greedy works in problem Ex?

In jiangly's solution, why should we sort f[0] and f[1] from large to small, match the large elements and recursively operate on the smaller ones? have no idea how to prove it.

Thank you! Here is a problem (CF 816.E) relate to the second technique.

In the TLE Submission, the default dp value is 1e9. This means that when you call the solve function and the current dp[i][valX][valY] is 1e9, it keeps doing recursion.

Assume current state is valX=10, valY=10, and the suffix of the input data is like [..., {1,1}, {1,1}, {1,1}, {1,1}]. We cannot subtract valX and valY to 0 even if we use all the suffix, so the dp[i][valX][valY] is 1e9. When you visit this state again, LINE21 check that the dp value is 1e9 and still need to be searched. The runtime would be exponential to n in the worst case.

Generally speaking, it's a bad idea to mix the UNVISITED status and the INVALID status when we do dfs with memorization.

The default dp value should also be changed. Change 1e9 in LINE21 and LINE43 into -1.

The main issue is that the parameter valX and valY is the solve funciton may be negative, and lead to many useless states. Since we only care about whether we have enough x and y, so change LINE22 into return dp[i][valX][valY] = min(1 + solve(i + 1, max(0, valX - v[i].ff), max(0, valY - v[i].ss)), solve(i + 1, valX, valY)); would just be fine.

Because the typename in the PBDS should be long long instead of int.

Same question here. AC 57 tests and failed 3 tests. While NTT on half of the polynomial got AC.

Let's fix N = 50, and we want to estimate what the maximum LCM could be. This is equivalent to, if we partition N to be $$$N = a_{1} + a_{2} + ... + a_{m}$$$，the LCM would be $$$LCM = lcm(a_{1}, a_{2}, ..., a_{m})$$$. Apparently we should make every $$$a_{i}$$$ to be coprime with others, to avoid loss of LCM. So an optimal solution to this would be: $$$a_{1} = 1, a_{2} = 4, a_{3} = 5, a_{4} = 7, a_{5} = 9, a_{6} = 11, a_{7} = 13, LCM = 180180$$$. 180180 is a loose upper bound, considered that some numbers in [1, 180180] won't be a valid LCM(some large prime, etc.). Actually for N=50, there are only 1056 valid LCM. So enumerating all possible LCMs would be easily fit in the time limit.

Agree. Maybe we should set a offset according to div 1/2/3. -200~-100 to div3, +100~+200 to div1 imo

Use the picture in the editorial. Take the grid as 0-indexed. We want to go to (H-A-1,i) from (0,0), and there are $$$C_{H-A-1+i}^{i}$$$ ways to do it. Then we go one step down to (H-A,i), one way to do it. Finally go from (H-A,i) to (H-1,W-1), $$$C_{A-1+W-i-1}^{W-X-1}$$$ ways to do it. Note that choosing different i guarantee the paths to be different. So the final answer is: $$$\sum_{i=b}^{W-1}C_{H-A-1+i}^{i} * C_{A-1+W-i-1}^{W-X-1}$$$

Using this formula, we can implement it by enumerating i, and precalculate factorial to calculate combinations in O(logMOD) time for each call. The total time complexity should be O(H+WlogMOD).

Maybe there are solutions using inclusion-exclusion principal. Here are some problems in Atcoder relate to it. Grid 1 Grid 2

Agreed. In my opinions, problems in ABCs is more "educational" and "introductory", while ARC needs more math skills and derivations.

For me, I realized that the problem F is something related to SA at the first glance of it. But I only know the general idea of SA and didn't know the details in its implementation. I copy/paste code from oi-wiki, but I mistook variable "sa" for "rk" when calculating answer and couldn't debug out of it during contest! I feel like a donkey after realizing my foolish mistakes. This contest really teach me a great lesson on SA