I was recently puzzled by this problem:

• Given $$$n$$$ intervals $$$[l_i,r_i]$$$. Find the lexicographically minimum permutation $$$p_1,p_2,\dots,p_n$$$ of $$$1-n$$$ such that $$$p_i\in [l_i,r_i]$$$ for each $$$1\leq i\leq n$$$.

This problem comes from misreading the problem A Place For My Head from Petrozavodsk Summer 2017. Day 5. Moscow IPT Contest. The original problem requires that $$$q_i\in [l_i,r_i]$$$ where $$$q=p^{-1}$$$ is the inverse permutation of $$$p$$$ and has constraint $$$1\leq n\leq 2\times 10^5$$$.

I wonder if there exists a decent (subquadratic) solution for this (misread version) of the problem? Many thanks in advance!

It seems that there's no blog about this contest yet. Let's discuss problems here. How to solve B,E and G?

How do you judge if a problem is good or not? If you need to rate problems, which aspects will you consider? Please feel free to share your ideas.

UPD: I posted this mainly because I want to build a standard to rate problems when problemsetting.

Let's discuss problems. How to solve 2,5,8 and 11?

and what is the requirement to have one?

I found this problem on the problem set of a contest in some training camp, but couldn't find more information beyond that. The problem statement is as follows:

Consider n different urns and $$$n$$$ different balls. Initially, there is one ball in each urn.

There is a special device designed to move the balls. Using this device is simple. First, you choose some range of consecutive urns. The device then lifts all the balls from these urns. After that, you specify the destination which is another range of urns having the same length. The device then moves the lifted balls and places them in the destination urns. Each urn can contain any number of balls.

Given a sequence of movements for this device, find where will each of the balls be placed after all these movements.

The first line contains two integers $$$n$$$ and $$$m$$$, the number of urns and the number of movements $$$(1 \leq n \leq 100 000,1 \leq m \leq 50 000)$$$.

Each of the next $$$m$$$ lines contain three integers count $$$i , from_i$$$ and $$$to_i$$$ which mean that the device simultaneously moves all balls from urn $$$from_i$$$ to urn $$$to_i$$$ , all balls from $$$from_{i + 1}$$$ to urn $$$to_{i + 1}$$$, . . ., all balls from urn $$$from_i + count_i − 1$$$ to urn $$$to_i + count_i − 1 (1 \leq count_i , from_i , to_i \leq n, \max(from_i , to_i ) + count_i \leq n + 1)$$$.

Could anyone please give a hint? Thanks in advance!

Hello, Codeforces! The reason why I am writing this blog is that my ACM/ICPC teammate calabash_boy is learning this technique recently(he is a master in string algorithms,btw), and he wanted me to provide some useful resources on this topic. I found that although many claim that they do know this topic well, problems concerning inclusion-exclusion principle are sometimes quite tricky and not that easy to deal with. Also, after some few investigations, the so-called "Inclusion-Exclusion principle" some people claim that they know wasn't the generalized one, and has little use when solving problems. So, what I am going to pose here, is somewhat the "Generalized Inclusion-Exclusion Principle". Most of the describing text are from the graduate text book Graduate Text in Mathematics 238, A Course in Enumeration, and the problems are those that I encountered in real problem set, so if possible, I'll add a link to the real problem so that you can solve it by yourself. I'll start with the basic formula, one can choose to skip some of the text depending on your grasp with the topic.

Consider a finite set and three subsets , To obtain , we take the sum + + . Unless are pairwise disjoint, we have an overcount, since the elements of has been counted twice. So we subtract . Now the count is correct except for the elements in which have been added three times, but also subtracted three times. The answer is therefore

, or equivalently,

The following formula addresses the case applied to more sets.

The Restricted Inclusion-Exclusion Principle. Let be subsets of . Then

This is a formula which looks familiar to many people, I'll call it The Restricted Inclusion-Exclusion Principle, it can convert the problem of calculating the size of the union of some sets into calculating the size of the intersection of some sets. It's not hard to prove the correctness of this formula, we can just check how often an element is counted in both sides. If , then it's counted once on either side. Suppose , and more precisely, that is in exactly of the sets . The count on the left-hand side is , and on the right hand side, we have

for , thus the equality holds.

Example 1. Let's see an example problem Co-prime where this principle could be applied: Given , you need to compute the number of integers in the interval such that is coprime with , that is, . There are testcases. Constraints: , .

The standard interpretation leads to the principle of inclusion-exclusion. Suppose we are given a set , called the universe, and a set of properties that the elements of may or may not process. Here we can define the properties as we like, such as , , or even . Let be the subset of elements that enjoy property (and possibly others). Then is the number of elements that process none of the properties. Clearly, is the set of elements that possess the properties (and maybe others). Using the notation

