Subsequence to Subarray Transformation Trick
Complexity of Euclid's dvision Lemma
inline int ceildiv(int a,int b){
if(a==0) return 0;
else return (a-1)/b+1;
}Intuitive explaination: You can assume some lines N already existing.
Any line intersecting at two points cuts that plane into two halves. To get max cutting we need to cut all the existing lines.
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.
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?
Proof: https://cp-algorithms.com/algebra/chinese-remainder-theorem.html
How to calculate modulo inverse mod some coprime number?
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];
}If there are ab+1 elements in a sequence then there always exits a monotonic increasing subsequence or decreasing subsequence of length a.
Hint : (x[i],y[i]) Consider at each point #monotonic increasing sequence vs #monotonic decreasing sequence.
- Given a sequence of some numbers find what is the min size of the sequence so that it has increasing/decreasing sequence of length k. let a[i],b[i] be longest increasing/decreasing subsequence till i including x[i]. Then claim that no two tuple exists (a[i],b[i]) & (a[j],b[j]) s.t a[i]=a[j] and b[i]=b[j]. So total distinct tuples: (k-1)x(k-1), we need a sequence of (k-1)x(k-1)+1
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.
Proof:
* [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.
- Horner-type representation: Rep(x)= x8*(w7w6....w0)+x7(w6.....w0)+x6*(w5.....w0)+x5*(w4.....w0)+...+x0*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)
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))
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
- Start with gcd(a,b).
- After one step, (a%b, b)
- After second step, (b%(a%b), a%b)
- Initial Sum = a + b
- Final Sum = (a%b) + (b%(a%b)) = c + d
- c + bk = a => a > c + b
- d + ck = b => b > d + c
- a + b > c + d + d + b
- a + b > c + d + d + c
- a + b > 2 (d+c)
- d + c < (a+b)/2
- After two rounds of the algorithm sum of a+b halves. So logarithm time
Another cute way of looking at the complexity:
-
Consider a = Fibo[N], b = Fibo[N-1]
-
Worst Case when a = Fibo(N), b = Fibo(N-1) and the algorithm goes like:
-
(f(n), f(n-1)) -> (f(n)-f(n-1), f(n-1)) -> (f(n-1), f(n-2)) ----> 1
-
f(n) = phi ^ n : Bennet's formula
-
n = log(f(n)) or n = log(min(a,b))
-
Trivia: GCD(Fibo(N), Fibo(N-1)) = Fibo(GCD(N,N-1)) = Fibo(1) = 1 Proof:
-
https://www.cut-the-knot.org/arithmetic/algebra/FibonacciGCD.shtml