I got bored with solving and wanted to do something which is related to cp and also very fun so i decided to write this tutorial.bare me for my bad English .

### how to solve grid problems

**trick**

here is my template to solve grid problems

```
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
string ds="RLDU";
int n,m;
bool possible(int x,int y){
//cout<<n<<" "<<m<<" "<<x<<" "<<y<<" possible"<<endl;
return (x<n&&x>=0&&y<m&&y>=0);
}
```

here we cand do just x+dx[i],y+dx[i] to move the four

directions and ds helps if we want to record path.

we can easily extend it to include four diagonals

## 1) counting rooms

**explanation**

For each unvisited '.' cell we have to make dfs(or bfs)

and keep on coloring the visited nodes.We keep track number

of dfs by count variable .our answer would be count.

**code**

void dfs(int x,int y){
if(!possible(x,y)||vis[x][y]!=-1||grid[x][y]==0)return ;
vis[x][y]=1;
int i;
fo(i,0,4){
int nx=x+dx[i],ny=y+dy[i];
dfs(nx,ny);
}
}
fo(i,0,n){
string s;
cin>>s;
fo(j,0,m){
if(s[j]=='.')grid[i][j]=1;
else grid[i][j]=0;
}
}
int ans=0;
fo(i,0,n){
fo(j,0,m){
if(grid[i][j]==1&&vis[i][j]==-1){
dfs(i,j);
ans++;
}
}
}
cout<<ans<<endl;

## 2) Labyrinth

**explanation**

We will store the coordinates of a and b ,now we start bfs

from a and try to reach b. We will keep a vector FRM and

DIR which will keep track of the cell from which we came here

and what is the direction of that move .At last if b is visited

we will go in reverse order by using FRM and try to recreate the path.

**code**

here a,b is coordinate of 'A' and c,d is coordinate of 'B'

queue<pii> q;
q.push({a,b});
vii from[n+1][m+1];
from[a][b].pb({0,0});
char ch[n+1][m+1];
while(!q.empty()){
pii p=q.front();
x=p.x;
y=p.y;
// cout<<from[x][y][0].x<<" "<<from[x][y][0].y<<" "<<x<<" "<<y<<" : ";
q.pop();
vis[x][y]=1;
if(grid[x][y]==3)break;
fo(i,0,4){
int nx=x+dx[i],ny=y+dy[i];
//cout<<x<<" "<<dx[i]<<","<<y<<" "<<dy[i]<<endl;
if(!possible(nx,ny))continue;
if(grid[nx][ny]==0||vis[nx][ny]!=-1)continue;
//cout<<"("<<nx<<","<<ny<<") ";
vis[nx][ny]=1;
q.push({nx,ny});
from[nx][ny].pb(p);
ch[nx][ny]=ds[i];
}
//cout<<endl;
}
if(vis[c][d]==-1){
cout<<"NO"<<endl;
return 0;
}
else{
cout<<"YES"<<endl;
pii p={c,d};
while(p.x!=a||p.y!=b){
s+=ch[p.x][p.y];
p=from[p.x][p.y][0];
}
reverse(all(s));
cout<<s.size()<<endl;
cout<<s<<endl;
}

## 3) Building Roads

**explanation**

The problem is basically connecting the disconnected components.

do dfs on all unvisited nodes and save one node from each

connected component as a head node.Then if there are k connected

components connect their head node via k-1 edges between heads.

**code**

vi v;
fo(i,1,n+1){
if(vis[i]==-1){
v.pb(i);
dfs(i);
}
}
cout<<v.size()-1<<endl;
fo(i,1,v.size()){
cout<<v[i]<<" "<<v[i]-1<<endl;
}

## 4) Message Route

**explanation**

This question is similar to Labyrinth ,start a bfs from 1 and

also keep vector FRM to know from where the current node is reached

and at last if n is visited go in reverse order using FRM to recreate path.

**code**

queue<int> q;
q.push(1);
while(!q.empty()){
int p=q.front();
q.pop();
vis[p]=1;
if(p==n)break;
for(int aa:graph[p]){
if(vis[aa]==-1){
from[aa]=p;
vis[aa]=1;
q.push(aa);
}
}
}
vi v;
if(vis[n]==-1){
cout<<"IMPOSSIBLE"<<endl;
}
else{
v.pb(n);
a=n;
while(a!=1){
a=from[a];
v.pb(a);
}
cout<<v.size()<<endl;
rfo(i,v.size()-1,0){
cout<<v[i]<<" ";
}
}

## 5) Building teams

**explanation**

The question is about coloring the bipartite graphs more about it.

we try to color all vertex greedily if vertex is not visited color

it white and run dfs . now color all its uncolored neighbors of white vertex

black and vice versa and run dfs on them.

