this blog will talk about the info needed to solve DP problems in general.

DP or dynamic programming is a method used to solve bigger problems be dividing them in some way

however while learning DP i recommend being similar with some data structures , sometimes we might just need a set or a map but at expert level i recommend being familiar with segment tree data structure.

this blog will be divided into phases where i explain some basic DP problems or explain some DP method in general.

each phase will contain codes and examples , you can ask more questions in comments.

1.Fibonacci

sorry for this i really know this is what people tend to explain when doing DP but hear me out

the standard Fibonacci function looked something like this

int f(int n){
   if(n<1)return 0;
   return f(n-1)+f(n-2);
}

thinking about the complexity of this code , it appears that if takes $$$O(f(n))$$$ time complexity.

you should know that $$$f(40)=102334155$$$ so we may not be able to compute $$$f(50)$$$ or anything greater with this function!.

or.. can we do something to make this even faster?

note that computing $$$f(i)$$$ will call $$$f(i-1)$$$ and $$$f(i-2)$$$ but then calling $$$f(i-1)$$$ will also call $$$f(i-2)$$$ , so here is the catch , lets change our function so that whenever we are computing $$$f(n)$$$ for a second time we return the previously computed answer, something like so

int mem[N],vis[N];
int f(int n){
    if(n<1)return 0;
    if(n==1)return 1;
    if(vis[n])return mem[n];
    vis[n]=1;
    return mem[n]=f(n-1)+f(n-2);
}

what is the complexity now? , turns out it is $$$O(N)$$$ as we may compute each item at most once and the rest will be returned in $$$O(1)$$$.

this is the trick behind (some) DP methods , but knowing this method we will jump into some actual problems that use it.

Frog 1

no comment needed , you may just observe how similar this is to Fibonacci (or you might just jump to solve it directly).

dp(i)=min(dp(i-1)+|h(i)-h(i-1)|,dp(i-2)+|h(i)-h(i-2)|)

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const int N=300000;
ll n,ans[N],h[N];
bool vis[N];
ll dp(int i)
{
    if(i==1)return 0;
    if(i<1)return 2e15;
    ll &res=ans[i];
    if(vis[i])return res;
    vis[i]=1;
    return res=min(dp(i-1)+abs(h[i]-h[i-1]),dp(i-2)+abs(h[i]-h[i-2]));
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>h[i];
    cout<<dp(n);
}

your task is now to try and solve Frog 2.

2. more conditions

previously we only needed to handle one state where as in most cases we may need more , it is really funny how some people solve DP problems with $$$7$$$ states and you see their code like how are you even understanding this!.

lets go even deeper , two states it is , and the problem Vacation might be a best choice for this.

dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i]
dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i];

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const int N=300000;
ll n,a[N],b[N],c[N];
ll dp[N][3];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i]>>b[i]>>c[i];
    for(int i=1;i<=n;i++){
        dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
        dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
        dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i];
    }
    cout<<max({dp[n][0],dp[n][1],dp[n][2]});
}

for(int i=1;i<=n;i++)dp(i);

3.Knapsack

this problem was really pain to understand at first , and it is not really present in the contest as long as i can see, we will now talk about Knapsack 1.

in this problem we have to compute $$$dp(W)$$$ as the maximum profit from a capacity of $$$W$$$, now we need to know how to compute it using previous states , when we use an item we add ts value and subtract its weight like so

dp(W)=max(dp(W-w[i])+v[i])

but this way we may use an item more than once (the problem).

and so we may need to add extra state to know which items were used

our state will be $$$dp[W][2^{100}]$$$ (just kidding this is impossible ).

i will leave you to think on how to solve this.

