### arham_doshi's blog

By arham_doshi, history, 4 years ago,

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 .

trick

explanation
code

explanation
code

explanation
code

explanation
code

explanation
code

explanation
code

explanation
code

explanation
code

explanation
code

explanation
code

explanation
code

explanation
code

explanation
code

explanation
code

explanation
code

Explanation
code

Explanation
code

Explanation
code

## 19) Planet queries I

explanation
code

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

• +77

| Write comment?
 » 4 years ago, # |   0 Auto comment: topic has been updated by arham_doshi (previous revision, new revision, compare).
 » 4 years ago, # |   +1 Problem links?
•  » » 4 years ago, # ^ |   +5 https://cses.fi/problemset/First register to create an account then you will be able to submit your codes.
•  » » » 4 years ago, # ^ |   0 Thanks :)
 » 4 years ago, # |   +5 Nice initiative.
 » 4 years ago, # |   +5 Very nice and helpful.
 » 4 years ago, # |   +5 Thanks arham_doshi
 » 4 years ago, # |   +5 all hail ......editorialist arham_doshi
 » 4 years ago, # |   +9 This may also help. https://github.com/ankitpriyarup/CSES_ProblemSet_Solution
•  » » 11 months ago, # ^ |   0 thankyou so much sir
 » 4 years ago, # |   0 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 ford instead of Floyd Warshall.
•  » » 4 years ago, # ^ |   +1 Yes, we can use it hence you have to print -1 as said in the problem statement.
•  » » » 4 years ago, # ^ |   +1 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:(
•  » » » » 4 years ago, # ^ |   +1 All tunnels are one-way tunnels...means it's a directed graph.
•  » » » » » 4 years ago, # ^ |   +1 Oops. Sorry my bad. :(
•  » » » » 4 years ago, # ^ |   0 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 "
 » 4 years ago, # |   +29 how to solve grid problems 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 is ..#..#. .#..#.. #.#..#. .#...#. instead I consider the input ######### #..#..#.# #.#..#..# ##.#..#.# #.#...#.# ######### It is really easy to implement. Initially fill the whole grid with #, then read the input.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Nice one, i like it. I use possible at many places like when when solveing a dp probelm
 » 4 years ago, # |   0 Auto comment: topic has been updated by arham_doshi (previous revision, new revision, compare).
 » 4 years ago, # |   0 Auto comment: topic has been updated by arham_doshi (previous revision, new revision, compare).
 » 4 years ago, # | ← Rev. 2 →   -8 ..
 » 4 years ago, # | ← Rev. 2 →   0 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? #include #include using namespace __gnu_pbds; using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int ui; typedef unsigned long ul; typedef pair pi; typedef pair pl; typedef vector vi; typedef vector vl; typedef vector vpi; typedef vector vpl; typedef priority_queue pq; typedef priority_queue,greater> pqg; typedef tree,rb_tree_tag,tree_order_statistics_node_update> indexed_set; #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound void dfs(int start, vector adj, vector& visited){ if(visited[start]) return; visited[start]=true; for(auto u:adj[start]) dfs(u,adj,visited); } int main() { ios::sync_with_stdio(0); cin.tie(0); int n,m; cin>>n>>m; vector adj(n+1,vi()); for(int i=0; i>a>>b; adj[a].pb(b); adj[b].pb(a); } vector visited(n+1,false); vi add; for(int i=1; i<=n; i++){ if(!visited[i]){ dfs(i,adj, visited); add.pb(i); } } cout<1){ for(int i=1; i
•  » » 3 years ago, # ^ |   0 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
 » 4 years ago, # | ← Rev. 2 →   +18 I'm currently making Video editorials for tree section of CSES. Interested people can check : CSES (DP ON) TREE ALGORITHMSI'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.
•  » » 4 years ago, # ^ |   +5 Thank You so much, it will be very helpful.
•  » » » 4 years ago, # ^ |   0 Do share suggestions/feedback if any :)
 » 4 years ago, # |   +1 This is really helpful.Thank You arham_doshi !!
 » 4 years ago, # |   0 13) flight routes give TLE as its O(nmk)
