Hello everyone, we are happy to announce that the 2nd Universal Cup has started officially.

The Universal Cup is a non-profit organization dedicated to offering training resources for competitive programming teams. Our website is https://ucup.ac/ (in English and Chinese).

In the previous season, over 750 teams from more than 300 affiliations all over the world, registered and participated in a total of 22 stages, encompassing contests from Asia, Europe, and America.

With the permission of contest setters and without involving copyright disputes, the Universal Cup will hold mirror contests for some undisclosed competition sets. It is expected to hold at least 20 contests in this season. We will simulate the actual situation in the competition, executing the board freeze in the last hour. At the same time, we will provide an overall rating board, which will help the team to make a reasonable assessment of itself.

Over the past few weeks, the committee has worked hard to schedule stages and try to improve the competing experience for participants. We are very excited to share some information here as a head up:

• In the upcoming 2nd Universal Cup, starting from September 2nd, 2023, we have already scheduled 14 high-quality stages from Asia and Europe mainly. The current schedule can be viewed on the main page of our website https://ucup.ac/.

• There are also 4 stages (expected on October 7th, 14th, 21st, and December 9th) in confirming. The schedule in the second half will also be updated later.

• We have managed to upgrade our judging system on QOJ, and we will use it as the contest platform starting this season. To provide more flexibility, instead of 3 fixed time windows, teams now can choose to start to compete in one of the following 6 windows as they want:

  • 13:00 (UTC +8) on Saturday ~ 18:00 (UTC +8) on Saturday
  • 16:00 (UTC +8) on Saturday ~ 21:00 (UTC +8) on Saturday
  • 19:00 (UTC +8) on Saturday ~ 24:00 (UTC +8) on Saturday
  • 21:00 (UTC +8) on Saturday ~ 02:00 (UTC +8) on Sunday
  • 23:00 (UTC +8) on Saturday ~ 04:00 (UTC +8) on Sunday
  • 02:00 (UTC +8) on Sunday ~ 07:00 (UTC +8) on Sunday

• For teams that have already registered, if they have done at least 3 contests in the previous season, their account will be preserved and enrolled into the current season automatically. Otherwise, the same as new teams, please register following the instructions on Registration.

• The official website has been upgraded. You are able to view all information from the previous by simply choosing the corresponding season on the website.

The first contest will be the stage Qingdao on September 2nd, 2023. The contest source is The 2018 ACM-ICPC Asia Qingdao Regional Online Contest prepared by SUA Problem Setter Team. For a great number of Chinese teams, we believe this will be a good practice to prepare for the upcoming ICPC preliminary online contests in late September.

As well as many other future stages, this stage will be uploaded to Gym afterward. We are grateful to MikeMirzayanov for letting us advertise Universal Cup in Codeforces and providing the great platform Codeforces and Polygon to help prepare contests. We are also very thankful to all contest setters of stages for your support to the Universal Cup. If any setter would like to propose a stage, please feel free to contact us.

Universal Cup Committee:

• Jingbang chenjb Chen
• Yuhao jqdai0815 Du
• Lingyu jiangly Jiang
• Yaowei Sugar_fan Lyu
• Qingyu Qingyu Shi
• Yaohui quailty Zeng

(Sorted by lexicographical order of the last name)

Hello Codeforces! The 11th Stage of the 1st Universal Cup is coming. It will be held from April 8th to 9th. It is also a replay of the 2022 ICPC East Continent Final Contest, which was held on March 24, 2023 — March 26, 2023.

As usual, we have three time windows for participating. You can participate in the contest in the following three time windows:

• April 8th 13:00 — 18:00 (UTC +8)
• April 8th 19:00 — 24:00 (UTC +8)
• April 9th 02:00 — 07:00 (UTC +8)

Please note that you can see two scoreboards in DOMjudge. The 'Local Scoreboard' shows the standings ONLY IN THE CURRENT TIME WINDOW. And the 'Combined Scoreboard' shows all participants, including the onsite participants, and the cup participants in the previous time windows.

• Contest link: https://domjudge.qoj.ac/
• Onsite Scoreboard: TBD
• Universal Cup Scoreboard: https://qoj.ac/ucup/scoreboard

As usual, we plan on uploading the contest onto Codeforces Gym after the stage.

About Universal Cup:

The Universal Cup is a non-profit organization dedicated to providing training resources for competitive programming teams. Up to now, there are more than 500 teams from all over the world registering for Universal Cup.

A more detailed introduction: https://codeforces.me/blog/entry/111672

• Register a new team: https://ucup.ac/register (Registration requests will be processed before each stage.)

• Results of the past stages: https://ucup.ac/results

• Terms: https://ucup.ac/terms

• Ratings: https://ucup.ac/rating

Hello Codeforces! The 10th Stage of the 1st Universal Cup is coming. It will be held from Apr 1th to 2th.

