Invariant is a property that remains unchanged after operations/transformation, we see this a lot in competitive programming, especially with operations involved.
Given an array $$$a$$$ of $$$n$$$ integers with $$$n \geq 2$$$, in one operation you can choose two different indices $$$i$$$ and $$$j$$$ $$$(1 \leq i, j \leq n)$$$ and increment $$$a_i$$$ with $$$1$$$ and decrement $$$a_j$$$ with $$$1$$$.
Given another array $$$b$$$ of $$$n$$$ integers, is it possible to change $$$a$$$ to $$$b$$$ with some operations?
It is easy to see that the invariant for this problem is that: The sum of all the integers in $$$a$$$ will remain unchanged.
With that information, we can further prove that it is possible to change $$$a$$$ to $$$b$$$ if the sum of integers in $$$a$$$ is equal to the sum of integers in $$$b$$$.
I wanted to make an "Invariant List" here so the community could benefit from it, if you have some invariants in mind share with us in the comment below, or you could also share some tips/insights to find invariants effectively.
I'd like to share some interesting invariants myself here, I've found these in some online judges, but I won't discuss too much of the detail for the solution/proof.
Given $$$n$$$ $$$(n \geq 3)$$$ distinct integers $$$a_1, a_2, \cdots, a_n$$$, in one operation you can do the following:
- Pick 3 pairwise distinct indices $$$i, j, k$$$ $$$(1 \leq i, j, k \leq n)$$$
- Apply $$$i \to j \to k \to i$$$ cycle to the array, It simultaneously places $$$a_i$$$ on position $$$j$$$, $$$a_j$$$ on position $$$k$$$ and $$$a_k$$$ on position $$$i$$$, without changing any other element.
Determine whether you can sort the integers by performing any number of operations.
The parity for the number of invertions of the array remains the same after any number of operations.
Given a tree with $$$n$$$ nodes $$$(n \geq 2)$$$ with node $$$u$$$ having an integer value of $$$a_u$$$, you are also given a positive integer $$$k$$$.
In one operation you can do the following:
- Choose an edge $$$(u, v)$$$
- Change $$$a_u$$$ to $$$a_u \oplus{} k$$$
- Change $$$a_v$$$ to $$$a_v \oplus{} k$$$
Determine the maximum possible sum of the values in the tree by performing the operation any number of times.
Let's call a node marked when the initial value has changed, then the number of marked nodes is always even.
Furthermore, we can pick any set of nodes (as long as the number of it is even) and mark those nodes.
Similar Problem: LeetCode Biweekly 125 — Q4
Given a binary string $$$s$$$ with length $$$n$$$, initially all the character of $$$s$$$ is $$$0$$$.
You are given an integer $$$x$$$ such that $$$1 \leq x \leq n$$$
In one operation you can choose any substring of $$$s$$$ with size $$$x$$$ and flip (turn $$$0$$$ to $$$1$$$ or turn $$$1$$$ to $$$0$$$) the characters in the substring.
Given another binary string $$$p$$$ with length $$$n$$$, determine whether you can make $$$s$$$ into $$$p$$$ with some number of operations (or not at all)
Let $$$f(k)$$$ be the XOR of all values of $$$s[i]$$$ such that $$$i \text{ mod } x=k$$$
Then we will find that for every operation, $$$f(0)=f(1)=\cdots=f(x-1)$$$ will always hold.
Similar Problem: 1630D
Given $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$, in one operation you can do the following:
- Choose an index $$$i$$$ such that $$$2 \leq i \leq n - 1$$$
- Change $$$a_i$$$ to $$$a_{i+1} + a_{i-1} - a_i$$$
Given another $$$n$$$ integers $$$b_1, b_2, \cdots, b_n$$$, is it possible to change $$$a$$$ into $$$b$$$ with any number of operations?
Let $$$d_i = a_{i+1} - a_i$$$, an operation at index $$$i$$$ is the same as swapping $$$d_i$$$ with $$$d_{i-1}$$$ therefore the set of values of $$$d$$$ remains unchanged.
Similar Problem: 1110E
Given $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$, in one operation you can do the following:
- Choose an index $$$i$$$ such that $$$2 \leq i \leq n - 1$$$
- Change $$$a_{i-1}$$$ to $$$a_{i-1} \oplus{} a_i$$$
- Change $$$a_{i+1}$$$ to $$$a_{i+1} \oplus{} a_i$$$
Given another $$$n$$$ integers $$$b_1, b_2, \cdots, b_n$$$, is it possible to change $$$a$$$ into $$$b$$$ with any number of operations?
Let $$$p$$$ be the prefix XOR of array $$$a$$$, an operation at index $$$i$$$ is the same as swapping $$$p_i$$$ with $$$p_{i-1}$$$ therefore the set of values of $$$p$$$ remains unchanged.
Similar Problem: 1906B
Given $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$ with $$$n$$$ being even, in one operation you can do the following:
- Choose an integer $$$k$$$ such that $$$1 \leq k \leq \frac{n}{2}$$$
- Swap the prefix of length $$$k$$$ with the suffix of length $$$k$$$
Is it possible to sort the integers using any number of operations?
Let $$$S$$$ be the multiset of unordered pair of elements of $$$\left(a_i, a_{n-i+1} \right)$$$ for all $$$1 \leq i \leq \frac{n}{2}$$$, then the set $$$S$$$ remains unchanged.
Similar Problem: 1365F
Given $$$n$$$ integers $$$a_1, a_2, \cdots, a_n$$$, in one operation you can do the following:
- Choose an index $$$i$$$ such that $$$2 \leq i \leq n - 2$$$
- Change $$$a_{i-1}$$$ to $$$a_{i-1} + a_i + a_{i+1}$$$
- Change $$$a_i$$$ to $$$-a_{i+1}$$$
- Change $$$a_{i+1}$$$ to $$$-a_i$$$
- Change $$$a_{i+2}$$$ to $$$a_i + a_{i+1} + a_{i+2}$$$
Given another $$$n$$$ integers $$$b_1, b_2, \cdots, b_n$$$, is it possible to change $$$a$$$ into $$$b$$$ with any number of operations?
Let $$$p$$$ be the prefix sum of array $$$a$$$, an operation at index $$$i$$$ is the same as swapping $$$p_{i+1}$$$ with $$$p_{i-1}$$$ therefore the set of values of $$$p$$$ at odd indexes remains unchanged, and the set of values of $$$p$$$ at even indexes remains unchanged as well.
Similar Problem: CodeChef ATBO
These problems pop into my mind when talking about invariants in competitive programming. They are quite similar.
Nice, I've added this to the blog content as well
If I understand your solution to problem 2 correctly, I think you should specify that you are considering each bit separately.
One that's appeared many times are variations on 1025C - Plasticine zebra.
The cyclic version of the array doesn't change, except for orientation.
Could please explain via small example, i dont get wdym by cyclic version of array
Easy invariants problem for matrices https://codeforces.me/problemset/problem/1980/E.
Just curious: For state set $$$S$$$ and transition set $$$T$$$, what do we call function $$$f$$$ if the following condition hold? The largest invariant?
$$$(s_1, s_2) \in T \iff f(s_1) = f(s_2)$$$
I know it's a bit late, but $$$T$$$ is called the (set-theoretic) kernel of $$$f$$$; $$$f$$$ itself doesn't really have a name as this can be defined for any function. More about this can be found here.
bump, last div2 D (2252D - Array Replacement) is very similar to problem 4 here,
crazy rating deflation
there is an array of length N and N persons that are on each position. In each query, the persons on the cells with value X moves left or right (to the previous/next cell); if they move out of bounds, they become unchanged after. Find the total number of out of bound positions after all queries.
the list of position of the persons is always monotonic.
I don't think this holds. Lets say wlog we take a person who starts at cell 3, we then move all people on cell 3 right. Person is on cell 4, we then query cell 4 left and that person is on cell 3. Thus the cell that person is on is not monotonic since it can increase and decrease. I think the number of out of bounds positions is monotonic at all times?
here the query refers to the cells's values, and the list of positions of persons (from 1 to N) is monotonic, not the position itself. i should have clarified that.
problem 5 reminds me of High Templars.
Denote $$$p_i$$$ as $$$\sum \limits_{j = 1}^i a_j$$$, then an operation is equivent to swapping $$$p_{i - 1}$$$ and $$$p_i$$$.
can someone suggest a good maths book or any other resoruce conatining invariant problems
Arthur Engel's book contains a great chapter on it.