•  » » 4 years ago, # ^ |   0 Its o(m*k), i was writing there max(n, m)*k
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
 » 4 years ago, # |   0 Auto comment: topic has been updated by arham_doshi (previous revision, new revision, compare).
 » 4 years ago, # |   0 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 pair = pq.top(); if(pair.first > distance[pair.second]) continue; i want to know constraint / testcase wise why this will give TLE. it was giving tle for 3 large testcasesthe issue was resolved on introducing a boolean visited arraymycode = https://ideone.com/e6ZTWL (not needed tho)
 » 4 years ago, # | ← Rev. 3 →   0 https://cses.fi/paste/cfd81e7f5b4db001e2466/what is wrong in this solution? CycleFinding?????
•  » » 4 years ago, # ^ |   0 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
 » 4 years ago, # |   0 can someone help me understanding this lines in Labyrinth problem? p = from[p.x][p.y][0]; what does from means? i was unable to googling it. is there any keyword? thank you
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 It is just 2d vector, i have declared it on 3rd line, it helps us in recreating the path.
•  » » » 4 years ago, # ^ |   0 what does FRM and DIR stand for? You mentioned it on the same Labyrinth problem. Thanks for this blog btw.
•  » » » » 4 years ago, # ^ |   0 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.
•  » » » » » 4 years ago, # ^ |   0 got it thanks, i did a similar thing but i thought FRM or DIR was some advanced thing that ive never heard of
•  » » » 4 years ago, # ^ |   +5 got it, thanks!
 » 4 years ago, # |   +5 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 Implementation#include using namespace std; int n,m; vector > a(1000,vector (1000)); vector > d(1000,vector (1000,-1)); vector > vis(1000,vector (1000,false)); string ans; void dfs(int i,int j) { vis[i][j]=true; if(i==n-1 or i==0 or j==0 or j==m-1) { cout<< "YES\n"; cout<ans.size()+1) { ans+="D"; dfs(i+1,j); } // up if(i-1>=0 and not vis[i-1][j] and d[i-1][j]>ans.size()+1) { ans+="U"; dfs(i-1,j); } //right if(j+1ans.size()+1) { ans+="R"; dfs(i,j+1); } //left if(j-1>=0 and not vis[i][j-1] and d[i][j-1]>ans.size()+1) { ans+="L"; dfs(i,j-1); } // backtrack vis[i][j]=false; if(ans.size()>0) { ans.pop_back(); } } int main() { cin>>n>>m; vector > mons; pair start; for(int i=0;i>a[i][j]; if(a[i][j]=='M') { mons.push_back({i,j}); } else if(a[i][j]=='A') { start={i,j}; } else if(a[i][j]=='#') { vis[i][j]=true; } } } queue > q; for(pair p:mons) { q.push(p); vis[p.first][p.second]=true; d[p.first][p.second]=0; } while(not q.empty()) { pair v=q.front(); q.pop(); int i=v.first; int j=v.second; // down if(i+1=0 and not vis[i-1][j]) { vis[i-1][j]=true; d[i-1][j]=d[i][j]+1; q.push({i-1,j}); } //right if(j+1=0 and not vis[i][j-1]) { vis[i][j-1]=true; d[i][j-1]=d[i][j]+1; q.push({i,j-1}); } } // reset vis matrix for(int i=0;i
•  » » 4 years ago, # ^ |   +1 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.
•  » » » 4 years ago, # ^ |   0 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?
•  » » » » 4 years ago, # ^ |   0 no the time complexity will still be n*m , we will just start bfs with all monsers simalteniosly.
•  » » » » » 3 years ago, # ^ |   0 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).
•  » » 3 years ago, # ^ | ← Rev. 4 →   0 Hey RisingWizard arham_doshi Can you explain this line if(d[i][j+1]>ans.size()+1) ?
 » 4 years ago, # |   0 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?
 » 4 years ago, # |   0 How to solve Planet Queries II ?
 » 4 years ago, # |   0 Too much helpful. Thanks a lot.
 » 4 years ago, # |   0 In Highscores I dont understand how you detected positive cycle using dfs , can anyone please explain a bit more..
•  » » 4 years ago, # ^ |   +1 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.
 » 4 years ago, # |   0 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 codefrom 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