The contest is based on a "simple" contest, Yuhao Du Contest 11. It was used in the Osijek Competitive Programming Camp 2023 Winter. Teams that participated in the camp can have their camp results included in the final standings. Thanks to the judges and authors for preparing this great contest and sharing with us as a Universal Cup Stage.

This contest consists of some problems I wrote in recent two years and some new problems. Most problems are not published before, but some problems are public, or well-known in China. If you solved problems I wrote in private training contests or some contests including ZJOI 2020 and SDOI 2022, please skip this round.

As usual, we have three time windows for participating. You can participate in the contest in the following three time windows:

• Apr 1st 13:00 — 18:00 (UTC +8)
• Apr 1st 19:00 — 24:00 (UTC +8)
• Apr 2nd 02:00 — 07:00 (UTC +8)

Please note that you can see two scoreboards in DOMjudge. The 'Local Scoreboard' shows the standings ONLY IN THE CURRENT TIME WINDOW. And the 'Combined Scoreboard' shows all participants, including the onsite participants, and the cup participants in the previous time windows.

Contest link: https://domjudge.qoj.ac/

Universal Cup Scoreboard: https://qoj.ac/ucup/scoreboard

About Universal Cup:

Universal Cup is a non-profit organization dedicated to providing trainings for competitive programming teams. Up to now, there are more than 500 teams from all over the world registering for Universal Cup.

A more detailed introduction: https://codeforces.me/blog/entry/111672

Register a new team: https://ucup.ac/register (the registration request will be processed before each stage)

Results of the past stages: https://ucup.ac/results

Terms: https://ucup.ac/terms

Ratings: https://ucup.ac/rating

Since competitive programming is dying, and I'm almost retired, so it's time to review the problems I authored.

Hi everyone! I wanted to write such a blog for a long time, motivated by similar blogs, by antontrygubO_o, by adamant and by tibinyte. This is not a super-comprehensive list. I set many shit problems that I don't want to share for some local contests.

It can be long, and I'm not sure if I have finished half of them yet.

The number of asterisks after the label indicates the recommendation levels. One asterisk means this problem is worth reading. Two asterisks mean this problem is one of my favorite problems, Three asterisks mean this problem is one of my best problems.

There are some examples that there are similar problems in math contests (I can't distinguish if it's deliberately copied from math contests or just a coincidence).

• 317E Princess and Her Shadow, which is almost the same as a problem from Canadian National Olympiad link

• 618F Double Knapsack, see the discussion here

• 1684H Hard Cut, see the discussion here

• K in Yuhao Du Contest 5. Yes, I admit the idea is from a problem in All-Russian MO link

Sometimes authors just learn the idea from MO problems. But sometimes, the problem is just identical (like 1684H).

I don't think there is much difference between copying problems from math contests and copying problems from an old opencup contest. However, the community seems much more tolerable of copying problems from math contests.

Maybe the difference is that the opencup problems are known to more participants. So copying problems from math contests has less impact.

Some updates:

For all problems mentioned above, solutions are almost the same as MO problems they correspond to.

The following are more examples that share the same setting with MO problems, but the solutions are not very similar. I feel these problems are ok.

• HDU 4660, commented by MinakoKojima. It shares the same setting with IMO 2011, Q2. But this problem is asking different things.

• I in Yuhao Du Contest 7. It shares the same setting with IMOSL 2009, C5. But it's much harder than that IMOSL problem. So I feel knowing this IMOSL problem doesn't help.

• A Chinese problem. It's definitely inspired by RMM 2019 Q3. And they share a similar idea. But I feel it's not bad since there are still several steps (however, basically implementation issues) to make the proof in the RMM problem work in this problem.

• D in Tianjin 2012. And this problem also happens in a recent Chinese team training contest. As far as I remember, there is a similar IMO problem in the 1990s. But I didn't remember the exact source.

A problem collection of ODE and differential technique

This problem might be well-known in some countries, but how do other countries learn about such problems if nobody poses them.

For those who are interested in well-known problems in China.

Thank Elegia and djq_cpp for developing this technique. Thank Rewinding for reviewing this article.

Chain Reaction in UOJ Round 3 By vfleaking

Statement

​ You are given a set $$$A$$$, you need to compute $$$g_{i} = \frac{1}{2} \sum_{j,k}{i-1 \choose j}{i-1-j \choose k} g_jg_k$$$ where $$$i-1-j-k \in A$$$.

Solution

​ Let the EGF of $$$g$$$ be $$$x(t)$$$ and EGF of $$$A$$$ be $$$a(t)$$$. Thus $$$x'(t)=\frac{1}{2} a(t) x^2(t)+1$$$. We can solve this equation by D&C and FFT in $$$O(n\log^2 n)$$$. But there is a slower solution in $$$O(n\log n)$$$.

​ For a polynomial equation $$$f(x(t))=0$$$, we can use the Newton's method to solve it. If we find a polynomial $$$x_n$$$ that $$$x \equiv x_n \pmod {t^n}$$$. We can derive the following equation by the Taylor series:

