amiya's blog

By amiya, 3 weeks ago, In English

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.

# Date Problem Contest Comment
-1 ??? 2009 Given a sequence $$$a_i$$$, you need to split them into $$$k$$$ parts and minimize the maximum absolute difference of each part. One of the problems I set in a training contest when I was in 7th grade, which is the first contest I made as far as I can remember. It's a textbook binary search problem. I can't tell if it's made by myself or just copied from elsewhere, but it doesn't really matter.
-0.75 August 2013 Given a sequence, answer the query "how many numbers appear at least $$$k$$$ times in a range". Mock Contest for NOIp in school I don't remember whether problems are made by me or copied from elsewhere. If it's not made by me, I will say sorry to the author. I don't know why I wrote such a textbook Mo algorithm problem in the contest, and for the first problem.
-0.5 August 2013 Given a complete bipartite graph with $$$k(k \leq 20)$$$ edges removed. Every edge has a weight. Find the number of perfect matchings, and the sum of the weights of perfect matchings. Weights of perfect matchings are the sum of the weight of edges here. Mock Contest for NOIp in school An easy PIE problem. It should be an easy version for a Codeforces problem (problem 18 in the list) later.
-0.25 August 2013 Given a $$$n \times m (n, m\leq 700, 2|nm)$$$ binary matrix. You can choose a cell $$$(i, j)$$$, and flip all the cells in the same row or column. Find the minimum number of operations and the lexicographically smallest solution. Mock Contest for NOIp in school Not a bad problem in my opinion.
0* May 2014 Triangle inscribed in ellipse Project Euler It's very recommended to click the link, and see wtf the problem is. It's a modern abstract art masterpiece of shit problems. However, to be honest, the intended solution is interesting.
1 August 2014 2048 Yuhao Du Contest 1(aka 2014 Multi-University Training Contest 8) Yuhao Du Contest 12346 do exist. It's the first ICPC contest I wrote. I remember I set the TL too tight for some problems and the statements for some problems are not very good. And it may be a common problem for many new problem-setters without the guidance of veterans. However, I am satisfied with the quality of the problems even from today's perspective. It doesn't contain many fancy problems, but it's very balanced and has moderate difficulty.
2 August 2014 Area of Mushroom Yuhao Du Contest 1
3 August 2014 GCD Array Yuhao Du Contest 1 A good combination of number theory tricks and data structure tricks. I didn't see this kind of problem before.
4 August 2014 Kingdom Yuhao Du Contest 1
5* August 2014 Light Yuhao Du Contest 1 My favorite problems in the set. It is not very difficult.
6 August 2014 Monster Yuhao Du Contest 1
7 August 2014 Multiplication table Yuhao Du Contest 1 A fun easy problem.
8 August 2014 Number Transformation Yuhao Du Contest 1 A fun easy problem.
9 August 2014 Periodic Binary String Yuhao Du Contest 1 The hardest problem in the set. But I feel it's not too interesting.
10 August 2014 Permanent Yuhao Du Contest 1
11 August 2014 Tree Yuhao Du Contest 1
11.5 August 2014 Find the number of pairs $$$(a, b)$$$ such that $$$a \bmod b = b \textrm{ div } a$$$, for $$$1\leq a, b\leq n(n\leq 10^{12})$$$ Mock Contest for NOIp in school A fun easy problem.
12 September 2014 I Wanna Be the Guy Codeforces Round #268 My first and only single author Codeforces Round. Some ideas may come from preparing for the ICPC contest. I don't want to make the contest so hard deliberately, but the competitors frustrated me, sad.
13 September 2014 Chat Online Codeforces Round #268
14 September 2014 24 Game Codeforces Round #268
15 September 2014 Two Sets Codeforces Round #268 A fun easy problem. And I deliberately make the pretest very weak. I missed the old days when the hacking strategy is also a part of the contest.
16* September 2014 Hack it! Codeforces Round #268 It has an unexpected beautiful solution that came up by the contestant during the contest. I think it is worth reading this beautiful solution.
17 September 2014 Tree Codeforces Round #268 Is it that hard? :clown_face::clown_face::clown_face:
18* September 2014 Permanent Codeforces Round #268 I also developed a technique that you can use a heuristic algorithm to find a good order to do state-compressed dp. It's not included in the tutorial of the contest but somehow spread secretly:thinking:.
$$$\frac{55}{3}$$$* February 2015 Given a permutation with $$$n (n\leq 10^5)$$$ elements, find $$$\sum P_i P_j P_k$$$ for triples $$$(i, j, k)$$$ where $$$(i, j) = (j, k) = (k, i) = 1$$$ Mock Contest for Winter Camp I developed a new trick to count coprime triples and wrote this problem.
$$$\frac{56}{3}$$$ March 2015 Find the $$$k$$$-th lexicographically largest [autocorrelations]( with length $$$n$$$ $$$(n\leq 200, 1\leq k\leq 10^{18})$$$. Mock Contest for ZJOI I learned a powerful way to write shit problems — reading papers.
19 April 2015 Product Thesis of Chinese national training team The problem itself is shit. I feel I didn't have good ideas in time so submitted this problem. But I developed a trick that does PIE on the symmetry group, which I think is fun.
19.5 June 2015 Let $$$S$$$ be a string consisting of ab?, $$$f(S)$$$ be the number of different autocorrelations I can get if I replace every ? with a or b. Find the shortest, then lexicographically smallest string $$$S$$$, such that $$$f(S) = i$$$ for $$$i = 1, 2, \dots, 2000$$$. Mock Contest for NOI Uh, what the hell is this?
20 August 2015 Expression Yuhao Du Contest 2 (aka 2015 Multi-University Training Contest 9, Ptz Summer 2015 Day 2) It is the second Yuhao Du contest, and is also used in the Petrozavodsk training camp. In that year, I remember I reached the top 10 on Codeforces with the id TooSimple, failed on IOI, and graduated from high school. The problems are harder than the previous one. I don't know how to describe my feeling about this problem set. I became a more experienced problem setter, and the problems are also good. But I feel more problems came from the way "let me develop this trick to a problem" or "let me make a data structure problem".
21 August 2015 Hack it! Yuhao Du Conest 2
22 August 2015 GCD Tree Yuhao Du Conest 2 A fun problem.
23 August 2015 Too Simple Yuhao Du Contest 2
24 August 2015 Arithmetic Sequence Yuhao Du Contest 2
25 August 2015 Persistent Link/cut Tree Yuhao Du Contest 2
26 August 2015 Travelling Salesman Problem Yuhao Du Contest 2
27 August 2015 Goldbach's Conjecture Yuhao Du Contest 2 A weird problem from the paper.
28* August 2015 Random Inversion Machine Yuhao Du Contest 2 The hardest problem in the set. Inspired by misreading this problem, it's way harder. A little bit technical, but not bad.
29 August 2015 Sometimes Naive Yuhao Du Contest 2
30** Sepetember 2015 You are given an empty graph with $$$n (n\leq 100)$$$ vertices, you are randomly choosing two numbers $$$u,v$$$, add an edge between $$$u$$$ and $$$v$$$. Compute the expected step to get a connected graph. Local Contest One of my best problems. I didn't remember where I used this problem and didn't remember the exact time. It may be not very hard from today's perspective.
31 November 2015 Cycle
Given $$$n (1\leq n\leq 2000)$$$ numbers form a cycle, divide them into $$$k$$$ parts, and maximize gcd of the sum of each part. Output the answer for $$$k = 1...n$$$
HihoCoder #16 HihoCoder used to be a Chinese competitive programming platform, but died. It's an okayish easy problem.
32 November 2015 Field
Given a tree with $$$n (1\leq n\leq 10^5)$$$ vertices, find the optimal heavy light decomposition when $$$u$$$ is the root for $$$u = 1, \dots, n$$$
HihoCoder #16 An fun easy problem.
33 November 2015 Group
Compute the number of subgroup with size $$$k$$$ of $$$S_n$$$. $$$k\leq 5, n\leq 10^5$$$.
HihoCoder #16 It was later improved in this problem. Compute the number of subgroups of $$$S_n$$$ isomorphic to some specific group $$$G( |G| \leq 30)$$$.
34* January 2016 Bamboo
First, we define a string $$$p$$$ can be made by $$$s$$$ and $$$t$$$ iff $$$s$$$ is the prefix of $$$p$$$, $$$t$$$ is the suffix of $$$p$$$, and $$$|s|+|t| \geq |p|$$$. A string $$$p$$$ can be made by $$$s_1, s_2, \dots, s_k$$$ iff there are strings $$$p_1,p_2,\leq, p_k$$$, such that $$$p_1=s_1$$$, $$$p_i$$$ can be made by $$$p_{i-1}$$$ and $$$s_i$$$, and $$$p_k=p$$$.
You are given a string $$$S(|S| \leq 10^6)$$$. Compute how many distinct lengths $$$x$$$ not exceeding $$$l (1\leq l\leq 10^{18})$$$ such that there are string $$$t$$$ with length $$$x$$$ that can be made by several copies of string $$$S$$$.
CNOI Winter Camp 2016 (Developed by Jianhao Wang) The first problem I wrote for the official CNOI contest. I'm one coauthor. A combination of several tricks. Maybe the most interesting step is how to optimize $$$O(n \log^2 n)$$$ into $$$O(n\log n)$$$.
35** February 2016 Map
It’s a communication task. Alice has a map with $$$n$$$ items (key, value), key is in $$$[0,2^{32})$$$, value is in $$$[0,2^{10})$$$. She needs to compress it into a binary string with length no more than $$$12500$$$ bits and send it to Bob.
Bob should answer queries, he should answer the corresponding value for the key. However, for a key not in the map, he can answer anything.
UOJ Goodbye Yiwei Contest (Developed by Kaifeng Lyu) An interesting problem, recommended.
36* March 2016 Random Tree Generator
This problem is a Petr-ish problem. You are given four random algorithms to generate trees, and try to distinguish them.
ZJOI 2016 ZJOI is Zhejiang provincial team selection contest. It's my first time leading write an official OI contest, and most problems are made by me. I follow the strategy that one data structure problem, one counting problem, and one problem in another genre.
37 March 2016 Tourist
You are asked to find the shortest path in the grid graph.
ZJOI 2016 A little bit surprised that no one wrote it before.
38** March 2016 Little Star
You are given a tree $$$T$$$ and a graph $$$G$$$ with $$$n(n\leq 18)$$$ vertices, compute the number of embedding of the tree into the graph. (a permutation $$$p$$$ such that $$$(u,v) \in T$$$ $$$\Rightarrow$$$ $$$(p(u), p(v)) \in G$$$)
ZJOI 2016 It may become a classical problem now. I learned that trick from computing the number of Hamilton paths but didn't see it used anywhere else before. You may be amazed when you see this trick for the first time.
39* April 2016 Big Forest ZJOI 2016 I seldom wrote data structure problems. This one is interesting.
40* April 2016 Circuit
You are given a graph and compute how many pairs of vertices can be two terminals of a series-parallel graph.
ZJOI 2016 An orthodox and hard graph problem. I'm a fan of this kind of problem. So I like it.
41*** May 2016 Suffix Array
Compute how many distinct suffix arrays can be constructed by a string with length $$$n $$$ and an alphabet with size $$$m (n, m\leq 500)$$$, the occurrence of $$$i$$$-th character should be no more than $$$c_i$$$.
CTSC 2016 One of my best problem. This problem is very interesting in a very natural setting. I'm very proud of this problem.
42 August 2016 Olympic Data Structure UOJ Round #15 (Developed by ???) It is said this problem is authored by me, but I have no idea why:clown_face: Maybe I just provided the idea that the Ukkonen algorithm can work on the multiple order-preserved patterns matching. But I have no idea about the details, and how it really works.
43 September 2016 Emulator
Given a graph, find a graph with the minimum number of edges that preserve the distances of all pairs of vertices.
HihoCoder #23 It also appeared in later ABC as far as I remember.
44 September 2016 Certificate
Given a boolean formula of $$$n (n\leq 14)$$$ variables, compute the certificate with the smallest size for each input.
HihoCoder #23 It seems I was a little interested in theoretical computer science then.
45 September 2016 Tree
Given a tree, answer the queries if we remove $$$k (\sum k \leq 10^5)$$$ edges from it, what is the diameter of each part.
HihoCoder #23
46 September 2016 Automorphism
Compute the number of unlabelled trees with size $$$n(n\leq 50)$$$ and automorphism no more than $$$k(\leq 10^9)$$$.
HihoCoder #23
47 Janurary 2017 Rikka with Number
I have a pair of number $$$(0, 1)$$$. In each step, you can add one number to another. You want to reach $$$n(n\leq 10^9)$$$ in $$$60$$$ steps.
HihoCoder #26 A fun easy problem.
48 January 2017 Rikka with Tree IV
Given a tree with $$$n(n\leq 10^5)$$$ vertices, color each vertex such that every connected subgraph with size no more than $$$k$$$ has distinct colors. What is the minimum number of colors?
HihoCoder #26
49* January 2017 Rikka with Cactus
Given a graph, for each edge, check if the graph is a cactus after removing it.
HihoCoder #26 An orthodox graph problem with heavy casework. I'm a fan of this kind of problem. So I like it.
50 January 2017 Rikka with Flow
Given a cost flow network, you can reduce the cost of some edges and want to make the cost of maximum cost circular flow less than $$$c$$$. What is the minimum total amount of cost you reduce?
HihoCoder #26 A funny problem.
51 January 2017 Isomorphism Checker
You need to construct graphs to hack some graph isomorphism checker.
UOJ Goodbye Bingshen (Developed by Kaifeng Lyu) Thank the developer for making this problem. I think I just gave the rough ideas of this problem. The intended solution is to construct the graph for each case. But it is overkilled by a specific class of graphs :clown_face:
52 February 2017 Chessboard
You are given an undirected graph with $$$n$$$ vertices and $$$m(n, m\leq 100)$$$ edges, there are $$$n-1$$$ chess with distinct labels on $$$n-1$$$ distinct vertices, and there are one empty vertex. In each step, you can move one chess to the adjacent empty vertex.
There are $$$T(T\leq 1000)$$$ queries, Given the starting and ending configuration, you should determine whether it is possible to reach the ending configuration from the starting one.
CNOI Winter Camp 2017 I found this problem can be reduced to a computational group theory problem, and felt it may be interesting to see the application of computational group theory algorithms in the combinatorial problem. I just found this problem was well-researched and only has one or two counterexamples. And it was about two days before the contest. Then I became a clown:clown_face:
52 February 2017 Chessboard
You are given an undirected graph with $$$n$$$ vertices and $$$m(n, m\leq 100)$$$ edges, there are $$$n-1$$$ chess with distinct labels on $$$n-1$$$ distinct vertices, and there are one empty vertex. In each step, you can move one chess to the adjacent empty vertex.
There are $$$T(T\leq 1000)$$$ queries, Given the starting and ending configuration, you should determine whether it is possible to reach the ending configuration from the starting one.
CNOI Winter Camp 2017 I found this problem can be reduced to a computational group theory problem, and felt it may be interesting to see the application of computational group theory algorithms in the combinatorial problem. I just found this problem was well-researched and only has one or two counterexamples. And it was about two days before the contest. Then I became a clown:clown_face:
53** February 2017 Random Numbers Deep Dark Fantasy Contest (Ptz Winter 2017 Day 5) The problems in the contest are all developed by ICPCCamp Team. Thank you for developing them. This is the only contest written by my ICPC team. ICPC is a somehow painful journey for me. And I feel a bit sorrowful when looking back to these days. I think we promised to write a contest, but we didn't have enough ideas, or it was just made in a hurry. So the contest only has 9 problems, which is unusual. I think I authored at least 5 of them. Since for some problem, I can't really tell if it was written by me, or my teammates.
To the problem itself, this one is interesting. And as far as I remember, Warsaw U Eagles(?) came up with an unexpected beautiful solution.
54 February 2017 Eulerian Orientation Deep Dark Fantasy Contest Not a bad problem, but also not very impressive.
55* February 2017 Tube Master II Deep Dark Fantasy Contest Many teams didn't pass the IQ test.
56** February 2017 Palindrome Deep Dark Fantasy Contest I noticed the palindrome prefix structure can be merged in polylog time when solving a distributed task in PA (When can we have another distributed competitive programming contest? sad). And then I wrote this problem. I think I was ahead of the academics since I wrote a mail to some authors in CPM, and they said they didn't know that. Or they didn't notice we can use this trick and segment tree to maintain the palindrome structure of a string dynamically.
57 February 2017 Territory Game Deep Dark Fantasy Contest It's a game theory problem in a quite natural setting. But the solution may have some casework. I remembered my initial idea is wrong, and it was fixed by the developer team.
58 March 2017 Polynomial ZJOI 2017 (Developed by Ruyi Ji) ZJOI 2017 was not led by me, so I provided this idea. It's inspired by a problem in Project Euler. Hard, but technical and annoying.
59 April 2017 Automorphism
What is the maximum number of edges can a simple undirected graph with $$$n (n\leq 10^{100})$$$ vertices can have such that the graph doesn't have a non-trivial automorphism?
BJOI 2017 It's used in Beijing team selection contest. I wrote two of them. The setting is quite natural, not a bad problem but not very impressive.
60 April 2017 Driving
Given a fixed sequence $$$b$$$, you need to maintain a sequence $$$a (|a| \leq 50000)$$$ to support modify $$$a_i$$$, and answer $$$\min_{p} \sum|a_i - b_{p_i}|$$$ where $$$p$$$ is a permtation here.
BJOI 2017 It's passed by brute force. Sorry, I should stop creating data structure problems.
61 May 2017 Square
How many subsets of $$$[L, R] (1\leq L \leq R \leq 10^7)$$$ that the product of numbers is a square number?
THUSC 2017 (Developed by Jiayi Weng) A pretty standard and boring problem. THUSC happened when I was in the World Final, very sad.
62* October 2017 Stones
There are two sets $$$A$$$ and $$$B$$$ and $$$n$$$ piles of stones. Alice and Bob take turns alternatively. Alice can choose a pile with size $$$s$$$ and split it into $$$a, s-a$$$ where $$$a\in A, 1\leq a < s$$$. Bob can split it into $$$b, s-b$$$. Who can't move loses.
Someone's Mock Contest for NOIp A fun easy problem. A good start problem for the partisan game and surreal numbers. However, you don't have any knowledge of surreal numbers here. In another word, surreal numbers in the partisan game are actually more intuitive than nimmer, it simply defines how many steps Alice can perform more than Bob. But most tutorials to surreal numbers suck.
63*** October 2017 Lollipop
You are given an $$$n\times m (n\leq 5, m\leq 10000)$$$ grid graph, there is a cost $$$c_i$$$ for each edge, there is a range $$$[l_i,r_i]$$$ for each vertex, you need to write the number $$$f_i$$$ in each vertex such that $$$l_i\leq c_i\leq r_i$$$. The value of an edge is the absolute difference between the number in two vertices times the cost itself. The value of a graph is the sum of all the edges. You need to minimize the value of the graph.
Someone's Mock Contest for NOIp One of my best problems. This problem may look a bit standard now. From a perspective back then, most ideas were novel. I'm really proud that I can come up with these ideas to write the problem.
An easier version in CGR 11 two years ago. And stop sending your best problem to others in a random private contest.
64 January 2018 Cube
There is a rectangular box. An insect inside the box wants to fly from some place to another place. This insect can only fly inside the box including the surface, and speed strictly inside the box and speed on the surface are two different constants. Find the minimum time.
Yuhao Du Contest 3 It's a contest used in a local training camp. And it may be prepared in 24 hours. So most problems are shit. Let me share some not-so-bad problems.
It's a cute geometry problem.
65 January 2018 Permutation
Given a permutation of $$$1,2,\dots, n$$$. You can split it into at most $$$k$$$ continuous parts and rearrange these parts. Find the array you can get with minimum lexicographic order.
Yuhao Du Contest 3 It seems to be a Div 2 B problem. But it may be a bit tricky since my first two versions of the model solution are both wrong.
66* January 2018 Tree
Given a tree with $$$n$$$ nodes. Alice and Bob take turns playing, starting with Alice. At first, Alice can choose any one node in the tree and color it. Then the player chooses an uncolored node adjacent to a node colored by Alice, and colors it. Who can't move loses.
Yuhao Du Contest 3 A fun easy problem. I'm usually bad at writing ad-hoc problems.
67 January 2018 Patterm Matching(I will fix the format later)
Given a string $$$s(|s| \leq 10^6)$$$ and code
counter = 0
for i in range(0, len(s)):
for j in range(0, len(t)):
if s[i+j] != t[j]:
counter += 1
Count the number of string with length not exceeding $$$l$$$, which would make counter is no less than $$$k (k\leq 10^{12})$$$.
Yuhao Du Contest 3 A problem with a natural setting, nothing special though.

Full text and comments »

  • Vote: I like it
  • +301
  • Vote: I do not like it

By amiya, history, 8 months ago, In English

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).

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.

