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

I recently came across Jiangly's code, where I learned a "shorter" way to create multidimensional vectors in C++.

vector<vector<vector<int>>> dp(n, vector<vector<int>>(m, vector<int>(k)));


You can use this shorter syntax:

vector dp(n, vector(m, vector<int>(k)));


I'm not sure which C++ version supports this syntax (probably C++11 or later).

Although the shorter syntax doesn't really make it really "short" as opposed to creating multidimensional array, I think this is worth knowing.

Is there any shorter syntax for multidimensional vector in C++? I know we can use this blog's template, though we might need to copy paste the template first.

• +72