arham_doshi's blog

By arham_doshi, history, 4 months ago, In English

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

1) counting rooms

explanation
code

2) Labyrinth

explanation
code

3) Building Roads

explanation
code

4) Message Route

explanation
code

5) Building teams

explanation
code

6) Round Trip

explanation
code

7) Monsters

explanation
code

8) Shortest Routes I

explanation
code

9) Shortest Routes II

explanation
code

10) High scores

explanation
code

11) Flight Discounts

explanation
code

12)Finding Cycles

explanation
code

13) Flight Routes

explanation
code

14) round trip 2

explanation
code

15) Course Schedule

explanation
code

16) Longest flight routes

Explanation
code

17) Game Routes

Explanation
code

18) Investigation

Explanation
code

19) Planet queries I

explanation
code

other useful links


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

 
 
 
 
  • Vote: I like it
  • +77
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem links?

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Nice initiative.

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Very nice and helpful.

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it
»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

all hail ......editorialist arham_doshi

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

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

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 months ago, # |
  Vote: I like it +29 Vote: I do not like it

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 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I am weak at graph. I think, it will help me so much..Thank you so much Sir !!!

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
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<int,int> pi;
typedef pair<ll,ll> pl;
 
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
 
typedef priority_queue<int> pq;
typedef priority_queue<int,vector<int>,greater<int>> pqg;
typedef tree<int,null_type,less<int>,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<vi> adj, vector<bool>& 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<vi> adj(n+1,vi());
for(int i=0; i<m; i++){
	int a,b;
	cin>>a>>b;
	adj[a].pb(b);
	adj[b].pb(a);
	}
 
vector<bool> visited(n+1,false);
 
vi add;
for(int i=1; i<=n; i++){
	if(!visited[i]){
		dfs(i,adj, visited);
		add.pb(i);
		}
	}
 
cout<<add.size()-1<<endl;
if(add.size()>1){
	for(int i=1; i<add.size(); i++){
		cout<<1<<" "<<add[i]<<endl;
		}
	}	
 
}
»
4 months ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thank You so much, it will be very helpful.

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

This is really helpful.

Thank You arham_doshi !!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        here's my code https://pastebin.com/r8sMf9ea. hope it may help you

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 testcases

the issue was resolved on introducing a boolean visited array

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

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you so much! I got stuck at some and tried to find hints and solutions months ago, so it is relieving to find these.

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I have a check distance[source]!=LLONG_MAX

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    It is just 2d vector, i have declared it on 3rd line, it helps us in recreating the path.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      got it, thanks!

»
7 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Planet Queries II ?

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Too much helpful. Thanks a lot.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In Highscores I dont understand how you detected positive cycle using dfs , can anyone please explain a bit more..

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice work arham_doshi

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 code

Thanks

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://cses.fi/paste/f9a5dcad00d48d53efb38/ arham_doshi

It gives wrong answer for last 2 cases

»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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