Table of Contents

Custom Ceil Function Lazy Caterer Chinese Remainder Theorem Derangement Chicken Mcnugget Theorem Erdos Szekeres Theorem Cyclicity Parity of Permutation Rank in Arbitrarty Bases Floyd Cycle Manhattern Trick Subsequence to Subarray Transformation Trick Complexity of Euclid’s dvision Lemma Difference Array, Sort, Repeat Hockey Stick Identity Catalan Number Stirling Number of Second Kind Stars and Bars

Custom Ceil function

    inline int ceildiv(int a,int b){
          if(a==0) return 0;
          else return (a-1)/b+1;
    }

Lazy Caterer

F[N] = F[N-1] + N

Intuitive explaination: You can assume some lines N already existing. </br> image </br> Any line intersecting at two points cuts that plane into two halves. To get max cutting we need to cut all the existing lines.</br> Consider a line far away(pink) which intersects with all the lines N(all diverging and sorted by slopes increasing). So maximum cuts increases by (N-1) + 2(open spaces) i.e F[N+1] = F[N] + N+1. Hence this is optimal proven. </br>

Now coming to cake cutting problem, since this construction exists, we can zoom(scale in) out everything and fit in the cake geometry.

Chinese Remainder Theorem

If Alice has x number of apples such that she can divide the apples in mi groups with ri remaining, for some i’s. What is the minimum no of apples she posses?</br>

Proof: https://cp-algorithms.com/algebra/chinese-remainder-theorem.html

How to calculate modulo inverse mod some coprime number?</br>

inline ll mod(ll x,ll m){ return (x%m+m)%m; }

ll extgcd(ll a,ll b,ll &x,ll &y){
      if(b==0){
          x=1ll;
          y=0ll;
          return a;
      }
      ll x1,y1;
      ll g = extgcd(b,a%b,x1,y1);
      x = y1;
      y = x1 - y1*(a/b);
      return g;
}

inline ll inv(ll a,ll m){
            ll x,y;
            ll g = extgcd(a,m,x,y); 
            assert(g==1);
            return mod(x,m);
    }

inline ll crt(ll r[],ll m[]){
		ll y[10],p[10];
		y[0] = r[0]; p[0] = 1;
		
		for(int k=1;k<N;k++){
				p[k] = p[k-1]*m[k-1];
				ll q = inv(p[k],m[k]);
				y[k] = mod(y[k-1]+(r[k]-y[k-1])*q*p[k],p[k]*m[k]);
			}
		return y[N-1];
}

Derangement