Full text and comments »

  • Vote: I like it
  • +243
  • Vote: I do not like it

By amiya, history, 3 years ago, In English

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 fantasy for reviewing this article.

Chain Reaction in UOJ Round 3 By vfleaking


​ 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$$$.


​ 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:

$$$0=f(x_{2n}) = f(x_n) + f'(x_n) (x_{2n} -x_n) + \dots$$$

​ 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

$$$\begin{eqnarray*} \frac{d}{dt} x_{2n} &\equiv & f(x_n) + f'(x_n) (x_{2n}-x_n) \pmod {t^{2n}} \\ & \equiv & f(x_n) + f'(x_n) x_{2n} - f'(x_n) x_n \pmod {t^{2n}} \end{eqnarray*}$$$

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

$$$\begin{eqnarray*} \left(\frac{d}{dt} x_{2n}\right)r &\equiv & (f(x_n)-f'(x_n) x_n) r + f'(x_n) x_{2n} r \pmod {t^{2n}} \\ \frac{d}{dt} (x_{2n}r)& \equiv & (f(x_n) - f'(x_n)x_n) r \pmod {t^{2n}} \end{eqnarray*}$$$

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


​ 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.


​ 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)$$$.

$$$g_i(x) e^{-x} = x (g_{i-1}(x) e^{-x} - g'_{i-1}(x) e^{-x}) + b_i g_{i-1}(x) e^{-x} = x (g_{i-1}(x)e^{-x})' + b_i g_{i-1}(x) e^{-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


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


​ 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

$$$(P^{n+1})'=(n+1) P^n P' = (P^n P)'=(P^n)'P + P^n P'$$$

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

$$$n(q_i p_1 + 2 q_{i-1} p_2 +\dots + k q_{i-k+1} p_k) = (i+1) q_{i+1} p_0 + iq_ip_1 + \dots + (i-k+1) q_{i-k+1} p_k$$$


​ 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 amiya


​ 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.


​ 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


​ 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$$$


​ 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]


​ 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$$$


​ 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 fantasy.

​ 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


​ 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$$$.


​ 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

$$$F=\sum_{i\geq 2} \frac{1}{2i} x^iy^i$$$


$$$G=\sum_{i\geq 1} x^iy^i$$$


$$$H=\frac{1}{2}\left(\sum_{i>0} x^{i+1} y^i + \sum_{i>0} x^i y^{i+1}\right)+x+y$$$


​ 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

$$$F=\sum_{i\geq 2} \frac{1}{2i} x^i$$$


$$$G=\sum_{i\geq 1} x^i$$$


$$$H=x+\frac{1}{2} \sum_{i\geq 2}x^i$$$


​ 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

$$$(P(H))'=P'(H)H', (P(H))"=P"(H)(H')^2 + P'(H)H"$$$

. So

$$$P'(H)=\frac{P(H)'}{H'}, P"(H)=\frac{P(H)"H'-P(H)'H"}{H'^3}$$$


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