at last check that each edge has ends with different colors.

**code**

void dfs(int p,int c){
if(vis[p]!=-1){
return ;
}
vis[p]=1;
color[p]=c;
for(int aa:graph[p]){
if(vis[aa]==-1)dfs(aa,1-c);
}
}
bool ok=true;
_init(vis);
fo(i,1,n){
if(vis[i]==-1){
dfs(i,0);
}
}
fo(i,0,m){
if(color[edges[i].x]==color[edges[i].y]){
ok=false;
break;
}
}
if(!ok){
cout<<"IMPOSSIBLE"<<endl;
return 0;
}
fo(i,1,n+1){
cout<<color[i]+1<<" ";
}

## 6) Round Trip

**explanation**

Question is about finding cycle.We will run a dfs an keep vector VIS

to keep track of the nodes in the recusion stack.If we are at node p

we will run dfs no all of its childs if any of the child is in recursion

stack we will add this vertex to an array CYCLE . Now we will also keep

track of where to end cycle by TILL . If current is equal to TILL return from all dfs's else return TILL

**code**

int vis[N],from[N],color[N],till;
vi v;
int dfs(int p,int c){
//cout<<p<<" <<<"<<endl;
if(vis[p]!=-1){
till=p;
v.pb(p);
return 1;
}
vis[p]=1;
for(int aa:graph[p]){
if(aa==c)continue;
int x=dfs(aa,p);
//cout<<p<<" "<<aa<<" "<<x<<endl;
if(x==1){
v.pb(p);
if(till==p){
return 2;
}
else{
return 1;
}
}
else if(x==2)return 2;
}
vis[p]=2;
return 0;
}

## 7) Monsters

**explanation**

You have to do a multi source bfs from all the monsters . You keep track

of minimum step a monster can reach a cell in the GRID matrix

. Then you apply bfs from source and keep track of steps (initially 0)

and go to only those nodes where steps are less than grid[x][y] means

you only go to those cells where you can reach before any monster

has reached there. You can recreate path using FRM and DIR matrix as I have done in Labyrinth .

**code**

const int N=1001;
int grid[N][N];
string maze[N];
int vis[N][N];
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int i,j,x;
cin>>n>>m;
string s;
vii mon;
int ax,ay;
fo(i,0,n){
cin>>s;
fo(j,0,m){
maze[i]=s;
if(s[j]=='A'){
ax=i;
ay=j;
}
if(s[j]=='M'){
mon.pb({i,j});
}
}
}
queue<pair<int,pii>> q;
_init(vis);
fo(i,0,mon.size()){
q.push({0,{mon[i].x,mon[i].y}});
vis[mon[i].x][mon[i].y]=1;
}
_init(grid);
while(q.size()>0){
pii p=q.front().y;
int lvl=q.front().x;
q.pop();
grid[p.x][p.y]=lvl;
fo(i,0,4){
int nx=p.x+dx[i],ny=p.y+dy[i];
if(!possible(nx,ny))continue;
if(maze[nx][ny]=='#')continue;
if(vis[nx][ny]!=-1)continue;
q.push({lvl+1,{nx,ny}});
vis[nx][ny]=1;
}
}
/*
fo(i,0,n){
fo(j,0,m){
cout<<grid[i][j]<<" ";
}
cout<<endl;
}
cout.flush();
*/
_init(vis);
pair<int,int> from[n+1][m+1];
char dir[n+1][m+1];
s="RLDU";
q.push({0,{ax,ay}});
pii to={-1,-1};
bool mm=mon.size()>0;
while(q.size()>0){
pii p=q.front().y;
int lvl=q.front().x;
q.pop();
if(grid[p.x][p.y]!=-1&&lvl>=grid[p.x][p.y]){
//cout<<p.x<<" "<<p.y<<" "<<lvl<<" "<<grid[p.x][p.y]<<endl;
continue;
}
//cout<<p.x<<" "<<p.y<<":";
if(p.x==0||p.x==n-1||p.y==0||p.y==m-1){
to={p.x,p.y};
break;
}
fo(i,0,4){
int nx=p.x+dx[i],ny=p.y+dy[i];
if(!possible(nx,ny))continue;
if(maze[nx][ny]=='#')continue;
if(vis[nx][ny]!=-1)continue;
if(grid[nx][ny]!=-1&&grid[nx][ny]<=lvl)continue;
from[nx][ny]=p;
q.push({lvl+1,{nx,ny}});
vis[nx][ny]=1;
dir[nx][ny]=s[i];
//cout<<"("<<nx<<","<<ny<<") ";
if(nx==0||nx==n-1||ny==0||ny==m-1){
//cout<<lvl<<" "<<
to={nx,ny};
break;
}
}
if(to.x!=-1)break;
//cout<<endl;
}
// cout<<to.x<<" "<<to.y<<" "<<ax<<" "<<ay<<endl;
if(to.x==-1){
cout<<"NO"<<endl;
return 0;
}
cout<<"YES"<<endl;
s="";
while(to.x!=ax||to.y!=ay){
s+=dir[to.x][to.y];
//cout<<to.x<<" "<<to.y
to=from[to.x][to.y];
}
reverse(all(s));
cout<<s.size()<<endl;
cout<<s<<endl;
return 0;
}