for(int i=1;i<=n;i++){
    for(int j=W;j-w[i]>=0;j--){
        dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    }
}

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const int N=100010;
ll n,W,w[N],v[N];
ll dp[N];
signed main(){
    cin>>n>>W;
    for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++){
        for(int j=W;j-w[i]>=0;j--){
            dp[j]=max(dp[j-w[i]]+v[i],dp[j]);
        }
    }
    cout<<dp[W];
}

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const int N=100010;
ll n,w[200],v[200],W;
ll mem[101][N];
bool vis[101][N];
ll dp(int i,int W){
    if(i==n+1)return 0;
    if(vis[i][W])return mem[i][W];
    vis[i][W]=1;
    ll &res=mem[i][W];
    res=dp(i+1,W);
    if(W-w[i]>=0){
        res=max(res,dp(i+1,W-w[i])+v[i]);
    }
    return res;
}
signed main(){
    cin>>n>>W;
    for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
    cout<<dp(1,W);
}

try to solve Knapsack 2 !

4.Tracing

Ok! now we are able to find the minimum,maximum whatsoever but how do we actually know how we reached the answer? like in Knapsack how do we know what items we choose?

till now we used only two arrays mem(the answer),vis(did we calculate it before?)

now we will use another array to know from which state we got our best answer after calculating the answer we use this array to trace it.

we will present this in a simple problem like this problem this problem was solved once and i saw $$$2$$$ or maybe more standard problems like it,

the state was like $$$dp[index in S][index in T]$$$

but knowing the transition might be hard so i will leave you to think!

int &res=ans[i][j]
if(s[i]==t[j]){
    res=dp(i+1,j+1)+1;
}
res=max({res,dp(i,j+1),dp(i+1,j)};

this way we made sure we tried all cases

we tried matching the current positions and incrementing each index by one,and so (somehow!) we can say we tried every case and got the best answer in the end!.

the code for the answer would be something like this

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const int N=100010;
string s,t;
int n,m;
int ans[4000][4000],to[4000][4000],vis[4000][4000];
int dp(int i,int j){
    if(i==n||j==m)return 0;
    int &res=ans[i][j];
    if(vis[i][j])return res;
    vis[i][j]=1;
    if(s[i]==t[j]){
        to[i][j]=1;
        res=dp(i+1,j+1)+1;
    }
    if(dp(i+1,j)>res){
        to[i][j]=2;
        res=dp(i+1,j);
    }
    if(dp(i,j+1)>res){
        to[i][j]=3;
        res=dp(i,j+1);
    }
    return res;
}
void trace(int i,int j){
    if(i==n||j==m)return;
    switch(to[i][j]){
        case 1:{
            cout<<s[i];
            trace(i+1,j+1);
            break;
        }
        case 2:{
            trace(i+1,j);
            break;
        }
        case 3:{
            trace(i,j+1);
            break;
        }
    }
}
signed main(){
    cin>>s>>t;
    n=s.size();
    m=t.size();
    dp(0,0);
    trace(0,0);
}

5.Time complexity

a main issue in DP as we really need to calculate this before going forward with our solution. the time complexity is simply sum of number of operations in all states

for simplicity i usually calculate the complexity of the dp function and multiply this by the number of states (this is not precise in general)

we will go forward with an example Candies

at first glance you might think you knew the solution, but usually you will get a TLE , why?.

lets say your dp function looked like this:

for(int j=0;j<=min(a[i],k);j++){
    res+=dp(i+1,k-j);
}

what is the complexity of this?

for each $$$dp[index][number of candies]$$$ we will loop (in worst case) on the number of candies, which means our complexity is $$$nk^2$$$ (an absolute disaster) we will have to get this loop in $$$O(1)$$$ for this to work.

i recommend you try to solve it.

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const int N=100010,M=1e9+7;
int n,a[200],K;
ll dp[101][N],p[101][N];
signed main(){
    cin>>n>>K;
    for(int i=1;i<=n;i++)cin>>a[i];
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        p[i-1][0]=dp[i-1][0];
        for(int k=1;k<=K;k++)p[i-1][k]=dp[i-1][k]+p[i-1][k-1];
        for(int k=0;k<=K;k++){
            dp[i][k]=p[i-1][k];
            if(k-min(k,a[i])>0)dp[i][k]+=M-p[i-1][k-min(k,a[i])-1];
            dp[i][k]%=M;
        }
    }
    cout<<dp[n][K];
}