$$$P(H)H'^3=P(H)'((m-n+1) H'^2 - H"H) + P(H)"H'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


​ 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$$$


​ This solution credits to djq_cpp.

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

$$$2mQ-(2x)Q'=m{m-1 \choose k}((x-1)^k(x+1)^{m-k}-(x-1)^{k+1}(x+1)^{m+k-1})$$$

. And we can simplify it to

$$$mQ-xQ'=m{m-1 \choose k} (x-1)^k(x+1)^{m-k-1}$$$


​ 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)$$$.

Full text and comments »

  • Vote: I like it
  • +1044
  • Vote: I do not like it

By amiya, 3 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • +250
  • Vote: I do not like it

By amiya, history, 4 years ago, In English

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


Full text and comments »

  • Vote: I like it
  • +386
  • Vote: I do not like it

By amiya, 5 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +263
  • Vote: I do not like it

By amiya, history, 6 years ago, In English

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 = 218 - 1, ai = i, bi = 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?

Full text and comments »

  • Vote: I like it
  • +149
  • Vote: I do not like it

By amiya, history, 6 years ago, In English

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!

Full text and comments »

  • Vote: I like it
  • +55
  • Vote: I do not like it

By amiya, history, 7 years ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +328
  • Vote: I do not like it

By amiya, 8 years ago, In English