## 8) Shortest Routes I

**explanation**

The question ask you to implement simple dijsktra more about it

**code**

priority_queue<pii,vii,greater<pii>> q;
q.push({0,1});
_init(dis);
_init(vis);
dis[1]=0;
while(!q.empty()){
pii p=q.top();
q.pop();
int node=p.y,d=p.x;
if(vis[node]!=-1)continue;
vis[node]=1;
for(pii aa:graph[node]){
if(vis[aa.y]!=-1)continue;
if(dis[aa.y]==-1||dis[aa.y]>d+aa.x){
dis[aa.y]=d+aa.x;
q.push({d+aa.x,aa.y});
}
}
}
fo(i,1,n+1){
cout<<dis[i]<<" ";
}

## 9) Shortest Routes II

**explanation**

The question is about simple Floyd Warshall Algorithmmore about it

**code**

cin>>n>>m>>q;
fo(i,1,n+1){
fo(j,1,n+1){
mat[i][j]=inf;
}
mat[i][i]=0;
}
fo(i,0,m){
cin>>a>>b>>c;
mat[a][b]=min(mat[a][b],c);
mat[b][a]=min(mat[b][a],c);
}
int k;
fo(k,1,n+1){
fo(i,1,n+1){
fo(j,1,n+1){
mat[i][j]=min(mat[i][j],mat[i][k]+mat[k][j]);
}
}
}
fo(i,0,q){
cin>>a>>b;
cout<<((mat[a][b]>=inf)?-1:mat[a][b])<<"\n";
}

## 10) High scores

**explanation**

Let say we are at node k we have to find weather there is a positive cycle ending

at k and if there if a cycle whether there is a path like 1->k->n then ans is zero.

You can do this by runnig dfs for each node and see if there is cycle ending at

that node with positive sum.if there is no such cycle you have to find biggest

route from 1 to n. You can do this by using bellman ford complexity o(n*m)

**code**

const int N=2501;
vii graph[N];
int vis[N],dis[N],from1[N],to1[N],fromn[N],ton[N],cycle[N];
int n,m,r,has1,hasn;
int findc(int p){
vis[p]=1;
if(p==1){
has1=1;
}
if(p==n){
hasn=1;
}
for(pii aa:graph[p]){
if(aa.x==r){
dis[p]=max(dis[p],aa.y);
continue;
}
if(vis[aa.x]==1)continue;
if(vis[aa.x]==2){
dis[p]=max(dis[p],dis[aa.x]+aa.y);
}
else{
int x=findc(aa.x);
if(x!=-inf){
dis[p]=max(dis[p],x+aa.y);
}
}
}
vis[p]=2;
return dis[p];
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int i,j,x;
cin>>n>>m;
int a,b,c;
fo(i,0,m){
cin>>a>>b>>c;
graph[a].pb({b,c});
}
fo(i,1,n+1){
_init(vis);
_init(dis);
has1=0;
hasn=0;
r=i;
fo(j,0,n)dis[j+1]=-inf;
x=findc(i);
//cout<<x<<" "<<has1<<" "<<hasn<<endl;;
to1[i]=has1;
ton[i]=hasn;
cycle[i]=x>0;
if(i==1){
fo(j,0,n)from1[j+1]=vis[j+1];
}
if(i==n){
fo(j,0,n)fromn[j+1]=vis[j+1];
}
}
fo(i,1,n+1){
if(cycle[i]){
if(from1[i]>0&&ton[i]>0){
cout<<-1;
return 0;
}
else if(fromn[i]>0&&to1[i]>0){
cout<<-1;
return 0;
}
}
}
//cout<<endl;
fo(i,0,n)dis[i+1]=-inf;
dis[1]=0;
fo(i,1,n+1){
fo(j,1,n+1){
if(dis[j]==-inf)continue;
for(pii aa:graph[j]){
dis[aa.x]=max(dis[aa.x],dis[j]+aa.y);
}
}
}
cout<<dis[n]<<endl;
return 0;
}

## 11) Flight Discounts

**explanation**

Find minimum distance from 1 till starting of edge and minimum distance

from end of node till n and add weight/2. may be the concept involved here

is called meet in the middle not sure though.create two graphs original and reverse.

from original graph start dijkstra from 1 and store result in FRM1 and from

