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.
thanks!!
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.
Easy invariants problem for matrices https://mirror.codeforces.com/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)$$$