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

• +66

 » 7 days ago, # |   +11 These problems pop into my mind when talking about invariants in competitive programming. They are quite similar.
•  » » 7 days ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } thanks!!
•  » » 6 days ago, # ^ |   0 Nice, I've added this to the blog content as well
 » 6 days ago, # |   0 If I understand your solution to problem 2 correctly, I think you should specify that you are considering each bit separately.
 » 6 days 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.