reverse graph start dijkstra from n and store result in TON .then iterate

through all edges and ans is minimum of (FRM1[edge[i].start + edge.weight/2 + TON[edge.end])

**code**

_init(vis);
_init(dis);
dis[0]=0;
priority_queue<pii,vii,greater<pii>> q;
q.push({0,0});
while(!q.empty()){
pii p=q.top();
q.pop();
if(vis[p.y]!=-1)continue;
vis[p.y]=1;
for(pii aa:graph[p.y]){
if(vis[aa.x]!=-1)continue;
if(dis[aa.x]==-1||dis[aa.x]>p.x+aa.y){
q.push({p.x+aa.y,aa.x});
dis[aa.x]=p.x+aa.y;
}
}
}
vi f1;
fo(i,0,n){
f1.pb(dis[i]);
}
_init(vis);
_init(dis);
dis[n-1]=0;
//pl();
q.push({0,n-1});
while(!q.empty()){
pii p=q.top();
q.pop();
if(vis[p.y]!=-1)continue;
vis[p.y]=1;
//cout<<p.x<<" "<<p.y<<endl;
for(pii aa:rev[p.y]){
if(vis[aa.x]!=-1)continue;
if(dis[aa.x]==-1||dis[aa.x]>p.x+aa.y){
q.push({p.x+aa.y,aa.x});
dis[aa.x]=p.x+aa.y;
}
}
}
// pl();
vi fn;
fo(i,0,n){
fn.pb(dis[i]);
}
//cout<<f1<<endl;
//cout<<fn<<endl;
int ans=f1[n-1];
for(piii bb:edges){
pii aa=bb.y;
if(f1[aa.x]!=-1&&fn[aa.y]!=-1){
ans=min(ans,f1[aa.x]+fn[aa.y]+bb.x/2);
}
}
cout<<ans<<endl;

## 12)Finding Cycles

**explanation**

This problem can be solved using bellman ford algorithm .

the key idea is relax each edge n(number of node) times if there is no negative cycle

then because you should have got the final answer in n-1 iterations itself

which means if there is a negative cycle only then there will be some changes in nth iteration

so this way you can detect the cycle and you can regenerate if using FRM array

in depht explanation

**code**

cin>>n>>m;
int a,b,c;
fo(i,0,m){
cin>>a>>b>>c;
graph[a].pb({b,c});
}
fo(i,1,n+1)dis[i]=inf;
dis[1]=0;
vi baap(n+1,-1);
fo(i,0,n+1){
till=-1;
fo(j,1,n+1){
for(pii p:graph[j]){
if(dis[p.x]>dis[j]+p.y){
dis[p.x]=dis[j]+p.y;
baap[p.x]=j;
till=p.x;
}
}
}
}
if(till==-1){
cout<<"NO"<<endl;
return 0;
}
cout<<"YES"<<endl;
fo(i,0,n){
till=baap[till];
}
vi cyc;
for(int aa=till;;aa=baap[aa]){
cyc.pb(aa);
if(cyc.size()>1&&aa==till){
break;
}
}
reverse(all(cyc));
cout<<cyc<<endl;

## 13) Flight Routes

**explanation**

Important observaion here is k is very small (k<10) and

if you want to find k routes each vertex is visited atmax k times in k routes.

so it is someting like dijkstra you keep CNT array were you keep count of each node

and take a min heap(set or priority queue in cpp) and insert 1st node with cost 0

in it. Now let say p is smallest node in heap. increase count of p in CNT array

if it is more than k then continue to next iteration.if p is last node add cost

to ANS array.now iterate through all edges of p and add child with cost p.cost + edge weight

in the heap.

now just print ans array complexity o(mk).more about it

**code**

const int N=1e5+5;
vii graph[N];
int dis[N],vis[N];
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int i,j,x,n,m,k;
cin>>n>>m>>k;
int a,b,c;
fo(i,0,m){
cin>>a>>b>>c;a--;b--;
graph[a].pb({b,c});
}
priority_queue<pii,vii,greater<pii>> q;
_init(dis);
_init(vis);
dis[0]=0;
q.push({0,0});
while(!q.empty()){
pii p=q.top();
q.pop();
if(vis[p.y]==1)continue;
vis[p.y]=1;
for(auto aa:graph[p.y]){
if(vis[aa.x]==-1){
if(dis[aa.x]==-1||dis[aa.x]>aa.y+p.x){
dis[aa.x]=aa.y+p.x;
q.push({dis[aa.x],aa.x});
}
}
}
}
/* fo(i,0,n){
cout<<dis[i]<<" ";
}*/
int count[n+1];
_init0(count);
vi v;
q.push({0,0});
int cnt=k;
while(!q.empty()&&count[n-1]<k){
pii p=q.top();
q.pop();
count[p.y]++;
if(p.y==n-1){
v.pb(p.x);
}
if(count[p.y]<=k){
for(auto aa:graph[p.y]){
q.push({p.x+aa.y,aa.x});
}
}
}
sort(all(v));
cout<<v<<endl;
return 0;
}

