Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

arham_doshi's blog

By arham_doshi, history, 9 days 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

»
9 days 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).

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

Problem links?

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

Nice initiative.

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

Very nice and helpful.

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

all hail ......editorialist arham_doshi

»
8 days 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.

  • »
    »
    8 days 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.

    • »
      »
      »
      8 days 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:(

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

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

      • »
        »
        »
        »
        8 days 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 "

»
8 days 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.

  • »
    »
    8 days 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

»
8 days 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).

»
8 days 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).

»
8 days 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 !!!

»
3 days 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;
		}
	}	
 
}
»
3 days 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.

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

    Thank You so much, it will be very helpful.