PROBLEM LINK:
Editorialist: bvpcsi_2020(bvpcsi_2020 | CodeChef User Profile for BVP CSI | CodeChef)
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Basic Programming
PROBLEM:
We have to find the total number of valid positions.
QUICK EXPLANATION:
Number of valid positions equals the number of commands + 1
EXPLANATION:
Since Gopal can skip any of the commands any number of times. Therefore the possible moves = length of the given string+1
SOLUTIONS:
#include<bits/stdc++.h>#define MOD 1000000007#define ll long long int
using namespace std;
int main()
{
int n;
cin>>n;
string str;
cin>>str;
cout<<n+1;
return 0;
}
PROBLEM LINK:
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Math
PROBLEM:
Find the coins paid(because of crossing the gate) by Tyler during his path.
QUICK EXPLANATION:
Count the number of times when Tyler crosses the line y=x.
EXPLANATION:
Tyler visits the gate when he stands on line y=x, this happens only when he makes an equal number of right and up moves. Tyler will pass the gate if he is currently at a gate and will make a similar move to the last one.
We have to iterate over the moves, in order from left to right keeping track of the number of up and right moves till now and increment the answer when the next move is similar to the current one and number of right and up moves are equal.
SOLUTIONS:
#include<bits/stdc++.h>#define MOD 1000000007#define ll long long int
using namespace std;
void solver()
{ ll n,ans=0;
cin>>n;
string s;
cin>>s;
ll cu=0,cr=0;
for(int i=0;i<n-1;i++)
{ if(s[i]==‘U’)
{
cu++;
}
Else
{
cr++;
}
if((cr==cu)&&(s[i]==s[i+1]))
{
ans++;
}
}
cout<<ans;
}
int main()
{
solver();
return 0;
}
PROBLEM LINK:
DIFFICULTY:
MEDIUM
PREREQUISITES:
Basic Programming
PROBLEM:
Find out if the given sequence of brackets can be balanced or not by shifting just one bracket.
QUICK EXPLANATION:
Check the number of closed and open brackets.
EXPLANATION:
We will check if sequence of bracket is balanced by subtracting the number of opening brackets and the number of closing brackets. Correct bracket sequence is such a sequence in which balance of any of its prefixes is at least 0 and the balance of the entire sequence is equal to 0. For example, consider the shortest prefix with balance equal to −2. If we move some opening bracket to the beginning of the sequence, balance of considered prefix becomes −1 and then the sequence is not correct. Moving opening bracket to the desired or correct position doesn’t change anything. Moreover, if we move the closing bracket from the end of the considered prefix to the end of the sequence, it still doesn’t become correct, because balance of the prefix is −1.
SOLUTIONS:
#include<bits/stdc++.h>
#define MOD 1000000007
#define ll long long int
using namespace std;
int main()
{
int n,co=0;
string s;
cin>>s;
bool flag=false;
for(int i=0;i<n;i++)
{ if(s[i]==‘(’)
{ co++;
}
else{ co–; }
if(co==-2)
{ flag=true; break; } }
if(flag)
{ cout<<“No\n”; }
else{ if(co==0)
{ cout<<“Yes\n”; exit(0); }
cout<<“No\n”; } return 0; }
PROBLEM LINK:
DIFFICULTY:
MEDIUM
PREREQUISITES:
Basic programming
PROBLEM:
We have to find if it’s possible to generate the given number of types of coins .
QUICK EXPLANATION:
Apply the given constraints. Think about different test cases.
SOLUTIONS:
#include<bits/stdc++.h>#define MOD 1000000007#define ll long long int
using namespace std;void solver(){
ll x,y;
cin>>x>>y;
cout<<(((x + y) % 2 == 0 || (y > x + 1) || (y == 1 && x > 0) || (!y)) ? “No” : “Yes”);}
int main()
{solver(); return 0;}
PROBLEM LINK:
PROBLEM LINK:
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
2 D array,Graphs
PROBLEM:
Find the air molecule which can be formed by combining all the 1s vertically and horizontally
QUICK EXPLANATION:
Use graph implementation to find the maximum number of air molecule possible by combining all the 1s.
EXPLANATION:
A group of connected 1s forms an air molecule.
A cell in 2D matrix can be connected to neighbours(adjacent cells) except the diagonal adjacent ones because its given vertically and horizontally . Using graph,we keep track of the visited 1s so that they are not visited again.
SOLUTIONS:
#include<bits/stdc++.h>#define MOD 1000000007#define ll long long int
using namespace std;
int solver(vector<vector>& grid) {
if(grid.empty()||grid[0].empty()){
return {};
}
int answer=0;
int H=grid.size();
int W=grid[0].size();auto inside= [&](int row,int col){ return 0 <= row && row < H && 0<= col && col < W ; }; vector<vector<bool>>vis(H,vector<bool>(W)); vector<pair<int,int>>directions{{0,1},{1,0},{-1,0},{0,-1}}; for(int row=0;row<H;row++){ for(int col=0;col<W;col++){ if(!vis[row][col]&&grid[row][col]=='1'){ answer++; queue<pair<int,int>> q; q.push({row,col}); vis[row][col]=true; while(!q.empty()){ pair<int,int> neigh= q.front(); q.pop(); for(pair<int,int> dir : directions ){ int new_row=dir.first + neigh.first; int new_col=dir.second + neigh.second; if(inside(new_row,new_col)&&!vis[new_row][new_col]&&grid[new_row][new_col]=='1'){ q.push({new_row,new_col}); vis[new_row][new_col]=true; } } } } } } return answer; }int main()
{
int n,m;
cin>>n>>m;
vector<vector< char > >arr(n,vector< char > (m));
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
cin>>arr[i][j];
}
int x=solver(arr);
cout<<x;
return 0;
}
PROBLEM LINK:
DIFFICULTY:
HARD
PREREQUISITES:
Dfs,Graph
PROBLEM:
Find an alternate path in the graph which begins and ends with nodes and does not contain any node more than once
QUICK EXPLANATION:
Iterate over all possible combination, order and direction of extra edges.
EXPLANATION:
The total number of ways is O(m!2 m) ways to go through these extra edges, in which each will bring us at most O(n2) more simple paths. If we count all these simple paths using simple depth-first search (dfs), the time complexity will be O(n 2 m!2 m), which is the same as the order of the answer.
But we can reduce the original graph keeping all the nodes on some cycle and compressing the other ones. The longest simple path on a complete binary tree is and the compressed graph will contain at most nodes. Running a simple depth-first search(dfs) algorithm on such a smaller graph will result to an complexity solution which satisfies the small constraint of m and works pretty fast.
SOLUTIONS:
#include<bits/stdc++.h>#define MOD 1000000007#define ll long long int
using namespace std;
const int MAXN=255;
const int Mod=1000000007;
inline void add_mod(int &x,int y)
{
x=(x+y<Mod ? x+y : x+y-Mod);
}int u[MAXN],v[MAXN];
map<int,int> mp;
inline int get_id(int x)
{
if(!mp[x])mp[x]=(int)mp.size();
return mp[x];
}vector< int > e[MAXN];
void add_edge(int u,int v)
{
e[u].push_back(v);
e[v].push_back(u);
}inline int cal_size(int u,int n,int d)
{
int t=u,c=0,res;
while(t)c++,t>>=1;
res=(1<<(d-c+1))-1,t=c;
while(t<d)t++,u=u<<1|1;
return res-max(min(u-n,1<<(d-c)),0);
}int num[MAXN];
void pre_dp(int u,int f)
{
for(auto &v:e[u])
{
if(v==f)continue;
num[u]-=num[v];
pre_dp(v,u);
}
}int vis[MAXN];
void dfs(int u,int &tot)
{
add_mod(tot,num[u]);
vis[u]=1;
for(auto &v:e[u])
if(!vis[v])dfs(v,tot);
vis[u]=0;
}int main()
{
int n,m,d=0;
scanf(“%d%d”,&n,&m);
while((1<<d)<=n)d++;
get_id(1);
for(int i=0;i<m;i++)
{
scanf(“%d%d”,&u[i],&v[i]);
int t=u[i];
while(t)get_id(t),t>>=1;
t=v[i];
while(t)get_id(t),t>>=1;
}
for(auto &t:mp)
{
int u=t.first,id=t.second;
if(u>1)add_edge(get_id(u),get_id(u>>1));
num[id]=cal_size(u,n,d);
}
pre_dp(1,0);
for(int i=0;i<m;i++)
add_edge(get_id(u[i]),get_id(v[i]));
int res=0;
for(int i=1;i<=(int)mp.size();i++)
{
int tot=0;
dfs(i,tot);
add_mod(res,1LLtotnum[i]%Mod);
}
printf(“%d\n”,res);
return 0;
}