6.DP left right

this kind is as easy as it sounds (maybe the most unexpected answer for a problem)

you might even be able to solve the Deque problem yourself

the idea is to get the answer of an array by getting the answer of some sub arrays .

lets try to solve the problem

the state is as following:

dp[L][R][player] = dp[3000][3000][2]

knowing this we can do two transitions:

dp[L+1][R][1-player] or dp[L][R-1][1-player]

so the answer would look like:

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const int N=100010,M=1e9+7;
ll n,a[3001],k;
ll mem[3001][3001][2];
bool vis[3001][3001][2];
ll dp(int L,int R,int P){
    if(L>R)return 0;
    if(vis[L][R][P])return mem[L][R][P];
    vis[L][R][P]=1;
    ll &res=mem[L][R][P];
    if(P){
        res=min(dp(L+1,R,1-P)-a[L],dp(L,R-1,1-P)-a[R]);
    }else{
        res=max(dp(L+1,R,1-P)+a[L],dp(L,R-1,1-P)+a[R]);
    }
    return res;
}
signed main(){
    cout<<fixed<<setprecision(10);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    cout<<dp(1,n,0);
}

another good example on this would be Slimes

try to solve it yourself the continue.

Break

here we are actually done with standard DP

from now on we will tend to explain somethings in short and less explained way

till now the learned info is more than enough till expert level or even master level

after this there will a bunch of hard topics that are considered DP approach (each one may need a whole new blog).

you now are able to solve these:

Longest Path

Grid 1

Coins

Stones

7.DP with a trick

this trick was so amazing when i learned it

in the past we learned that DP goes in a single direction but what if the DP calls itself?

here is an example Sushi

the state of the DP here is

you may try to solve this on your own at first

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#define ld long double
const int N=100010,M=1e9+7;
int n,a[400],K;
ld mem[301][301][301];
bool vis[301][301][301];
ld dp(int c1,int c2,int c3){
    if(c1<0||c2<0||c3<0)return 0;
    if(c1==0&&c2==0&&c3==0)return 0;
    ld &res=mem[c1][c2][c3];
    if(vis[c1][c2][c3])return res;
    vis[c1][c2][c3]=1;
    int c0=n-c1-c2-c3;
    ld n=::n;
    res=(c1/n*(1+dp(c1-1,c2,c3))+c2/n*(1+dp(c1+1,c2-1,c3))+c3/n*(1+dp(c1,c2+1,c3-1))+c0/n)/(1-c0/n);
    return res;
}

signed main(){
    cout<<fixed<<setprecision(10);
    cin>>n;
    ll c[4]={0,0,0,0};
    for(int i=1;i<=n;i++){cin>>a[i];c[a[i]]++;}
    cout<<dp(c[1],c[2],c[3]);
}

8.DP bitmask

here a bitmask is chosen to identify if an element is used or not , we may use this in a lot of ways , i remember using a bitmask of $$$3^n$$$ or even $$$4^n$$$ but let's focus now on $$$2^n$$$

let's solve this problem Matching.

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#define ld long double
const int N=100010,M=1e9+7;
ll mem[21][1<<21];
int vis[21][1<<21];
ll n;
bool comp[21][21];
ll dp(int i,int m){
    if(i==n)return 1;
    if(vis[i][m])return mem[i][m];
    vis[i][m]=1;
    ll &res=mem[i][m];
    for(int j=0;j<n;j++){
        if((m>>j)&1)continue;
        if(!comp[i][j])continue;
        res+=dp(i+1,m|(1<<j));
    }
    res%=M;
    return res;
}
signed main(){
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)cin>>comp[i][j];
    }
    cout<<dp(0,0);

}

