CP Tricks

cumilitive sum(csum) of matrix (1,1) to (i,j) csum[i][j]=csum[i-1][j]+csum[i][j-1]-
csum[i-1][j-1]+matrix[i][j]
query of any sum of rectangle(x1,y1,x2,y2)=csum[x2][y2]-csum[x2][y1-1]-csum[x1-1]
[y2]+csum[x1-1][y1-1];
Rotate by 45 degree to linearize distance:

Eg if distance between two points is given as max(abs(x1-x2),abs(y1-y2))
it can be written in form summation form by changing cordinate x1=(x1+y1),y1=(x1-
y1)
distance will be (abs(x1-x2)+abs(y1-y2))/2;
//https://atcoder.jp/contests/abc351/tasks/abc351_e
Re-root the tree technique.

first caluclate by subtree rooting in dfs , and then calcuate the re-rooted value
by second dfs
//https://cses.fi/problemset/result/7013514/
when finding max/min after operation on strings

see what string will look like when no operations can be performed on
it.Eg:https://www.codechef.com/START133A/problems/ABCC3
when two parameters are there in greedy, may be sort by one and use heap/multiset
on other parameter.
Eg:https://leetcode.com/problems/minimum-cost-to-hire-k-workers/?envType=daily-
question&envId=2024-05-11
when on ith move we can move by +i or -i, then minimum steps to reach a point p is,
let d(x)=(x*x+x)/2 and d(x) >=p , if differnece between d(x)-p is even and less
than x then in atmost 1 extra jump exactly p can be achieved.
permutation cycles, edge between i and p[i], graph is a componenet, where each
component is a simple cycle.
For these type of questions https://codeforces.com/blog/entry/129410

Every subarray the first and last element should be min or max
Every subarray should be monotonically increasing or decreasing
Lexicographically least topsort , instead of queue use priortiy queue in regular

topsort algo
In row and column operations, think if anyone can be done first

https://leetcode.com/problems/score-after-flipping-matrix/description/?
envType=daily-question&envId=2024-05-13
counts how many times a edge will be used, to count the number of operations.
https://leetcode.com/problems/distribute-coins-in-binary-tree/submissions/
1260964237/?envType=daily-question&envId=2024-05-18
top set bottom set trick for median running or top k type of queries with updates.
maintain multisets of elements.
Multisource bfs-https://www.codechef.com/problems/PRISON
//identity
x+y = (x^y) + 2(x&y)
floor((x^y)/2)=floor((x/2) ^ (y/2))=floor(x/2) ^ floor(y/2)
x < y < z we always have min(x^y, y^z) < x^z.
any set of integers,
the minimum bitwise XOR between some pair of them will always be obtained by some
adjacent pair in sorted order.
piegonhole principle
Segtree to find largets sum sequence with non adjcent element

https://leetcode.com/problems/maximum-sum-of-subsequence-with-non-adjacent-
elements/submissions/1268288437/
LIS in o(nlogn) without merge sort

int LIS(int arr[], int N)
{
// Your code goes here
vector<int> v;//stores the LIS
v.push_back(arr[0]);
for(int i=1;i<N;i++){
auto it=upper_bound(v.begin(),v.end(),arr[i]);
if(it==v.end()){
v.push_back(arr[i]);
}else{
*it=arr[i];//replace the bigger number with smaller one, makes
space for longer sequence
}
}
return v.size();
}
Number of occurences of s2 as subsequence in s1