​ Thus $$$x_{2n} = x_n - \frac{f(x_n)}{f'(x_n)} \pmod {t^{2n}}$$$.

​ For an ODE $$$\frac{d}{dt} x =f(x)$$$, we have

Let $$$r= e^{-\int f'(x_n) dt}$$$.

In this problem, $$$f(x)=\frac{1}{2} a(t) x^2(t)+1$$$. Since exp, multiplication and division takes $$$O(n \log n)$$$ time, the we have the time complexity $$$T(n)=T(n/2) + O(n\log n)$$$,which is $$$O(n\log n)$$$.

​ Note: I think we can generalize this method to solve high order ODE or system of ordinary differential equations. But the constant factor will be much more terrible.

Gnutella Chessmaster in MIPT contest Ptz camp 2018, Summer

Statement

​ I think the author of this problem is Endagorion.

​ This is a simplified version of this problem: We define the weight of a sequence $$$a_1, a_2, \dots, a_k$$$ as $$$\prod_{i=1}^k (a_i+i)$$$. You are given a sequence $$$c_1, c_2, \dots, c_n$$$. Compute the sum of the weight of all the subsequences of $$$c$$$ with length $$$k=1, 2, \dots, n$$$.

​ You can submit this problem here Little Q's sequence. However, you only need to compute the sum of all the subsequences here.

Solution

​ First, we consider the naive dp: $$$f_{i,j}=f_{i-1,j} + f_{i-1,j-1} \cdot (j+a_i)$$$. Let $$$g_{i,j} = f_{i,i-j}, b_i=a_i+i$$$, we have $$$g_{i,j}=g_{i-1,j-1} + g_{i-1,j} (b_i-j)$$$.

​ Let $$$g_i(x)$$$ be the OGF of $$$g_i$$$, we have $$$g_i(x)=x g_{i-1}(x)+b_i g_{i-1}(x) - x g'_{i-1}(x)=x(g_{i-1}(x)-g'_{i-1}(x))+b_i g_{i-1}(x)$$$.

​

​ Let $$$h_i=g_i(x) e^{-x}$$$, $$$h_i = x {h'_{i-1}}+b_i h_{i-1}$$$, where $$$h_{i,j}=j h_{i-1,j}+b_i h_{i-1,j}=(b_i+j) h_{i-1,j }$$$. Thus $$$h_{n,j}=h_{0,j} \prod_{i=1}^n (b_i+j)$$$. It's a multipoint evaluation of the polynomial $$$P(x)=\prod_{i=1}^n (x+b_i)$$$, which can be solved in $$$O(n\log ^2 n)$$$.

​ If we only need to compute the sum, there is also an alternative way to solve it. $$$g_i=(x - x \frac{d}{dx} +b_i) g_{i-1}(x)$$$. Let $$$P(x) = \prod_{i=1}^n (x+b_i)=\sum_{k=0}^n p_k x^k$$$. Then $$$g_n=\sum_{k=0}^n p_k (x-x\frac{d}{dx})^k(1)$$$. By induction, $$$(x-x\frac{d}{dx})^k (1)=\sum_{j=0}^k \lbrace ^k_j \rbrace (-1)^{k-j} x^j$$$. Let $$$q_k=\sum_{j=0}^{k} \lbrace ^k_j \rbrace (-1)^{k-j}$$$. According to OEIS, $$$\sum_{k\geq 0} q_k x^k=e^{1-x-e^{-x}}$$$. Thus we can compute $$$q_k$$$ in $$$O(n\log n)$$$.

​ Note: Due to the special property, the original version can also be solved in $$$O(n \log n)$$$ by a combinatorial method.

Exp in Gennady Korotkevich Contest 5 By tourist

Statement

​ You are given a polynomial $$$P(x)$$$, you need to find the first $$$m$$$ coefficients of $$$Q=P^n (x)$$$ in $$$O(m|P|)$$$.

Solution

​ There are many similar problems like Lucky Tickets, or computing Catalan numbers, Large Schröder numbers. Also, we will discuss the relation between ODE and P-recursive sequence further in the latter part.

​ We have

​ Thus $$$n Q P'= Q'P$$$. Consider the coefficient of $$$x^i$$$ in both parts, we have

.

​ We can compute $$$q_{i+1}$$$ from $$$q_{i-k+1}, q_{i-k+2}, \dots, q_{i}$$$ in $$$O(k)$$$.

​ BTW, a more intuitive way to derive this formula is we take $$$\ln$$$ of both sides and then take the derivative. $$$\ln G=n\ln F \Rightarrow G'/G=nF'/F$$$.

​ Note: This method also works for $$$n$$$ is not an integer. For example, you can also compute $$$\sqrt{P(x)}$$$ in the same manner. More example: compute $$$G=\sum_{i=0}^k \frac{F^i}{i!}$$$ . $$$G'=F'(G-\frac{F^k}{k!})$$$. We can compute $$$F^k$$$ using the above method and then solve this equation in a similar way.

Dirichlet $$$k$$$-th root in EC Final By jqdai0815

Statement

​ You are given a number theory function $$$g$$$ and $$$k$$$, you need to find a function $$$f$$$ such that $$$g=f^k$$$. The multiplication is Dirichlet convolution here.

Solution

​ The intended solution is $$$O(n\log^2 n)$$$. This improved solution credits to _rqy and Elegia.

​ Let $$$F(s)=\sum_{n\geq 1} \frac{f(n)}{n^s}$$$, which is the Dirichlet generating function. We also denote the Dirichlet generating function of $$$g_i$$$ by $$$G(s)$$$. $$$F'(s)=\sum_{n\geq 1} \frac{ f(n) \ln n}{n^s}$$$, thus $$$f'(n)=f(n) \ln n$$$.

​ Using the argument of the previous problem, we have $$$k G F'=F'Q$$$. Consider the coefficient of $$$n$$$-th term, we have $$$\sum_{d|n} f'(d) g(\frac{n}{d})=\frac{1}{k} \sum_{d|n} f(d) g'(\frac{n}{d})$$$. Since $$$g(1)=1, g'(1)=0$$$, we can compute $$$f'(n)$$$ and then $$$f(n)$$$ in $$$O(n\log n)$$$.

​ The remaining problem is how to deal with $$$\ln n$$$ in the modular arithmetic. Intuitively, we can replace $$$\ln n$$$ with $$$\Omega(n)$$$, which is the number of prime factors of $$$n$$$ counted with multiplicities. Since it's completely additive like $$$\ln n$$$. A rigorous proof can be like that we define a transformation $$$T$$$ of $$$f$$$ such that $$$(Tf)(n) = \Omega(n) f(n)$$$, and we can find $$$T (fg)=(Tf)g+f(Tg)$$$. So we can just replace the derivative of the DGF in the above argument to this transformation.

Rhyme By Elegia

Statement

​ Compute the sum of $$$\frac{n!}{\prod_{i=1}^k x_i!}$$$ where $$$\sum_{i=1}^k x_i=n$$$ and $$$d|x_i$$$ for all $$$i (1\leq i\leq k)$$$.

​ $$$n\leq 10^9, k\leq 2000, d=6$$$

Solution

​ The EGF of each term is $$$\sum_{j\geq 0} \frac{x^{jd}}{(jd)!}=\frac{1}{d}\sum_{j=0}^{d-1} e^{\omega^j x}$$$. Let $$$f(x)= \left(\frac{1}{d}\sum_{j=0}^{d-1} e^{\omega^j x}\right)^k$$$.

​ Since $$$w^2=w-1$$$, we have $$$f(x)=\sum c_{a,b} e^{(a+b\omega)x}$$$ where $$$-k\leq a,b\leq k$$$. And then we can sum over $$$c_{a,b} (a+b\omega)^n$$$ to get the answer. The question is that how to compute $$$c_{a,b}$$$ effectively. Since $$$1$$$ and $$$\omega$$$ are independent, we can regard $$$\frac{1}{d}\sum_{j=0}^{d-1} e^{\omega^j x}$$$ as a bivariate polynomial $$$F(u,v)$$$ where $$$u=e^x, v=e^{\omega x}$$$. We need to compute $$$G(u,v)=F(u,v)^k$$$. If we use FFT directly, the time complexity is $$$O(k^2 \log k)$$$, which might be not fast enough. However, we have $$$F \frac{\partial G}{\partial u}=k \frac{\partial F}{\partial u}G$$$. Thus we can compute $$$G$$$ in $$$O(k^2)$$$ in the same manner. We omit the details here.

Discussion about ODE and P-recursive sequence

​ It is known that every algebraic generating function is D-finite, and the coefficient is P-recursive.

​ First, there are some known results from Enumerative Combinatorics Volume 2. If $$$w$$$ be a formal power series over $$$K$$$, let $$$V_w$$$ denote the vector space over $$$K(x)$$$ spanned by $$$w, w', \dots$$$. Since it's D-finite, the dimension of $$$V_w$$$ is finite.

• If $$$u,v \in \mathcal{D}$$$, then $$$w=au+bv \in \mathcal{D}$$$, $$$\dim V_w \leq \dim V_u+\dim V_v$$$

• If $$$u,v \in \mathcal{D}$$$, then $$$w=uv \in \mathcal{D}$$$, $$$\dim V_w \leq \dim V_u\dim V_v$$$

• If $$$u,v \in \mathcal{D}$$$, then $$$w=u * v \in \mathcal{D}$$$, $$$\dim V_w \leq \dim V_u\dim V_v$$$, $$$u* v$$$ is the Hadamard product here.

• If $$$u \in \mathcal{D}$$$, $$$v$$$ is algebraic and $$$v(0)=0$$$, then $$$w=u(v(x)) \in \mathcal{D}$$$

Thus we can construct ODE for the generating function of P-recursive sequences. Here are some example:

• $$$g_1(x)=\sum_{i\geq 0} \frac{x^i}{i!} \Rightarrow g_1 = g'_1$$$

• $$$g_3(x)=\sum_{i\geq 0} x^i i! \Rightarrow g_3=g'_3x^2+g_3x+1$$$

• $$$g_4(x)=\sum_{i\geq 0} \frac{x^i}{i!(i+k)!} \Rightarrow g_4=g"_4x+(k+1)g'_4$$$

• $$$g_5(x)=\sum_{n\geq 0} \frac{1}{(k-1)n+1} {kn \choose n} x^{(k-1)n+1} \Rightarrow g_5=\frac{k x g'_5}{1+(k-1) g'_5}$$$

• $$$g_6(x) = (1+x)^a (1-x)^b \Rightarrow g'_6 = \frac{ag_6}{1+x} + \frac{bg_6}{1-x}$$$

• $$$g_8(x)=f^n \Rightarrow ng_8 f'= f g'_8$$$

Other examples are we can construct the ODE for the truncation of $$$P$$$-recursive sequences.

• $$$g_2(x) = \sum_{i=0}^k \frac{x^i}{i!} \Rightarrow g_2=g'_2+\frac{x^i}{i!}$$$

• $$$g_7(x)=\sum_{i=0}^k {n\choose i} a^i b^{n-i} \Rightarrow ng_7(a'+b')-g'_7(a+b)=n{n-1 \choose k} (a' a^k b^{n-k}-b'a^{k+1}b^{n-k-1})$$$

Universal Judge Aircraft in UOJ Round 19 By [user:ridiculos]

Statement

​ There are $$$n$$$ variables $$$x_1, x_2, \dots, x_n$$$ and two given parameters $$$a,b (a>b)$$$. Initially, all the variables are set to $$$0$$$.

​ Every time, you will choose a variable $$$x_i$$$ randomly and uniformly among the variables, which are less than $$$a$$$. You will terminate the process when all variables are not less than $$$b$$$. Compute the expected value of the number of variables that are equal to $$$a$$$.

​ $$$n, a, b \leq 250$$$

Solution

​ The intended solution is $$$O(na^2 \log n)$$$. This solution credits to djq_cpp.

​ We omit the routine generating function manipulations here. The hardest part of this problem is that let $$$P(x)=\sum_{i=0}^{b-1} \frac{x^i}{i!}$$$, you need to compute $$$P(x), P^2(x), \dots, P^{n-1}(x)$$$. If we use FFT directly, the time complexity is $$$O(na^2 \log n)$$$. Since the degree of $$$P$$$ is not small, the method in problem Exp doesn't help a lot here.

​ Let $$$R=\frac{x^{b-1}}{(b-1)!}, S=P^{k-1}, T=P^k, U=RS$$$. We notice that $$$P'=P-\frac{x^{b-1}}{(b-1)}=P-R$$$. Thus $$$T'=kP'S=k(P-R)S=kPS-RS=kT-U \Rightarrow (i+1)t_{i+1}=k t_i-u_i$$$. Since $$$U$$$ can be computed from $$$S$$$ in linear time, $$$P^k$$$ can be computed from $$$P^{k-1}$$$ in linear time. We remove the $$$O(\log n)$$$ factor here.

Generalization and Discussion

​ I'm thinking to generalize this technique to other problems. But I don't find amazing results. The following is the discussion with Rewinding.

​ For example, let $$$P(x)=\sum_{i=0}^n \frac{x^i}{i!i!}$$$, we can only get the similar recurrence of $$$P^{i} (P')^j$$$. If we need to compute $$$P^1,P^2, \dots, P^k$$$, we need to compute all terms $$$P^i (P')^j$$$ for $$$i+j\leq k$$$. So the time complexity is $$$O(k^2 nk )$$$. It may perform well when $$$k$$$ is extremely small, and $$$n$$$ is very large. However, there is another concern that I conjecture that the $$$in, in+1, \dots, i(n+1)$$$ term of $$$P^k$$$ maybe a P-recursive sequence. I do believe it's a P-recursive sequence. But I don't know how large the degree and the order it can be.

​ Another direction of generalization is to compute the first $$$n$$$-th term of $$$k$$$-th power of $$$P(x)=\sum_{i=0}^a \frac{x^i}{i!}$$$ more effectively. I don't think we can improve it to linear time. But it might be possible to improve it to $$$O(n \log a)$$$ or just $$$O(n\log n)$$$ but without $$$\exp, \ln$$$.

​

Chinese Elephant Chess By djq_cpp

Statement

​ Find the number of binary matrixes with $$$n$$$ rows and $$$m$$$ columns that there are at most $$$2$$$ ones in each row and column.

​ $$$n,m \leq 5\times 10^4$$$.

Solution

​ You can regard it as a bipartite graph with $$$n$$$ vertices and $$$m$$$ vertices in both parts. The degree of every vertex is no more than $$$2$$$. The graph consists of even cycles, even chains, and odd chains.

​ The EGF of even cycles, even chains and odd chains are

,

,

respectively.

​ And the answer is $$$n!m![x^ny^m] e^{F+G+H}$$$.

​ It's hard to deal with bivariate EGFs. We need to transform them into univariate EGFs. Since the degrees of $$$x$$$ and $$$y$$$ are the same in EGF of even cycles and even chains, we can transform them into univariate EGFs directly. For odd chains, we know the number of chains starting in the left part is less than the number in the right part by $$$m-n$$$. So we can enumerate the number of odd chains in the left part, and transform it into a univariate EGF.

​ The new EGF is

,

,

.

​ The answer is $$$n!m! [x^m] e^{F+G} \sum_{i=0}^n \frac{H^iH^{m-n+i}}{x^i i! (m-n+i)!}$$$. Let $$$P(x)=\sum_{i\geq 0} \frac{x^i}{i! (m-n+i)!}, Q=\frac{H^2}{x}$$$. The formula can be simplified to $$$n!m![x^m] e^{F+G} H^{m-n} P(Q)$$$.

​ We know the coefficient of $$$P$$$ is P-recursive. So we can construct an ODE for $$$P$$$ that $$$P=P"x+(m-n+1)P'$$$.

​ We also have that

. So

.

​ Then we can get the ODE of $$$P(H)$$$ :

, which is something like $P(H)\cdot A=(P(H))' \cdot B+(P(H))'' \cdot C$, where $$$A,B,C$$$ are three polynomials. So we can use D&C and FFT to solve this equation in $$$O(n\log^2 n)$$$.

​ Note that $$$H=\frac{1}{2}(x+\frac{x}{1-x})$$$, if we multiply $$$(1-x)^6$$$ in the both side of the ODE of $$$P(H)$$$, we can get a polynomial recurrence of $$$P(H)$$$ with small order and degree. So $$$P(H)$$$ can be computed in $$$O(n)$$$ here. It's not hard to see $$$H^{m-n}$$$ and $$$e^{F+G}$$$ are also P-recursive, so the convolution should also be P-recursive. Then we solved this problem in the linear time easily. But I think the order and degree will be too large if we try to find the recurrence of the answer directly. So a more effective way might solve these recurrences directly and compute the answer by FFT.

Generalization and Discussion

​ It looks polynomial modular composition can be computed in $$$\tilde{O}(n)$$$ in academia. But I don't know whether it's practical. The most popular algorithm is $$$O(n^2 + n^{1.5} \log n)$$$. You can also read the discussion and implementation of the Brent-Kung algorithm here. However, it is a bit slower than $$$O(n^2)$$$ one when $$$n=20000$$$.

​ It's not hard to see the above method can be applied to compute the polynomial composition $$$F(G(x))$$$ when $$$F$$$ is D-finite. We can construct the ODE of $$$F(G(x))$$$ and solve the equation using D&C and FFT in $$$O(n\log ^2 n)$$$. However, when the ODE of $$$F$$$ is too complicated, there is a severe issue of the constant factor.

​ Combined with Newton's method, we can compute the composition inverse of a D-finite series. A good application is to compute the number of simple permutations (a.k.a NEERC18 I) with length $$$1,2, \dots, n$$$ in $$$O(n\log^2 n)$$$.

Pearl in CTSC 2019 By laofudasuan

Statement

​ Compute $$$\frac{n!}{2^d} [x^n]\sum_{p=0}^{k} {m \choose p} (e^x-e^{-x})^p (e^x+e^{-x})^{m-p}$$$.

​ $$$n\leq 10^9, m\leq 10^5$$$

Solution

​ This solution credits to djq_cpp.

​ Let $$$Q(x)=\sum_{p=0}^k {m \choose p} (x-1)^p (x+1)^{m-p}$$$. So

. And we can simplify it to

.

​ The right is P-recursive, thus $$$Q$$$ can be computed in $$$O(m)$$$. So the answer is $$$\frac{n!}{2^d} [x^n] Q(e^{2x}) e^{-mx}$$$. The whole problem can be solved in $$$O(m(1+\log_m n))$$$.

​ Note: We need to compute $$$1^n, 2^n, \dots, m^n$$$, but it's multiplicative. Thus we can compute them in $$$O(m\log_m n)$$$.

I will update this blog when I upload new screencasts.

I plan to upload Chinese videos (screencasts, commentaries, and tutorials) on bilibili, and others on Youtube.

I will try to improve my English skill and make the video better.

Codeforces Round #621: Screencast, Commentary in Chinese.

Codeforces Round #619: Screencast

SPOILER ALERT : If you didn't solve the problems in NEERC and you want to enjoy the problems, please don't read.

Hi, guys.

rng_58, FizzyDavid and I try to solve ICPC world finals problem this year. I will post live commentaries here.

If every thing works fine, I will also stream here. However, we are in the different places. You can only see me solving problem.

Also good luck to all the contestants.

I accepted this problem during the training using a solution.

When I read the model solutions submitted by Mike, I found they are brute force too. And It will failed on a easy case n = 2¹⁸ - 1, a_i = i, b_i = i + 1.

Only my solution and Los_Angelos_Laycurse's solution pass this case.

I think we implemented more clever brute force solutions.

But I don't know how to prove my solution is right or construct some hard cases to make my solution TLE.

I really want to know: Is there any provable solution to solve this problem?

Hello everyone,

hihoCoder is going to hold a contest at the first day of this year. (2017/01/01 19:00 UTC+8)

hihoCoder is a Chinese website which holds some contests for beginners and also a monthly challenge.

The contest lasts 2 hours and contains 4 problems. The problem set is prepared by me and jiry_2. There will be english translation of the problems. The hardest problem is as hard as div1 C/D in my mind.

Enjoy problems!

When I was submitting the problem D in round #371, I clicked the "Choose File" button and selected my code.

Before the submission, I read my code another time, found a bug in my code and fixed it. And then I clicked the "submit" button.

But it turned out that my solution got wrong answer on pretest 4. I stress-tested my solution, and found it passed the big random data. I was really shocked. umm... Maybe my solution failed on some small testcases. So I tried many ways to generate testcases. But my solution was right on all the testcases I generated.

After struggling for about 40mins, I gave up and submitted it again. It passed all the pretests.

I compared two codes, and just found I submitted the old version (before fixing the bug) at first time.

After asking my roommate, he said when you clicked the "Choose File" button, it would upload the file instead of recording the path.

In the rest time of the contest, I tried to solve problem B and E but failed.

I think I should quit from algorithm contest like YuukaKazami and study harder.

Team member: lyy Ruchiose jqdai0815 zhj

jcvb failed on a relatively easy problem on day 2. But he still has one year to compete.

I'll upload my example solutions and will post links to them as soon as it becomes possible.

All the problems in Div 1 don't have the unique solution. I list several solutions to each problems. There are also some interesting bonus problems. I can't solve some of them yet :( If you have interesting ideas, feel free to share and discuss your ideas in the comments. :)

My English is poor, so if there are some mistakes or something you can't understand, you can also discuss it in the comments.

469A - I Wanna Be the Guy

I Wanna Be the Guy is an interesting game. I strongly recommend it to you.

The problem itself is easy. Just check if all the levels could be passed by Little X or Little Y.

7894174

469B - Chat Online

This problem is not hard. Just iterator over all possible t, and check if the schedule of Little X and Little Z will overlap.

7894252

Bonus:

1. p, q ≤ 50, l, r ≤ 10⁹
2. p, q, l, r ≤ 10⁵

468A - 24 Game

Solution 1:

If n ≤ 3, it's easy to find that it's impossible to make 24, because the maximal number they can form is 9.

If n > 5, we can simply add n - (n - 1) = 1, 24 * 1 = 24 at the end of the solution to the number n - 2.

So we can find the solution of 4, 5 by hand. 1 * 2 * 3 * 4 = 24, (5 - 3) * 4 * (2 + 1) = 24

7894267

Solution 2:

We can find the pattern like that n + (n + 3) - (n + 1) - (n + 2) = 0, and find the solution of 4, 5, 6, 7 by hand or brute forces.

Solution 3:

A knapsack-like solution.

7894283

468B - Two Sets

Solution 1:

If we have number x and a - x, they should be in the same set. If , it's obvious that . The contraposition of it is , that means if , a - x should in the set B. Same as the number x, b - x.

So we can use Disjoint Set Union to merge the number that should be in the same set.

If a - x doesn't exist, x can not be in the set A. If b - x doesn't exist, b can not be in the set B.

Then check if there are any conflicts among numbers which should be in the same set.

There are many other solutions to solve this problem based on the fact that x, a - x, b - x should be in the same set, like greedy, BFS and 2-SAT.

7894313

Solution 2:

If a = b, it's easy to find the solution.

We regards every number as a node. Every number x links to number a - x and number b - x.

The degree of every node is at most 2. So this graph consists of a lot of chains and cycles, and some node may have self loop.

We only need to check if the lengths of all the chains are even or the chain ends with a self loop.

7894323

Bonus:

Prove there is no cycle in the graph described in the solution 2.

Divided all the numbers from [0, n - 1] into two sets that have parameters a, b. Can you solved it in O(1)?

468C - Hack it!

Define . , so we should find a pair of number a, b that

Solution 1:

First we choose x randomly. Then we can use binary search to find the minimal d that .

So is very small, between 0 and . If , after choosing x atmost 9 * len + 2 times, we can definitely find a pair that

7894341

Solution 2:

We can use binary search to find the minimal d that g(d) ≥ a, g(d) ≥ 2a, ...

This solution is similar to the first one.

7894452

Solution 3:

We can use binary search to find the minimal d that g(d) ≥ a. And we use two pointers to maintain an interval [l, r] that until we find .

I can't prove the correctness of this algorithm, but it performs well in practice.

7894356

Solution 4:

Thanks ZhouYuChen for his talented idea.

If x < 10¹⁸, we can get f(10¹⁸ + x) = f(x) + 1. That means if we shift the interval [x + 1, x + 10¹⁸] by 1, the result will be increase by 1 too. And it also not hard to find that g(10^x) = 45 * x * 10^x - 1. So if , [a - x, a - x + 10¹⁸ - 1] is the answer.

It's easy to see that upper bound of the answer is a, because of pigeonhole principle (among g(0), g(1), ..., g(a) at least two are equal). So big integer is not required in this problem.

If solution 3 is correct, the upper bound of the answer can be 2 * 10¹⁶.

7878473

Bonus:

Prove or disprove that solution 3 is correct.

468D - Tree

I am sorry that this problem coincides with that one.

d(u, v) = dep_u + dep_v - 2 * dep_LCA(u, v), so the answer is:

dep_i there means the distance between node i and root.

We choose centroid of tree as root (let's denote it u), so we can make every pair (i, p_i) are in different subtrees, that means dep_LCA(i, pi) = 0.

So the answer is .

The next part of this problem is find the lexicographically smallest solution.

We regards it as finding the lexicographically smallest matching in a bipartite graph.

For a subtree, if the amount of nodes in this subtree in the left part > the amount of nodes not in this subtree in the right part, the perfect matching doesn't exist. So the amount of nodes in this subtree in the left part + the amount of nodes in this subtree in the right part should be no more than the amount of nodes unmatched, while the root is an exception.

We can use a segment tree to maintain it easily. We determined the minimum possible p_i from 1 to n. If there is a subtree that the amount of nodes in this subtree in the left and right part is equal to the amount of nodes unmatched, we must select a node from it, so p_i equal to the node in this subtree with the minimum id. Otherwise, we can choose a node with the minimum id that is not in the same subtree with i.

7894417

468E - Permanent

The permanent can be obtained as follows: for each (e₁, e₂, ..., e_t) such that x₁, x_e2..., x_et are distinct and y_e1, y_e2, ..., y_et are distinct, add to the answer.

It can be proved by the formula :

,

where s and t are subsets of the same size of {1, 2, ..., n} and , are their respective complements in that set.

Construct a undirected graph G with 2n vertices v₁, v₂, ..., v_2n, where the edge weight between vertex v_i, v_n + j is A_i, j - 1. We only need to know the sum of weight of all matchings that we choose t edges. The weight of matching is the product of all edge weights in the matching.

We only need to know the sum of the weights that we choose x edges in the each connected components.

The number of nodes in a connected component is s and the number of edges in this connected component is t.

Algorithm 1:

Because it's a bipartite graph, so the number of vertices in one part is at most s / 2. So we can use state compressed dp to calculate the ways to choose x edges in this connected component. The complexity is O(2^s / 2 * s²).

Algorithm 2:

We can choose a spanning tree. The number of edges in spanning tree of these vertices is s - 1, and the number of non-tree edges is t - s + 1. So we can enumerate all the non-tree edge, use tree dp to calculate the ways. The complexity is O(2^t - s * s²).

Combined with these two algorithm, the complexity is O(min(2^s / 2, 2^k - s) * s²)) = O(2^k / 3 * k²).

Всем привет! Приближается Codeforces Round #268! Мы приглашаем вас поучаствовать в этом раунде. Он начнется в 17:00 по московскому времени 20-го сентября.

Задачи раунда были подготовлены мной. Спасибо xyz111 и dhh1995 за идеи некоторых задач. Также благодарю vfleaking,foreseeable, MinakoKojima, Ruchiose и xllend3 за тестирование.

Традиционно говорю спасибо Gerald за помощь с раундом, Delinur за перевод условий и, конечно, MikeMirzayanov за Codeforces и Polygon.

Это мой первый Codeforces раунд. Надеюсь, он вам понравится.

В задачах раунда вы будете помогать герою, чье имя Little X. Удачи вам и удовольствия от решения задач! :)

UPD

Раунд закончился. Спасибо за участие.

Мои поздравления победителям.

Div. 1

1. PavelKunyavskiy
2. Kostroma
3. HellKitsune
4. SirShokoladina
5. DemiGuo

Div. 2

1. manman
2. topcodecheforces
3. mhy12345
4. GS_ZJ_137
5. z.last

Поздравляю ecnerwala, единственного решившего задачу D!

К сожалению, никто не решил задачу E в обоих дивизионах.

Разбор задач будет опубликован завтра.