Блог пользователя muhammadhasan01

Автор muhammadhasan01, 5 месяцев назад, По-английски

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
  • Проголосовать: не нравится

»
5 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 месяцев назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

Invariant
»
4 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Easy invariants problem for matrices https://codeforces.me/problemset/problem/1980/E.

»
4 месяца назад, # |
  Проголосовать: нравится 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)$$$