what is the time complexity of this code?

9.DP on tree

the most annoying kind especially with re rooting , lets focus on the main idea.

in this kind of dp you must chose a root and calculate the result of each node depending on its children.

like in the Independent Set problem.

the state of the dp is $$$dp[node][color]$$$ so if the current color is black you consider the answer of $$$dp[child][white]$$$ , otherwise you consider both $$$dp[child][white]$$$ and $$$dp[child][black]$$$

note that we must multiply the childrens answer (not add)

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#define ld long double
#define pb push_back
const int N=100010,M=1e9+7;
ll n;
vector<int> adj[N];
bool vis[N][2];
ll mem[N][2];
ll dp(int i,int d,int c){
    if(vis[i][c])return mem[i][c];
    vis[i][c]=1;
    ll &res=mem[i][c];
    res=1;
    int cn=0;
    for(int j:adj[i]){
        if(j==d)continue;
        cn++;
        if(c==0){//it is white
            res*=(dp(j,i,1)+dp(j,i,0));
        }else{
            res*=dp(j,i,0);
        }
        res%=M;
    }
    return res;
}
signed main(){
    cin>>n;
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    cout<<(dp(1,1,0)+dp(1,1,1))%M;
}

10.DP with segment tree

this kind of DP is almost always deduced as we only need to know segment trees so solve this.

some times we only need to find minimum or maximum in range to solve them .

a good example would be Flowers

in this problem we must chose an increasing sub sequence of heights such that the sum of values as maximum

we can solve it for each index from $$$1$$$ to $$$n$$$ get the maximum answer among all heights that are less than $$$h(i)$$$ and add the value of the current flower to it and then update this value in the segment tree.

the solution is left to the reader :).

11. DP with matrices

if you do know matrices you really should not be reading this as all matrices problems are DP in fact, but you might have fun solving Walk

Note that i might make a tutorial about matrices some day! stay tuned :).

12.digit DP

this is one of the most annoying because if you made a mistake debugging is impossible.

problems of digit DP give you two numbers a,b such that their values are really huge (up to $$$10^{100000}$$$) and ask you to count how many numbers between them satisfies something.

in the problem Digit Sum.

this is a not really easy problem , and the state is more annoying

if(we are sure we are greater than a)L=0;
else
L=a[i]-'0'
if(we are sure we are less than b)R=9;
else R=b[i]-'0';

so our solution is:

#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#define ld long double
#define pb push_back
const int N=10010,M=1e9+7;
string a,b;
ll D;
ll mem[N][2][2][100];
int vis[N][2][2][100];
ll dp(int i,int bl,int br,int md){
    if(i==a.size())return md==0;
    if(vis[i][bl][br][md])return mem[i][bl][br][md];
    vis[i][bl][br][md]=1;
    ll &res=mem[i][bl][br][md];
    int L=a[i]-'0',R=b[i]-'0';
    if(bl)L=0;
    if(br)R=9;
    for(int j=L;j<=R;j++){
        res+=dp(i+1,bl|(j>L),br|(j<R),(md+j)%D);
    }
    res%=M;
    return res;
}

signed main(){
    cin>>b;
    a=string(b.size()-1,'0')+"1";
    cin>>D;
    cout<<dp(0,0,0,0);
}

and i think that's it as much as i would like to solve more , but i think i will leave it to you to view more and more dp problems , thank you for reading :).

i have just read a problem and was debugging , then i returned to the original statement to see it was no where to be found

this happened twice today

the first time it was like this:

i enter a gym to solve the following problem

i saw the statement and submitted , but when i returned the statement just disappeared

and the only thing to be found is a 404 not found link to download the whole pdf.

the second time it happened on this problem

and when i returned to the statement there were none!

MikeMirzayanov

could you please look upon this bug.

thank you!

this blog is an animated explanation of two pointers method