int countWays(string s1, string s2) {
// code here
int n=s1.size(),m=s2.size();
vector<vector<int> > dp(n+1,vector<int> (m+1,0));
int ans=0,mod=1e9+7;
for(int i=0;i<=n;i++){
dp[i][0]=1;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=dp[i-1][j];
if(s1[i-1]==s2[j-1]){
dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod;
}
return dp[n][m];
}
Think binary operations (/2,*2,*2+1) etc with help of binary tree, visulaize, check
for parity of operations etc.
https://codeforces.com/contest/1981/problem/C
Find total number of segment[l,r] intersects- make a array of (l,-i),(r,i) and sort
it and count the actives points at end of each segment
and count the sum.
https://atcoder.jp/contests/abc355/tasks/abc355_d
sum over all pairs (i,j) with i<j iin A is symmetric for i and j, rearrange the
sequence without changing the answer.
assume A is sorted in ascending order.
LExicogrpahic maximum / least when deleting charachter look at the next character
which replaces the current character,
i.e look at index i+1 if index is being deleted.
https://codeforces.com/problemset/problem/983/B think of [l,r] computationi n

matrix as a 2-d matrix, may help .
look for invariants in swapping 2-d matrix

problems,https://codeforces.com/contest/1980/problem/E
functional graphs-each node outdegree is 1
when abs and addition are involved, keep track of maximum and minimum possible
https://codeforces.com/contest/1984/problem/C1
https://codeforces.com/contest/1985/problem/G all digit can be 9/k at most because

carry on mutiplication will
Think of regular bracket sequence as tree,

On open bracket create a new child node and move to it and on closed bracket move
to parent.
hash of each subtree will be based on hash of each children,all leaf node will have
hash of 1.
No of permutations in which i th smallest elemetn is smaleest in the cycle it is

part of is N!/i
(x, y) to calculate the Manhattan distances between them, instead of using |x1-x2|
+|y1-y2|
convert all points (x, y) into (x+y, x-y) and the distances will become max(|x1-
x2|, |y1-y2|) (also known as Chebyshev distance).
https://codeforces.com/blog/entry/57534
https://www.codechef.com/problems/GRAPHCOST
select prefix minimum as much as possible,once prefix does not decrese select
prefix minmum by reversig the array.
dsu by sorting edges of tree according to edge length, then computing stats.
https://practice.geeksforgeeks.org/contest/job-a-thon-34-hiring-challenge/problems
Operations related to MEX, distinct element count, max element, number of elements
Upto 10^12 there can be atmost 300 non-prime numbers between any two consecutive
prime numbers.
When A≤B then floor(B−1/A)≤N≤ceil(B−1/A) where N is the number of multiples of A
between any two multiples of B
gcd(F[n],F[m])=F[gcd(n,m)], where F[x] is the xth fibonacci numbers and first two
terms are 0,1
IF two properties are there and oredering based on them, remove useless elements,
see the limits on elements.
https://codeforces.com/contest/1987/problem/D
think about only frequency, moves for B os tp remove elemtns such that number of
distinct elements are reduced.
currently on index i,and j extra moves available,maximum possible elements that can
be removed by B
https://atcoder.jp/contests/abc360/tasks/abc360_e
probablity of only 1 is different rest all are same, use this to compute final
probablity in a loop, think like state diagram
when operation on adjacent elements,

think differnce array, think about even and odd number of elemnts
Swapping adjacent elements in a distinct array is basically trying to equate two

permutations using adjacent swaps.
possible when same number of inversions
https://math.stackexchange.com/questions/203835/enumerating-number-of-solutions-to-
an-equation
https://codeforces.com/contest/1988/problem/D
//dp[v][i]= the value if the vertex v is removed in ith round
//total loss is a[i]*b[i],where b[i]= round in which it is removed.
//as adjacent items can;t be picked in same round, round number will differ.
//due to max set The "independent set" constraint ,the upper bound will be around
19

CP Tricks

Uploaded by

Copyright:

Available Formats

CP Tricks

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CP Tricks

Uploaded by

Copyright:

Available Formats

cumilitive sum(csum) of matrix (1,1) to (i,j) csum[i][j]=csum[i-1][j]+csum[i][j-1]-

Rotate by 45 degree to linearize distance:

Re-root the tree technique.

when finding max/min after operation on strings

For these type of questions https://codeforces.com/blog/entry/129410

Lexicographically least topsort , instead of queue use priortiy queue in regular

In row and column operations, think if anyone can be done first

Segtree to find largets sum sequence with non adjcent element

LIS in o(nlogn) without merge sort

Number of occurences of s2 as subsequence in s1

vector<vector<int> > dp(n+1,vector<int> (m+1,0));

https://codeforces.com/problemset/problem/983/B think of [l,r] computationi n

look for invariants in swapping 2-d matrix

functional graphs-each node outdegree is 1

https://codeforces.com/contest/1985/problem/G all digit can be 9/k at most because

Think of regular bracket sequence as tree,

No of permutations in which i th smallest elemetn is smaleest in the cycle it is

when operation on adjacent elements,

Swapping adjacent elements in a distinct array is basically trying to equate two

You might also like