Codeforces Round #853 (Div. 2) Editorial

Codeforces Round #853 (Div. 2) Editorial

2 days ago, # | In A complexity is , or you can check that in somehow? In F to estimate we can consider the following bijection: let's take white balls and 5 black balls and put them in a linear order. White balls will denote letters of the string, 2nd and 4th black balls will denote where we split our string in 3 parts, and 1st/3rd/5th black balls will denote where in each of 3 strings we stay in DP. Thus there is a bijection between orders of balls and all DP states over all ways to split the string into 3 parts (actually we allow splits with empty parts, so it's even a bit smaller than this). The number of ball orders is , thus

• 2 days ago, # ^ | Thanks for sharing! I'll fix the typo in A. :)

  • 43 hours ago, # ^ | ← Rev. 7 →   +17 It's possible to solve it fastly. How to Quickly Calculate the GCD in E (Bonus) and A Bonus of E: The only algorithm costing in the official solution is calculating GCD. However, we can calculate for all in : since satisfying (this property is also called "Multiplicative"), we can use Euler's sieve to calc it in , solving the bonus of E. Bonus of A: there's a well-known tech that can also solve A in precalc and per query (where and the number of pairs of GCD we query is in this problem). You can solve this problem (on a mainland Chinese OJ, Luogu).

    • 43 hours ago, # ^ | But in this case, O(SIZE+K) will be of the order of 10^6 per case, so won't it be slower than O(n^2) as n<=100?

      • 39 hours ago, # ^ | ← Rev. 4 →   +14 It's my typo. Initialization only runs once. Fixed&thx. In fact we only run initialization like a Euler's sieve to reduce the range to and precalc for all (Like the bonus of E) within and we can query any in .