muhammadhasan01's blog

By muhammadhasan01, 7 days ago, In English

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

  • Vote: I like it
  • +66
  • Vote: I do not like it

»
7 days ago, # |
  Vote: I like it +11 Vote: I do not like it

These problems pop into my mind when talking about invariants in competitive programming. They are quite similar.

  • »
    »
    7 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks!!

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nice, I've added this to the blog content as well

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

If I understand your solution to problem 2 correctly, I think you should specify that you are considering each bit separately.

»
6 days ago, # |
  Vote: I like it +9 Vote: I do not like it

One that's appeared many times are variations on 1025C - Plasticine zebra.

Invariant