## 14) round trip 2

**explanation**

The quesiton is about finding cycle in a directed graph. there are 3 types of vertex in dfs

color 1: white = the vertex is completely unvisited.

color 2: grey = the vertex whose some but not all child are visited.

color 3: black = the vertex whose all the child are visited .

Now there will be a cycle only when the vertex you are currently on has a grey child.

So how will trace the cycle .we can do it by storing the end grey vertex in a variable.

and add all the vertex when going back in the recursion until that grey vertex is again visited.

more about it

detecting cycle in directed graph(video)

detecting cycle in directed graph gfg

**code**

int dfs(int p){
if(vis[p]!=-1)return 0;
vis[p]=1;
int x;
for(int aa:graph[p]){
if(vis[aa]==-1){
x=dfs(aa);
if(x!=0){
if(x==2)return x;
cycle.pb(p);
if(p==till)return 2;
else return 1;
}
}
else if(vis[aa]==1){
cycle.pb(aa);
cycle.pb(p);
till=aa;
return 1;
}
}
vis[p]=2;
return 0;
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int i,j,x,n,m;
cin>>n>>m;
int a,b;
fo(i,0,m){
cin>>a>>b;
graph[a].pb(b);
}
_init(vis);
fo(i,1,n+1){
if(vis[i]==-1){
dfs(i);
}
if(cycle.size()>0)break;
}
if(cycle.size()==0){
cout<<"IMPOSSIBLE"<<endl;
}
else{
cout<<cycle.size()<<endl;
reverse(all(cycle));
cout<<cycle<<endl;
}
return 0;
}

## 15) Course Schedule

**explanation**

the problem is about simple topological sort.

more about it

topsort video

topsort tutorial cp algo

**code**

const int N=1e5+5;
vi graph[N],top;
int vis[N],till;
bool cycle;
void dfs(int p){
if(vis[p]!=-1)return ;
vis[p]=1;
int x;
for(int aa:graph[p]){
if(vis[aa]==1){
cycle=true;
}
else if(vis[aa]==-1){
dfs(aa);
}
if(cycle)return;
}
vis[p]=2;
top.pb(p);
return ;
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int i,j,x,n,m;
cin>>n>>m;
int a,b;
fo(i,0,m){
cin>>a>>b;
graph[a].pb(b);
}
cycle=0;
_init(vis);
fo(i,1,n+1){
if(vis[i]==-1){
dfs(i);
}
if(cycle)break;
}
if(cycle){
cout<<"IMPOSSIBLE"<<endl;
}
else{
reverse(all(top));
cout<<top<<endl;
}
return 0;
}

## 16) Longest flight routes

**Explanation**

I solved this problem using dp. Here there is no cycle so there could not be an infinite path.

What we can do if there is a path like A->B . we find maxpath

for a by just adding 1 to max path of b. `dp[a]=max(dp[a],dp[b]+1)`

**code**

int dfs(int p){
vis[p]=1;
int x;
if(p==n){wt[p]=0;vis[p]=2;return 0;}
for(int aa:graph[p]){
if(vis[aa]==-1){
dfs(aa);
}
if(wt[aa]==-1)continue;
if(wt[aa]+1>wt[p]){
//cout<<p<<" "<<aa<<" "<<wt[aa]<<" "<<wt[p]<<" ";
wt[p]=wt[aa]+1;
to[p]=aa;
// cout<<wt[p]<<endl;
}
}
vis[p]=2;
return wt[p];
}

## 17) Game Routes

**Explanation**

this question is about dp on graph.the number of ways

by which a node A can reach N is equal to sum of ways of its childs.

`for(int child:graph[a])dp[a]=(dp[a]+dp[child])%MOD`

**code**

int dfs(int p){
vis[p]=1;
int x;
if(p==n){wt[p]=1;vis[p]=2;return 0;}
for(int aa:graph[p]){
if(vis[aa]==-1){
dfs(aa);
}
wt[p]+=wt[aa];
wt[p]%=MOD;
}
vis[p]=2;
return wt[p];
}

## 18) Investigation

**Explanation**

The question is basically dijkstra + dp.

You have to run dijkstra and keep track of minimum distance from 1 of all vertex.

If a child has minimum distance = current dis+ edge.weight you just updated the dp.

If a child has min dis>current dis+ edge.weight you reset everyting in dp.

**code**