Solving permutation with fixed points k or more: N! - Sum{D(N,k)} k = 0…K-1 https://en.wikipedia.org/wiki/Rencontres_numbers and calcuate.

  • D[N] = (N-1)(D[N-1]+D[N-2])

    Chicken McNugget Theorem

    Ref : https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem https://brilliant.org/wiki/postage-stamp-problem-chicken-mcnugget-theorem/

    If there are two number a,b which are relatively prime, the greatest number which can be represented using a & b is (a-1)(b-1)+1.

    Also exactly half of them 1 to ab - a -b is representable and half is not. And if the numbers are not coprime just divide by gcd (a,b). pattern will be multiple of gcds. Also exactly one of (k, ab-a-b-k) is representable.

    Erdos Szekeres Theorem

    If there are ab+1 elements in a sequence then there always exits a monotonic increasing subsequence or decreasing subsequence of length a. </br> Hint : (x[i],y[i]) Consider at each point #monotonic increasing sequence vs #monotonic decreasing sequence.

    Cyclicity

    https://codeforces.com/contest/1367/problem/E

    image

    Parity of Permutation:

  • https://www.geeksforgeeks.org/number-of-transpositions-in-a-permutation/

  • https://www.geeksforgeeks.org/even-and-odd-permutations-and-their-theorems/

    Idea: Parity of permutation does not change after doing three cycle swaps. So if starts with parity=0, you can reach sorted permutation as parity of permutation=parity of inversion count.</br>

    Proof:</br> * [abc] after 3 cycle sort is [bca]. * [abc]—>[bac]—->[bca]. Parity=+(1+1)%2=0 * Each adjacent swaps changes inversion count by 1.

    Rank in Arbitrary Bises

    Lets say the wts of the groups be given as: (w8 w7 w6 w5 w4 w3 w2 w1 w0)

    What is the representation of the rank=x element? rank is calulated from 1 but we calculate from 0, so x=x-1.

    How to get the vector <x8,x7,….x0>?

    Algorithm:

    x0 = x % w0 —> x/=w0 x1 = x % w1 —> x/=w1…. and so on!

    Floyd Cycle

    image

    Manhatten Trick

    Also called 45 degree rotation trick, given any Manhatten metric convert it to Chebyshev metric. |x| = max(x,-x) </br> dist(x1,x2) = |x1-x2|+|y1-y2| = max(x1-x2,x2-x1) + max(y1-y2,y2-y1) = max(x1+y1-x2-y2,x1-y1-x2+y2,-x1+y1+x2-y2,-x1-y1+x2+y2)

    Given a specific point, to find closest or farthest distance from it:

    ans= max(dist(x0, x)) = max(max(x0+y0-x-y,x0-y0-x+y,-x0+y0+x-y,-x0-y0+x+y))) = max(x0+y0-min(x+y),x0-y0-min(x-y),-x0+y0+max(x-y),-x0-y0+max(x,y))

    Practice problems:

    https://codeforces.com/contest/1979/problem/E

    Subsequence -> Subarray (Pref Sum)

    Given a signed (+/-) operation in subsequence, it can be converted to contiguous operation in prefix sum array and prove it is a bijection. Operation in pref sum world is tractable and easier to solve. Cool transformation trick.

    Eg. https://codeforces.com/problemset/problem/1775/E

    Complexity of Euclid’s Division Lemma

    Another cute way of looking at the complexity:

    Difference Array, Sort, Repeat

    This is cool complexity trick I learnt while solving https://codeforces.com/contest/1707/problem/B.

    Claim: After some iteration, non-zero elements will perish! Let’s say after k operations on the array, there will be m non-zero element.

    Proof:

    https://en.wikipedia.org/wiki/Tetrahedral_number

    Other ideas here:

    (Imp) Idea : BITWISE proofs (ref: aryanc403):

    Prime and Perfect Squares

    Main Idea : Even powers of primes in a number neutralize in the whole process among themselves. Consider only prime factors ^ (power % 2) for the problems.

    Hockey Stick Identity

    C(r,r) + C(r+1,r) + C(r+2,r) + C(r+3,r) + … + C(N,r) = C(N+1,r+1)

    Catalan Number

    Catalan (N, K) = INV(binpow (N+1)) * Choose (2 * N, N)

    Catalan number comes up in problems involving producer and consumer, say a consumer can only come when there is a producer. Like counting bracket balancing sequences, ants going up to the matrix top without crossing diagonal etc.

    For more review dp/catalan.md file.

    Example: https://www.codechef.com/problems/CNTISFN343

    Stirling Number of Second Kind

    Number of ways of distributing N distinguishable objects into K indistinguishable bins.

    Nth item can be kept as a singleton or not.

    Transition: F(N, K) = F(N - 1, K - 1) + K * F(N - 1, K - 1)

    Stars and Bars Method

    Many combinatorial problem can be reduced to stars and bars method. Consider the problem where you need to find number of combinations of k elements in an array such that no two elements are adjacent.

    Well, try to see the structure.

    ……x….x….x.x..x…….x.x….

    It is like there should be at least one dots between two crosses. Consider r[1] + r[2] + … + r[k+1] = N - K where, r[1] >= 0, r[k + 1] >= 0 and other r[i] >= 1. Can you reduce this to a stars and bars problems?

    Sum … r[i] = N - K - (K - 1) Sum … r[i] = N - 2K + 1, where r[i] >= 0.

    Number of possibilities = C (N - 2K + 1 + K, K) = C(N - K + 1, K).