as two pointers is not really considered an algorithm this blog will only talk about famous problems and how they are handled.

this blog is not supposed to be hard it is targeted for under 1400 rating

this blog was made to summarize HCPC-2025 training for two pointers at Homs university / Syria.

overview

1. check if an array is sub sequence of another array

2. check if an array is sub array of another array

3. number of less or equal

4. merge two sorted arrays

5. number of sub arrays with sum less than or equal $$$X$$$

6. number of sub arrays with number of distinct elements less than or equal $$$X$$$

lets start:

1. check if an array is sub sequence of another array

checking that is relatively easy (easier than checking is sub array)

name the arrays $$$a$$$,$$$b$$$ we need to check if $$$a$$$ is sub sequence of $$$b$$$ keep two pointers in $$$a$$$ and $$$b$$$ pointing to the first element

keep increasing $$$b$$$'s pointer and then for each matching increase $$$a$$$'s pointer

if(a[i]==b[j]){
    i++;
}
j++;

2. check if an array is sub array of another array

given arrays $$$a(n)$$$ and $$$b(m)$$$ check if $$$a$$$ is sub array of $$$b$$$

here we could use two pointers $$$l$$$ and $$$r$$$ pointing to positions in $$$b$$$

first $$$l=1,r=0$$$

increase r by 1

and while the sub array $$$b[l:r]$$$ is not a prefix of $$$a$$$ keep increasing $$$l$$$

the brute force implementation is $$$O(m*n)$$$ but $$$kmp$$$ algorithm improves this to $$$O(n+m)$$$

the idea of $$$kmp$$$ is :

instead of increasing $$$l$$$ one by one

just for each prefix of $$$a$$$ store the longest prefix that is also a suffix of that prefix

and by knowing this info we could know how much exactly to increase $$$l$$$ and we do not need to check if it is a prefix anymore

$$$kmp$$$ is out of topic for now

3. number of less or equal

given two sorted arrays $$$a(n)$$$ and $$$b(m)$$$

for each element in $$$a$$$ count how many elements in $$$b$$$ that are less than or equal it

the idea is two keep a pointer $$$i=0$$$ in $$$a$$$ and $$$j=0$$$ in b

increase $$$i$$$ and while $$$j+1 \lt =m$$$ and $$$b(j+1) \lt =a(i)$$$ increase $$$j$$$

the answer for the element $$$a(i)$$$ is $$$j$$$ now

the idea is that we do not reset $$$j$$$ at each $$$i$$$ because the arrays are sorted

this means if $$$a(i) \gt =b(j)$$$ then $$$a(i+1) \gt =b(j)$$$

time complexity $$$O(n+m)$$$

4. merge two sorted arrays

given two sorted arrays $$$a(n)$$$ and $$$b(m)$$$

keep two pointers referring to the beginning of each array $$$i=1$$$ $$$j=1$$$

if $$$i \lt =n$$$ and $$$j \lt =m$$$ then append the smallest element to the resulting array and increase the pointer pointing to it

else append the elements remaining in one of them

time complexity $$$O(n+m)$$$

5. number of sub arrays with sum less than or equal $$$X$$$

given the array $$$a(n)$$$ we use two pointers $$$l=1,r=0$$$ and keep track of the $$$sum$$$

while $$$l \lt =n$$$

we add the element $$$a(r+1)$$$ if $$$sum+a(r+1) \lt =X$$$ and $$$r+1 \lt =n$$$

now the answer for $$$l$$$ is the number of sub arrays starting at $$$l$$$ which is $$$r-l+1$$$

and then subtract $$$a(l)$$$ from the sum (if $$$l \lt =r$$$) and increase $$$l$$$

the final answer is the sum of answers at each index

6. number of sub arrays with number of distinct elements less than or equal $$$X$$$

the same idea of the previous one

but we increase $$$r$$$ only if the number of distinct elements after inserting $$$a(r+1)$$$ does not exceed X