signed main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int i,j,x;
cin>>n>>m;
int a,b,c;
fo(i,0,m){
cin>>a>>b>>c;
graph[a].pb({b,c});
}
_init(vis);
_init(min_price);
_init0(routes);
_init(min_flight);
_init(max_flight);
_init(can_reachn);
min_price[1]=0;
routes[1]=1;
min_flight[1]=0;
max_flight[1]=0;
priority_queue<pii,vii,greater<pii>> q;
q.push({0,1});
while(!q.empty()){
x=q.top().y;
q.pop();
if(vis[x]!=-1)continue;
vis[x]=1;
for(pii aa:graph[x]){
if(vis[aa.x]==1)continue;
if(min_price[aa.x]==-1||min_price[aa.x]>min_price[x]+aa.y){
min_price[aa.x]=min_price[x]+aa.y;
routes[aa.x]=routes[x];
min_flight[aa.x]=min_flight[x]+1;
max_flight[aa.x]=max_flight[x]+1;
q.push({min_price[aa.x],aa.x});
}
else if(min_price[aa.x]==min_price[x]+aa.y){
routes[aa.x]+=routes[x];
routes[aa.x]%=MOD;
min_flight[aa.x]=min(min_flight[aa.x],min_flight[x]+1);
max_flight[aa.x]=max(max_flight[aa.x],max_flight[x]+1);
q.push({min_price[aa.x],aa.x});
}
}
}
cout<<min_price[n]<<" "<<routes[n]<<" "<<min_flight[n]<<" "<<max_flight[n]<<endl;
return 0;
}

## 19) Planet queries I

**explanation**

basically tunnel is directed edge and left end is parent and right end is first order child(its direct child).

moving k steps in tunnel means you have to go to kth order child .you can do this using binary lifting.

here is short explanation of binary lifting.

basically we keep tack of all the childs of a node which is at a distance which is power of 2.

if a graph is like this a->b->c->d->e

then first order child of a is b (1st child)

second order child of a is c (2nd child)

and third order child of a is e(4th child)

so by doing this we can find the kth child in log n time .

more about it.

binary lifting cp algo

binary lifting algo live

**code**

cin>>n>>q;
fo(i,1,n+1){
cin>>x;
dp[0][i]=x;
}
fo(i,1,LOGN){
fo(j,1,n+1){
dp[i][j]=dp[i-1][dp[i-1][j]];
//cout<<dp[i-1][j]<<" ";
}
// cout<<endl;
}
fo(i,0,q){
int a,b;
cin>>a>>b;
rfo(j,30,0){
//cout<<(b&(1ll<<j))<<" ";
if((b&(1ll<<j))>0){
a=dp[j][a];
}
}
cout<<a<<endl;
}

#### other useful links

**links**

Hope this is helpfull to you . I will try to add more as I solve furthure.

Auto comment: topic has been updated by arham_doshi (previous revision, new revision, compare).Problem links?

https://cses.fi/problemset/

First register to create an account then you will be able to submit your codes.

Thanks :)

Nice initiative.

Very nice and helpful.

Thanks arham_doshi

all hail ......editorialist arham_doshi

This may also help. https://github.com/ankitpriyarup/CSES_ProblemSet_Solution

thankyou so much sir

Hi, thanks for the editorials. I am unable to understand the problem $$$High$$$ $$$Scores$$$. It says we can use a tunnel several times, that means if there is an edge with

positive weightcan't we use it several times(infinite times i.e. $$$a$$$ -> $$$b$$$ then $$$b$$$ -> $$$a$$$ ... ) and our answer will be -1?and i think in the editorial you meant

`Bellman ford`

instead of`Floyd Warshall`

.Yes, we can use it hence you have to print -1 as said in the problem statement.

If that is the case why our answer is 5 for sample? We can use the edge with positive weight from 1 and use it infinite times and our answer will be -1. Sorry if I misunderstood you:(

All tunnels are one-way tunnels...means it's a directed graph.

Oops. Sorry my bad. :(

yeah may be i got confused sed between bellman ford and floyd warshal.talking about sample it is a directed edge so after going from a to b you canot go back. "

the tunnel starts at room a, ends at room b"Here is an additional trick for grid problems. Specifically for problems where the input is some kind of maze with

`#`

for "blocked" cells and`.`

for "free" cells. I like the approach of using the`dx`

and`dy`

arrays but the`possible`

function feels clunky to me in some problems.Instead I put a "frame" made out of

`#`

around the whole grid. That is: when the input isinstead I consider the input

It is really easy to implement. Initially fill the whole grid with

`#`

, then read the input.Nice one, i like it. I use possible at many places like when when solveing a dp probelm

Auto comment: topic has been updated by arham_doshi (previous revision, new revision, compare).Auto comment: topic has been updated by arham_doshi (previous revision, new revision, compare)...

I'm having trouble with Building Roads problem. For some reason, I am getting TLE for test cases 6-11, although my solution is similar in idea to ones that have been accepted. How can I change my code so I don't get TLE?

In case someone reads this, I had the same problem. I'm not experienced with C++ so I struggled to catch the problem. It turns out adj in dfs function is passed as copy, not by reference. Changing that to vector &adj, or just using global variables instead works, because you won't copy the adj vector every time you call dfs function

I'm currently making Video editorials for tree section of CSES.

Interested people can check : CSES (DP ON) TREE ALGORITHMS

I'm hoping to finish it in around a week, will be happy to know if people find it helpful :)

UPD : added first 5, do share suggestions if any.

Thank You so much, it will be very helpful.

Do share suggestions/feedback if any :)

This is really helpful.

Thank You arham_doshi !!

13) flight routes give TLE as its O(nmk)

