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
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
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.
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
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.
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
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.
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
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.
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
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.
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
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
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
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 .
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
The question ask you to implement simple dijsktra more about it
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
The question is about simple Floyd Warshall Algorithmmore about it
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
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)
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
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])
_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
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
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
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
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
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
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
the problem is about simple topological sort.
more about it
topsort video
topsort tutorial cp algo
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
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)
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
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
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
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.
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
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
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
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
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 weight can'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 fordinstead ofFloyd 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 thedxanddyarrays but thepossiblefunction 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
frommeans? 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.
Thanks 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 Highscores I 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
from heapq import * n,m=map(int,input().split()) l=[] d={i:[] for i in range(1,n+1)} for i in range(m): a,b,c=map(int,input().split()) d[a].append([b,c]) dis=[float('inf') for i in range(n+1)] dis[1]=0 h=[] heappush(h,[0,1]) #distance, node while h: z=heappop(h) distance,cur=z for i in d[cur]: node,di=i if distance+ di < dis[node]: dis[node]=distance + di heappush(h,[dis[node],node]) print(*dis[1:])Thanks
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?
...
...
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 dijkstra for 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 be O(V*E*log(V)+V*V) which in worst case can be V^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.
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));
if (!c) for (auto it : adj[s]) dp[s][c] = minm(dp[s][c], (it.ss / 2) + dfs(it.ff, 1)); } } return dp[s][c];}
signed main() { memset(dp, -1, sizeof(dp)); cin >> n >> m; int x, y, w; map<pii, int>mp;
for (int i = 0; i < m; ++i) { cin >> x >> y >> w; if (x != y) { pii pr = {x, y}; if (mp.find(pr) == mp.end()) mp[pr] = w; else { w = minm(w, mp[pr]); mp[pr] = w; } } } for (auto it : mp) adj[it.ff.ff].pb({it.ff.ss, it.ss}); cout << dfs(1, 0) << endl; return 0;}
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 Cycles using 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)$$$?
https://cses.fi/paste/ec6f372ba706d70b619ffe/
For the problem
High Scoresthere is a simpler solution that is easier to implement. You can just use Bellman Ford to calculate the maximum distance from node 1 to n. Run the loop n — 1 times ( for calculating maximum distances using Bellman Ford ) and then scan the edges for one last time. If the distance to a node u seems to increase again, this indicates u is part of a positive weight cycle ( sum of weights in the cycle u that is part of > 0 ).If that is the case, check if node n is reachable from u and print -1 if 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.