we can use std::map for this

how to count number of sub arrays with number of distinct elements strictly greater than $$$X$$$ ?

just subtract the answer of the previous problem from $$$n(n+1)/2$$$

problem solving

CF-79C

CSES-1660

CSES-1663

CF-1305B

CF-EDU

this blog will talk about prefix sums in general , how to use them , nice tricks , etc ...

this blog was made to summarize HCPC-2025 training for prefix sums at Homs university / Syria.

overview

1. what is prefix sum?

2. get range sum in $$$O(1)$$$

3. find number of sub arrays with sum equal to $$$x$$$ (map trick)

4. even more prefix sums

lets start:

1. what is prefix sum?

prefix sum of an array a of size $$$n$$$ is another array of size $$$n+1$$$ as follows:

        a(1)       a(2)           a(3)                 ...  a(n)
p(0)=0  p(1)=a(1)  p(2)=a(1)+a(2) p(3)=a(1)+a(2)+a(3)  ...  p(n)=a(1)+a(2)+...+a(n)

so in general $$$p(i)$$$ contains the sum of all elements up to $$$i$$$

and we introduce another element at the front representing the empty prefix

we can build prefix sum array in simple one line of code

for(int i=1;i<=n;i++)p[i]=p[i-1]+a[i];

this is the only info we care about (for now).

2.get range sum in $$$O(1)$$$

as we want the sum in range $$$[L,R]$$$

we realize that it is the same as $$$p(R)-p(L-1)$$$

a(L)+a(L+1)+...+a(R)=(a(1)+a(2)+...+a(L-1)+a(L)...+a(R))-(a(1)+a(2)+...+a(L-1)) = p(R)-p(L-1)

3. find the number of sub arrays with sum equal to $$$x$$$

given the array $$$a$$$ of size $$$n$$$

every sub array sum is represented by two prefix sums $$$p(L-1),p(R)$$$

first we initialize a map

map<int,int> cnt;

and loop through the array

lets say we are considering index $$$i$$$

at this point every prefix sum $$$p(j)$$$ such that $$$j \lt i$$$ is considered in the map

it is necessary to consider the empty prefix at first

cnt[0]=1;

and then at each index $$$i$$$

we do *something to get all sub arrays ending at index $$$i$$$ and have the sum equal to $$$x$$$ count and add it to the final answer

and then do

cnt[p[i]]++;

what to *do each time?

well we want the following equation $$$ p(i)-V=x $$$ when V is the value that we are searching

then $$$V=p(i)-x$$$

so we simply add $$$cnt[p[i]-x]$$$ to the final answer each time

note that $$$V=p(L-1)$$$ that's why we considered the empty prefix at the first place

there is a problem at CSES mentioning this trick

4. even more prefix sums

here i will mention other prefix stuff that might be useful to use later,

1.prefix xor

we can create an array containing the xor of each prefix, this way we can get the xor of any range

for(int i=1;i<=n;i++)p[i]=p[i-1]^a[i];
//xor of a range [L,R] is p[R]^p[L-1]

this is possible because

X^X=0 , A^B=B^A , X^0=X

2.prefix $$$mul$$$,$$$and$$$ , $$$or$$$ , $$$max$$$ , $$$min$$$ , $$$gcd$$$ and rarely $$$lcm$$$

these queries are sadly not usual to get in a range as we will need advanced data structures (aka sparse table) to get them in $$$O(1)$$$ (or $$$log(n)$$$ in case of gcd,lcm)

but you can get them in $$$log(n)$$$ complexity by using segment trees (out of topic but worth mentioning)

if we want $$$mul$$$ in range we wouldd need to make sure a lot of things are satisfied , like there should not be zero (as it will make all prefixes ahead zeros and we cant cancel them),and overflow cannot happen (which could mean a lot of things), in our case we will focus on $$$mul$$$ in range with $$$mod$$$ so we can get inverse mod in $$$O(log(n))$$$,or even $$$O(1)$$$ if the mod is small enough

