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
inline int ceildiv(int a,int b){
if(a==0) return 0;
else return (a-1)/b+1;
}
F[N] = F[N-1] + N
Intuitive explaination: You can assume some lines N already existing. </br>
</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.
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];
}
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])
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.
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.
https://codeforces.com/contest/1367/problem/E
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.
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!
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
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
Another cute way of looking at the complexity:
n = log(f(n)) or n = log(min(a,b))
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):
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.
C(r,r) + C(r+1,r) + C(r+2,r) + C(r+3,r) + … + C(N,r) = C(N+1,r+1)
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.
Example: https://www.codechef.com/problems/CNTISFN343