Hello Codeforces!
Today I'll be writing about what I have learnt about combinatorics, which played, and, in my opinion, will still be playing an important role in both Codeforces and CP (short for competitive programming).
However, combinatorics is such a great subject that made that impossible for me to write it all in one blog. So, this is just the second blog, which is friendly to beginners. If you are interested, please, pay attention to this account and I'll give posts as series for a long term.
If you have found some mistakes in the text, or if you have some questions about the topic, please, leave a comment, and I'll check it weekly and reply. Also, if you find some grammar mistakes, a kind comment will be also welcomed.
Previous Blogs
Content
- Homework Tutorial
- Catalan Sequence
- Stirling Number
- Derangement
- Recurrence relation
- homework
Part 0 — Pre-knowledge
In order not to make this blog too long (it's already very long now xD), I won't explain these things anymore. You can find them on wikis or google them.
- What Combinatorics (1)(2) mentioned.
- CP basics.
- Reading simple C++ code.
Part 1 — Homework Tutorial
Task A
The first task of it can be solved with two quick powers in $$$\mathcal O(\log{(n+k)})$$$ time.
The second task can be solved with combination initiation, $$$inv[i]$$$ initiation mentioned in Task C in $$$\mathcal O(n)$$$ time.
Task B
Let's define $$$z$$$ the number of the $$$0$$$s in the array, $$$p$$$ the number of the positive elements in the array, $$$m$$$ the number of the negative elements in the array.
When the product is $$$0$$$, we have to choose at least one $$$0$$$. You may find it difficult to solve it directly, let's reduce the invalid subsets' count, which contains no $$$0$$$. So the count is $$$2^{n-z}$$$. The whole count is $$$2^n$$$, the answer is $$$2^n-2^{n-z}$$$ which can be solved in $$$\mathcal O(\log n)$$$ time.
When the product is positive, we have to choose $$$2i$$$ negative numbers. So we can enumerate the count of the negative numbers and calculate the answer. Notice that $$$2i\in[0,n]$$$. First, we can choose any subset of the set of positive numbers. So the answer is:
When the product is negative, we have to choose $$$2i+1$$$ negative numbers. So we can enumerate the count of the negative numbers and calculate the answer. Notice that $$$2i+1\in[0,n]$$$. First, we can choose any subset of the set of positive numbers. So the answer is:
All above can be solved in $$$\mathcal O(n)$$$ time.