Its o(m*k), i was writing there max(n, m)*k

I calculated the complexity. Shouldn't it be O(k(m+nlogn))?. It is still giving me TLE for the above algorithm.

Secondly, why did you run a classical djikstra before? you are not using the distance array in the algorithm.

i am finding all the possible paths . you can think it as bfs . it i optimised brute force where you can only take take vertex at max k time. i was solving all the question in line so in 2-3 ques i needed dijkstra so i just kept it there ignore it. dm me your code.

Auto comment: topic has been updated by arham_doshi (previous revision, new revision, compare).CAN SOMEONE PLEASE HELP ME???

for Investigation question above, i am doing exactly what the author does except for one thing:

he uses a visited array and if already visited, continues..

i do something like

i want to know constraint / testcase wise why this will give TLE. it was giving tle for 3 large testcases

the issue was resolved on introducing a boolean visited array

mycode = https://ideone.com/e6ZTWL (not needed tho)

https://cses.fi/paste/cfd81e7f5b4db001e2466/

what is wrong in this solution? CycleFinding?????

Not sure but may be possible that the distance you are initating with LLONG_MAX may get over fload when you do distance[i] + someting

can someone help me understanding this lines in Labyrinth problem?

what does

`from`

means? i was unable to googling it. is there any keyword? thank youIt is just 2d vector, i have declared it on 3rd line, it helps us in recreating the path.

what does FRM and DIR stand for? You mentioned it on the same Labyrinth problem. Thanks for this blog btw.

FRM stands for FROM means from which cell it has come to this cell, and DIR stands for directon means from previous cell in which directon do we move (right, left, up, down) to reach current cell. Both these auxiliary array help us in recreating path after wards.

got it thanks, i did a similar thing but i thought FRM or DIR was some advanced thing that ive never heard of

got it, thanks!

Thanks for the editorial!!

Really great job!

Just want to add that in the problem Monsters, after applying multi source bfs we can use dfs as well instead of bfs to find the path from 'A' to boundary, as we need not find the shortest path.

My ImplementationThanks dhruv, one more thing i noticed is that if you use dfs you don't need the auxiliary array to recreate path, nice one.

what is the time complexity if we run BFS on multiple monsters? For each monster we might take n.m time right?

then overall complexity will be too high?

no the time complexity will still be n*m , we will just start bfs with all monsers simalteniosly.

