Invariant is a property that remains unchanged after operations/transformation, we see this a lot in competitive programming, especially with operations involved.

Simple Example

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.

Problem 1

Problem 2

Problem 3

Problem 4

Problem 5

Problem 6

Problem 7

• +71

 » 2 months ago, # |   +11 These problems pop into my mind when talking about invariants in competitive programming. They are quite similar.
•  » » 2 months ago, # ^ |   0 thanks!!
•  » » 2 months ago, # ^ |   0 Nice, I've added this to the blog content as well
 » 2 months ago, # |   0 If I understand your solution to problem 2 correctly, I think you should specify that you are considering each bit separately.
 » 2 months ago, # |   +9 One that's appeared many times are variations on 1025C - Plasticine zebra. InvariantThe cyclic version of the array doesn't change, except for orientation.
 » 3 weeks ago, # |   +8 Easy invariants problem for matrices https://mirror.codeforces.com/problemset/problem/1980/E.
 » 3 weeks ago, # |   0 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)$