we arrive at the inclusion-exclusion principle.

Inclusion-Exclusion Principle. Let be a set, and a set of properties. Then

The formula becomes even simpler when depends only on the size . We can then write for , and call a homogeneous set of properties, and in this case also depends only on the cardinality of . Hence for homogeneous properties, we have

This is the very essence of Inclusion-Exclusion Principle . Please make sure you understand every notation before you proceed. One can figure out, by letting , we arrive at the restricted inclusion-exclusion principle.

Example 2. This problem Character Encoding requires you to compute the number of solutions to the equation , satisfying that , modulo . Constraints: . Hint: the number of non-negative integer solutions to is given by .

Solution

The only thing we need to handle is to get rid of that annoying constraint . To do that, we apply the inclusion-exclusion principle. Let , then is our desired answer. Clearly, this set of properties is homogeneous. Take , then is the number of solutions with . Setting , and it's the same as the number of solutions of the system

, thus the answer is therefore

The complexity of the solution is , due to precomputing factorials and the modular inverses of factorials.

Example 3. Well, this one is a well-known problem. K-Inversion Permutations. The statement is neat and simple. Given N, K, you need to output the number of permutations of length N with K inversions, taken modulo . Constraint: .

Solution

An idea one should come up with instantly is to let as the number of permutations of length with inversions. The recurrence is also trivial: . This is , and can be optimized to using prefix sums, which is still not enough due to the given constraints.

Consider the dp formula, for the th element, we add a number to the number of inversions, so the answer is equal to the number of solutions to satisfying that .

Like the last example, we can apply the inclusion-exclusion principle. Let , then is our desired answer. Applying the similar method we've done solving the last example, we can notice that if the sum of elements of equals to , then the number of solutions to the equation is . Therefore, we can group those sets together. By inclusion-exclusion principle,

where

where .

So the problem becomes calculating all the . We can use the technique as we can computing partition numbers. Partition into two cases where there exist an in the set or not, and then we get the recurrence . Another important observation is that there are at most valid values for . Therefore, the problem is solved in .

Example 4. This problem comes from XVIII Open Cup named after E.V. Pankratiev. Grand Prix of Gomel.Problem K,(Yes, created by tourist:) ) which gives a integer , and requires one to find out the number of non-empty sets of positive integers, such that their greatest common divisor is , and their least common multiple is , taken modulo .Constraint: .

I guess that's the end of this tutorial. IMO, understanding all the solutions to the example problems above is fairly enough to solve most of the problems that require the inclusion-exclusion principle(but only for the IEP part XD). This is my first time of writing an tutorial. Please feel free to ask any questions in the comments below or point out any mistakes in the blog.

This is a problem in CSAcademy Contest Romanian IOI 2017 Selection #3, Pitmutation, which basically is: Given two permutations A, B of length N with some positions fixed while some positions remains unknown, find the number of configurations such that there are exactly S positions p₁, p₂, ..., p_S, where A_pi > B_pi, both N, S ≤ 300.

I've already come up a solution when there are no fixed positions. For simplicity, we can consider B as identity permutation and later multiply the answer by N!. Then we decompose the permutation into cycles. Let dp[i][j] denote the number of configurations, when there are i elements remaining, and the needed number of A_pi > B_pi positions is j. Enumerate the length of cycle the smallest element is in for transferring, which involves precalculating another DP: dp2[i][j] denote the number of permutations A of length i that consists of one cycle such that there are j positions x where A_x > A_{(x + 1)%i}. This precomputation can be done in O(N²). With the help of this array, the original can be calculated in O(N³). Also can be optimized to using FFT. Furthermore, since we only concern the answer with S such positions, and every time we are multiplying the same polynomial, so we only need 2 times of DFT, and thus the complexity is O(N²).

However, I can't generalize this solution to the case where there are fixed positions, and also I can't find an editorial for this problem. Is there anyone willing to share some insights? Thanks in advance!

Here is a problem I encountered during the Barcelona Bootcamp named 'Matrix Coloring':

Let F(n, m, k) be the number of ways to color the grid with n rows and m columns into k colors, such that any two neighbouring cells have different colors. We need to calculate modulo 10⁹ + 7 under the constraints n × m ≤ 50, k ≤ 10⁹.The time limit is 5 seconds.

The official solution involves DP on broken files and hardcode, which the latter part doesn't get me much satisfied. So, can any one offer some different ideas?

Actually, I'm kind of having some of problems dealing with these kinds of matrix coloring problems. Some restrict that the neighbouring cells should have different colors, while some restrict that no column/row should contain the same color, what's the general idea behind this kind of problems? If you know something, please share. Thanks!

Is there any limitation on registering for the site? Or can anyone please tell me how I can register/buy an account for the site? Thanks in advance.