Because we visit at most every node once (or five times, once when we start and once for each direction, but it's still constant).

Hey RisingWizard arham_doshi Can you explain this line

if(d[i][j+1]>ans.size()+1)?IN THE FLIGHT ROUTES PROBLEM

if you want to find k routes each vertex is visited atmax k times in k routes.Can somebody explain me why it is so?How to solve Planet Queries II ?

Too much helpful. Thanks a lot.

In

HighscoresI dont understand how you detected positive cycle using dfs , can anyone please explain a bit more..We first find positive cycles using Bellman-Ford, and then we check if these cycles can be reached on a path from 1->n. We can do this by reversing the edges and running a dfs from node n, and running a normal dfs from node 1.

Can anyone help me out in the implementation of Dijkstra's Algo in python using heaps, I'm getting TLE in 2 test cases only

My codeThanks

I suggest you to use c++ or java as the test cases in cses are very tight.

arham_doshi I have a different approach for the problem "Flight Discount" But getting wrong answer on 3 TC can you help me please,I can't find any TC.

My Solution

Can someone help why this Java code gives TLE at test case #8 and how to optimize it?

Code

Auto comment: topic has been updated by arham_doshi (previous revision, new revision, compare).I'm trying to solve Shortest Routes II using Dijkstra but it is giving me TLE on 5 cases. I used same approach for Shortest Routes I and it got accepted but for 2nd one it's not. I'm also taking care of sub-optimal cases by not inserting the already processed nodes still it's giving me TLE. Could anyone suggest how to optimize the Djikstra approach. My solution.

Any help would be appreciated. Thank you.

Since actually we need to know all distances from each vertex to each other vertex a solution based on Floyd-Warshall works more efficient here.

While solving finding cycles using bellman ford, if I iterate over a vector<vector>edges, which is a list of edges, I get a TLE, but if I iterate over an adjacency list instead of that, it runs faster. Why is that?

Code with list of edges...

Code with adjacency list...

instead of

`for(auto e: edges)`

use reference.`for(auto &e: edges)`

Wow it worked!! But why is copying a small vector such an overhead I wonder? Thanks a lot though!

You are doing it n times

Can somebody help me understand why is my code https://cses.fi/paste/dfd9fc301c9be88b1f65d5/ giving TLE in one of the test cases of Labyrinth, I did it very similar to editorail.

After working on it for quite some time I found that instead of storing the answer in string , storing in stack passed that one test case which previously gave me TLE.

In shortest Routes 2 we have used Floyd warshall algorithm which has a time complexity of O(n3) but if we use Dijkstra algorithm for every node to find the shortest path between it and other nodes its time complexity will be O(n2*log(n)) but still Dijkstra algorithm gives TLE while Floyd warshall algorithm doesn't can someone please explain where I am doing wrong

no u are wrong about the time complexity of

dijkstrafor a node it is(V+E*log(V))where E is our no. of edges and V is no. of vertices or nodes so E in worst can be V^2 and applying for every node to find the shortest path between it and other nodes its time complexity will beO(V*E*log(V)+V*V)which in worst case can beV^3*log(V)Can't we solve flight discounts using dp? I tried this approach but my soln is giving WA for 3 test cases. Like dp[n][2], where the dp[s][c] is the shortest path to s from 1 using the discount c times.

Code## define int long long int

## define MAXN 100005

vector adj[MAXN]; int dp[MAXN][2]; int n, m, mx = pow(10, 17);

int dfs(int s, int c) { if (dp[s][c] == -1) { if (s == n) dp[s][c] = 0; else { dp[s][c] = mx; for (auto it : adj[s]) dp[s][c] = minm(dp[s][c], it.ss + dfs(it.ff, c));

}

signed main() { memset(dp, -1, sizeof(dp)); cin >> n >> m; int x, y, w; map<pii, int>mp;

}

Editorial for Road Reparation

Ques link

First check graph is connected or not. If it is not connected then answer is not possible.

If it is connected find minimum spanning tree. You can use prism algo for finding MST.

My code link

Editorial for Flight Route Check

Ques LinK

Run the dfs from any node and then check all nodes are visited or not. if any node is not visited, u will get the answer.

Also check is there any node is present in graph whose outdegree is zero. if yes then u can visited from this node to any node.

Else the answer is YES.

My Code Link

very useful

I tried solving

12. Finding Cyclesusing DFS (I know that Bellman–Ford exists, I just liked the idea of using prefix sums to track if a cycle is negative or not), but I keep getting TLE's in tests 7, 13 and 15 (the graph structure in those cases is something like a tree, I guess that's why this could be the case). Is this kind of problem solvable by DFS, or because it is a weighted directed graph (and I have to revisit the same node multiple times) the worst-case time complexity is worse than $$$O(n + m)$$$?My solution:https://cses.fi/paste/ec6f372ba706d70b619ffe/

For the problem

`High Scores`

there is a simpler solution that is easier to implement. You can just useBellman Fordto calculate the maximum distance from node1ton. Run the loopn — 1times ( for calculating maximum distances usingBellman Ford) and then scan the edges for one last time. If the distance to a nodeuseems to increase again, this indicatesuis part of a positive weight cycle ( sum of weights in the cycleuthat is part of >0).If that is the case, check if node

nis reachable fromuand print-1if it is.Link to my solution

I have an even simpler solution for High Scores: https://cses.fi/paste/ba556eee811dc61873945c/

We can just run Bellman-Ford one more time, and check if the last guy changes. Whenever we change a node, we decrease both distances by a large amount (so that the updates are fast).

Planet Queries I

An alternative to binary lifting. A natural solution is to exploit the properties of the graph. Each node has only 1 outgoing edge. Similarly, if there's a cycle then there's no outgoing edge, nodes can only teleport into the cycle. For nodes that aren't self loops, they are in a cycle or they will reach it after a certain number of jumps.

We find the strongly connected components in the graph. $$$O(n + m)$$$

Given that the condensation graph is topologically sorted, it is possible to have a constant time response per query. But queries need to be processed in the topological order (staring with big cycles, then self-loops, then first nodes that join cycles, etc.).

I got it to pass with C++, Python IO is unfortunately half of the exec time.

Can u share the solution?

https://mirror.codeforces.com/blog/entry/131419

I pasted the solution here.