it is also important to mention that we can get $$$(and,or)$$$ queries in range using simple prefix sum

by applying prefix sum on each bit as follows:

for(int j=0;j<30;j++){
    for(int i=1;i<=n;i++){
        p[j][i]=p[j][i-1]+((a[i]>>j)&1);
    }
}

and then we can get $$$or$$$ or $$$and$$$ queries in a range $$$[L,R]$$$ as follows:

int AND(int L,int R){
    int res=0;
    for(int j=0;j<30;j++){
        if(p[j][R]-p[j][L-1]==R-L+1)res+=1<<j;
    }
    return res;
}

int OR(int L,int R){
    int res=0;
    for(int j=0;j<30;j++){
        if(p[j][R]-p[j][L-1]>0)res+=1<<j;
    }
    return res;
}

but in certain problems it is enough to get them in a prefix (or a suffix maybe?)

3. 2D prefix sum

the idea is we want to get sum in a rectangle in $$$O(1)$$$

given the 2D array $$$a$$$ of $$$n$$$ rows and $$$m$$$ columns

   a(1,1) a(1,2)  ...  a(1,m)
   a(2,1) a(2,2)  ...  a(2,m)
   ...
   a(n,1) a(n,2)  ...  a(n,m)

we do a prefix sum on each row of $$$a$$$ first so that

p(i,j)=a(i,1)+a(i,2)+...+a(i,j)

and then we do another prefix sum on columns of $$$p$$$ so that

s(i,j)=p(1,j)+p(2,j)+...+p(i,j)

actually we don't need two more arrays for that, we can simply apply these operations on the same array twice, or one more array just to keep the original array.

the code is as follows:

for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)p[i][j]=a[i][j]+p[i][j-1];

for(int j=1;j<=m;j++)
for(int i=1;i<=n;i++)p[i][j]+=p[i-1][j];

we can get sum of elements in a rectangle with upper left corner at $$$(i,j)$$$ and with $$$x$$$ rows and $$$y$$$ columns like this

p[i+x-1][j+y-1]-p[i+x-1][j-1]-p[i-1][j+y-1]+p[i-1][j-1]

using inclusion exclusion principle (which is out of topic right now)

but i can explain why this is true

let the array $$$f$$$ represent how may times we added an element from the array $$$a$$$

first each $$$f(i,j)=0$$$

i will add each component to see how the frequency of elements change

notice that adding $$$p(i,j)$$$ represents increasing the value of $$$f(i1,j1)$$$ $$$i1 \lt =i&&j1 \lt =j$$$ by one

i=2,j=2,x=4,y=3
             +p[i+x-1][j+y-1]    -p[i+x-1][j-1]     -p[i-1][j+y-1]   +p[i-1][j-1]
  0 0 0 0 0  1 1 1 1 0           0 1 1 1 0          -1 0 0 0 0        0 0 0 0 0
  0 0 0 0 0  1 1 1 1 0           0 1 1 1 0           0 1 1 1 0        0 1 1 1 0
  0 0 0 0 0  1 1 1 1 0           0 1 1 1 0           0 1 1 1 0        0 1 1 1 0
  0 0 0 0 0  1 1 1 1 0           0 1 1 1 0           0 1 1 1 0        0 1 1 1 0
  0 0 0 0 0  1 1 1 1 0           0 1 1 1 0           0 1 1 1 0        0 1 1 1 0

4.offline range addition

the idea is simple

given an array of zeros $$$a$$$

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

you can add $$$V$$$ to a range $$$[L,R]$$$ by adding $$$V$$$ to $$$a(L)$$$ and subtracting $$$V$$$ from $$$a(R+1)$$$

0 0 0 V 0 0 0 0 0 -V 0 0 0 0 0

and then applying prefix sum on the array