•  » » 4 years ago, # ^ |   0 I suggest you to use c++ or java as the test cases in cses are very tight.
 » 4 years ago, # |   0 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
 » 4 years ago, # |   0 Can someone help why this Java code gives TLE at test case #8 and how to optimize it?Code
 » 4 years ago, # |   0 Auto comment: topic has been updated by arham_doshi (previous revision, new revision, compare).
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   0 While solving finding cycles using bellman ford, if I iterate over a vectoredges, 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... #include using namespace std; #define ll long long vector> graph[100001]; vector> edges; int main() { cin.tie(0); ios_base::sync_with_stdio(false); int n, m; cin>>n>>m; for(int i=1;i<=n;i++) { vector e; e.push_back(0); e.push_back(i); e.push_back(0); edges.push_back(e); graph[0].push_back({0,i}); } while(m--) { int u,v,w; cin>>u>>v>>w; vector e; e.push_back(u); e.push_back(v); e.push_back(w); edges.push_back(e); graph[u].push_back({v,w}); } ll dist[n+1]={}; for(int i=1;i<=n;i++) dist[i]=INT_MAX; int parent[n+1]={}; int relaxed_vertex=-1; for(int i=1;i<=n;i++) { relaxed_vertex=-1; for(auto e: edges) { int u=e[0]; int v=e[1]; int w=e[2]; if(dist[v]>dist[u]+w) { dist[v]=dist[u]+w; parent[v]=u; relaxed_vertex=v; } } } if(relaxed_vertex==-1) cout<<"NO"<<'\n'; else { cout<<"YES"<<'\n'; for(int i=0;i cycle; int v=relaxed_vertex; while(! ( (cycle.size()>0) && (v==relaxed_vertex) ) ) { cycle.push_back(v); v=parent[v]; } cycle.push_back(relaxed_vertex); reverse(cycle.begin(),cycle.end()); for(auto c: cycle) cout< using namespace std; #define ll long long vector> graph[100001]; vector> edges; int main() { cin.tie(0); ios_base::sync_with_stdio(false); int n, m; cin>>n>>m; for(int i=1;i<=n;i++) { vector e; e.push_back(0); e.push_back(i); e.push_back(0); edges.push_back(e); graph[0].push_back({0,i}); } while(m--) { int u,v,w; cin>>u>>v>>w; vector e; e.push_back(u); e.push_back(v); e.push_back(w); edges.push_back(e); graph[u].push_back({v,w}); } ll dist[n+1]={}; for(int i=1;i<=n;i++) dist[i]=INT_MAX; int parent[n+1]={}; int relaxed_vertex=-1; for(int i=1;i<=n;i++) { relaxed_vertex=-1; for(int ver=0;ver<=n;ver++) { for(auto e: graph[ver]) { int u=ver; int v=e.first; ll w=e.second; if(dist[v]>dist[u]+w) { dist[v]=dist[u]+w; parent[v]=u; relaxed_vertex=v; } } } } if(relaxed_vertex==-1) cout<<"NO"<<'\n'; else { cout<<"YES"<<'\n'; for(int i=0;i cycle; int v=relaxed_vertex; while(! ( (cycle.size()>0) && (v==relaxed_vertex) ) ) { cycle.push_back(v); v=parent[v]; } cycle.push_back(relaxed_vertex); reverse(cycle.begin(),cycle.end()); for(auto c: cycle) cout<
•  » » 3 years ago, # ^ |   0 instead of for(auto e: edges) use reference. for(auto &e: edges)
•  » » » 3 years ago, # ^ |   0 Wow it worked!! But why is copying a small vector such an overhead I wonder? Thanks a lot though!
•  » » » » 3 years ago, # ^ |   0 You are doing it n times
 » 3 years ago, # | ← Rev. 2 →   0 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.
•  » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # |   0 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
•  » » 3 years ago, # ^ |   +3 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)
»
3 years ago, # |
Rev. 3   0

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
 » 2 years ago, # | ← Rev. 2 →   +4 Editorial for Road ReparationQues linkFirst 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.
 » 2 years ago, # |   +1 Editorial for Flight Route CheckQues LinKRun 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
 » 2 years ago, # |   0 very useful
 » 14 months ago, # | ← Rev. 2 →   0 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)$? My solution:https://cses.fi/paste/ec6f372ba706d70b619ffe/
 » 13 months ago, # |   0 For the problem High Scores there 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
•  » » 9 months ago, # ^ |   0 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).
 » 7 months ago, # |   0 Planet Queries IAn 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.
•  » » 5 weeks ago, # ^ |   0 Can u share the solution?
•  » » » 5 weeks ago, # ^ |   0 https://mirror.codeforces.com/blog/entry/131419I pasted the solution here.