Team member: lyy Ruchiose amiya zhj

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

Full text and comments »

  • Vote: I like it
  • +110
  • Vote: I do not like it

By amiya, 8 years ago, In English

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.


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.



  1. p, q ≤ 50, l, r ≤ 109
  2. p, q, l, r ≤ 105

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


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.


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.


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.



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


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.


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.


Solution 4:

Thanks ZhouYuChen for his talented idea.

If x < 1018, we can get f(1018 + x) = f(x) + 1. That means if we shift the interval [x + 1, x + 1018] by 1, the result will be increase by 1 too. And it also not hard to find that g(10x) = 45 * x * 10x - 1. So if , [a - x, a - x + 1018 - 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 * 1016.



Prove or disprove that solution 3 is correct.

468D - Tree

I am sorry that this problem coincides with that one.

d(u, v) = depu + depv - 2 * depLCA(u, v), so the answer is:

depi 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, pi) are in different subtrees, that means depLCA(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 pi 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 pi 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.


468E - Permanent

The permanent can be obtained as follows: for each (e1, e2, ..., et) such that x1, xe2..., xet are distinct and ye1, ye2, ..., yet 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 v1, v2, ..., v2n, where the edge weight between vertex vi, vn + j is Ai, 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(2s / 2 * s2).

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(2t - s * s2).

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

Full text and comments »

  • Vote: I like it
  • +124
  • Vote: I do not like it

By amiya, 9 years ago, In English

Hello everyone! Codeforces Round #268 is coming soon! We invite you to participate in this round. It will be held on September 20th at 17:00 MSK.

Problems have been prepared by me. Thanks xyz111 and dhh1995 for giving me the idea of some problems. Thanks vfleaking, foreseeable, MinakoKojima, Ruchiose and xllend3 for testing.

I also want to thank Gerald for helping to prepare this round, Delinur for translating the statements, and also MikeMirzayanov for Codeforces and Polygon.

It is my first round on Codeforces. Hope you will enjoy this round.

You'll help a boy named Little X in this round. Good luck and have fun :)


Round has finished. Thanks for participating.

Congratulations to the winners.

Div. 1

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

Div. 2

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

Congratulations to ecnerwala, the only participant to solve the problem D!

Unfortunately, no one has solved the problem E in both divisions.

Editorial for the round will be added tomorrow.


Editorial is here.

Full text and comments »

  • Vote: I like it
  • +256
  • Vote: I do not like it