0 0 0 V V V V V V 0 0 0 0 0 0 0

well that is not useful when talking about one query , the thing is you can add multiple values to multiple ranges and then apply prefix sum , this is considered offline approach in multiple cases.

5. offline 2D range addition

adding V to rectangle with upper left corner at $$$(i,j)$$$ and with $$$x$$$ rows and $$$y$$$ columns

add V to both $$$(i,j)$$$ $$$(i+x,j+y)$$$

subtract V from both $$$(i+x,j)$$$ $$$(i,j+y)$$$

and then apply prefix sum 2D like we learned

i=2,j=2,x=2,y=3
   0 0 0 0 0    0 0 0 0 0     0 0 0 0 0
   0 0 0 0 0    0 V 0 0 -V    0 V V V 0
   0 0 0 0 0    0 0 0 0 0     0 V V V 0
   0 0 0 0 0    0 -V 0 0 V    0 0 0 0 0 
   0 0 0 0 0    0 0 0 0 0     0 0 0 0 0

you can actually extend this to 3D array (worth mentioning).

problem solving

CSES-1662

spoj-CSUMQ

CF-835C

CF-1398C

CF-1291D

AC-abc164D

CF-2072D

CF-1501B

CF-433B

CF-296C

CF-816B

CF-1722E

CF-1837D

CF-2074D

AC-abc398D

hello codeforces

yesterday i noticed that someone from my friends solved problem D in 8 minutes.

well this friend is known in our telegram training group to be a cheater.

i refused that fact cuz there is no direct proof.

while i was looking at his code i noticed that some code was copied and pasted 3 times in different functions doing nothing.

i knew that was not normal , so i needed a proof now.

so i decided to look at problem D solves and was suprised that so many solutions are alike in a way, but different only in variable names, and some of them were in a straight one line of code , but the same idea over and over.

you can check some examples

308151686 308117651 308160744 308153550 308165846 308152360 308142455 308171609 308166500 308167550 308158553 308146140 308144552 308158580 308144531 308170236 308171447 308138274 and best for last 308165802

you can notice the large similarity between them,,

most of them were submitted at the near end of the contest,

these acts are not acceptable in this community, so many coders leave CP because others are cheating and he is getting negative delta over and over while not cheating.

i would like to notice MikeMirzayanov to these acts.

update:

the same person cheated today

i invastigated more and found a code on a telegram group

further more

here is his submission 308347774

here is the code on the telegram group

D1?#include <bits/stdc++.h>
using namespace std;
 
int f(long long m, long long n, int B, const vector<int>& p) {
    if (m <= n) return p[(int)m];
    return (m & 1LL) ? B : B ^ f(m / 2, n, B, p);
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        long long l, r;
        int n;
        cin >> n >> l >> r;
        
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
 
        if (l <= n) {
            cout << a[(int)l] << "\n";
            continue;
        }
 
        vector<int> p(n + 1);
        p[0] = 0;
        for (int i = 1; i <= n; i++) {
            p[i] = p[i - 1] ^ a[i];
        }
 
        int fn = p[n];
        int B = (n & 1) ? fn : fn ^ p[n / 2];
        long long m = l / 2;
        
        cout << f(m, n, B, p) << "\n";
    }
    
    return 0;
}

you don't need to be smart to know whats happening , these codes are being distributed through youtube and telegram channels, too bad we can't stop them , but at least cheaters don't deserve to get to expert by cheating and get away with it.

note: i will share the same codes that were shared for B C

i don't care about A if you cheat A just get a life man.

Hello codeforces

I am burnet out and can't actually have fun solving problems,

The first motivation for me was that there are plenty of fun problems out there to solve

Furthermore i feel like i am not learning much ,

I know i know you will say (solve more) so get better by time and whatever ,

I have no problem in that

But somehow i think it is more fun to focus on some topic and burn it to the ground,

Is there any good topic to learn that has a lot of new helpfull tricks?