#### Hello everyone :)<br>↵
`I want to learn from my mistakes and so since I have no one to help me out so am writing this blog to rely on CF community to help me out.`↵
↵
#### Qn1↵
Given coordinates of points on a 2d plane. <br>↵
You need to `find the minimum cost rectangle such that it encloses atleast k points` <br>↵
Cost is decided by 2*(length + breadth) of the rectangle. <br>↵
↵
Constraints: <br>↵
At max 100 points (0<=x,y<=100)↵
1<=k<=100↵
↵
<spoiler summary="My Approach">↵
I Tried bruteforce that is iterating over all possible starting positions, then choosing all possible lengths and breadths, but this will lead to O(n^4)↵
<pre class="prettyprint"> ↵
int n = 100;↵
int a[n][n];↵
↵
for(int i=0;i<queries;i++)↵
{↵
int x,y;↵
cin>>x>>y;↵
a[x][y]++;↵
}↵
↵
int count[n][n]={0};↵
↵
for(int i=1;i<=n;i++)↵
{↵
for(int j=1;j<=n;j++)↵
{↵
count[i][j] = 0;↵
count[i][j] = count[i-1][j] + count[i][j-1] - count[i-1][j-1] + a[i][j];↵
}↵
}↵
↵
// bruteforce all rectangles↵
for(int i=0;i<n;i++)↵
{↵
for(int j=0;j<n;j++)↵
{↵
for(int xspan=1;xspan<n;xspan++)↵
{↵
for(int yspan=1;yspan<n;yspan++)↵
{↵
int sx=i,sy=j;↵
int ex=i+xspan,ey=j+yspan;↵
↵
if(count[ex][ey]-count[sx-1][sy-1]>=k)↵
{↵
ans = min(ans,2*(xspan+yspan));↵
}↵
}↵
↵
}↵
}↵
}↵
</pre>↵
</spoiler>↵
↵
If anyone has a better approach then please write it in comments section :) ↵
↵
#### Qn2 ↵
Given two numbers `A` and `B`. `Find if it is possible to transform A to B using the following operations any number of times`.<br>↵
1) If `A` is odd then you can subtract 1 from it<br>↵
2) If `A` is even then you can add 1 to it<br>↵
3) If `A` is even you can divide it by 2<br>↵
4) If `A` is even/odd you can multiply it by 2↵
<br>↵
If its possible to transform `A` to `B` then print the minimum number of operations required else print -1.<br>↵
Constraints: 1<=A,B<=10^18↵
↵
#### Qn3 ↵
Given a rooted tree with N nodes. Each node has some value Ci assigned to it. `For each node in the tree, print the MEX (the smallest number not present in a pool of values]) of the values present in its subtree.`<br>↵
Constraints: 1<=N<=10^5, 1<=Ci<=N-1, All Ci values are distinct and unique.<br>↵
↵
↵
#### Qn4 ↵
Given a tree with white and black nodes, `count the distinct pairs of nodes such that both are black and there exists atleast one white node in the path between them`. <br>↵
Constraints: N -> Number of nodes -> 10^5 | Edges -> N-1 (fixed)↵
<br>↵
↵
<spoiler summary="My Approach">↵
I used DFS, started from a corner node and then went on to a leaf node. ↵
↵
Upon reaching any leaf node I returned 1 if it was black (count of black node)↵
↵
Upon return of the dfs function, number of black nodes encountered is returned.↵
↵
If the current node is white then I calculate the answer by pairing all the black nodes already encountered with the remaining ones. ↵
↵
Now after calculation on white node, I set the black node count to 0 that is returned by this function.↵
↵
My Code:<br>↵
<pre class="prettyprint">↵
define ff first<br>↵
define ss second<br>↵
define pb push_back<br>↵
↵
map<int, vector<int>>g;↵
map<int, int>color;↵
map<int, int>vis;↵
↵
int visited_black_nodes = 0;↵
int ans = 0;↵
int n;↵
↵
int white_nodes = 0;↵
↵
int getans(int node)↵
{↵
↵
int black_nodes = 0;↵
int visited_cnt = 0;↵
for (auto i : g[node])↵
{↵
if (!vis[i])↵
{↵
vis[i] = 1;↵
black_nodes += getans(i);↵
visited_cnt++;↵
}↵
}↵
↵
if (visited_cnt == 0)↵
{↵
return color[node] == 0;↵
}↵
↵
if (color[node] == 1)↵
{↵
ans += (n - white_nodes - visited_black_nodes - black_nodes) * black_nodes;↵
visited_black_nodes += black_nodes;↵
return 0;↵
}↵
else↵
{↵
return black_nodes;↵
}↵
}↵
↵
↵
int main() {↵
↵
cin >> n;↵
↵
for (int i = 0; i < n; i++)↵
{↵
cin >> color[i + 1];↵
↵
if (color[i + 1] == 1)↵
{↵
white_nodes++;↵
}↵
}↵
↵
int q = n - 1;↵
while (q--)↵
{↵
int a, b;↵
cin >> a >> b;↵
g[a].pb(b);↵
g[b].pb(a);↵
}↵
↵
int corner_node = -1;↵
↵
for (int i = 0; i < n; i++)↵
{↵
if (g[i].size() == 1)↵
{↵
corner_node = i;↵
}↵
}↵
↵
getans(corner_node);↵
↵
cout << ans << endl;↵
}↵
↵
</pre>↵
</spoiler>↵
↵
#### Qn5 ↵
Given a list of commands for a robot. Each commands is a number with a character, for example `3L`, `4R` etc. Initially the robot is at 0. Now the goal is to `make the robot be at maximum distance from the start point`. To do this we can remove any continuous subsegment consisting of `L` and `R` with the condition that number of L commands removed should be equal to number of R commands removed.<br>↵
↵
Example: we can remove `2L 5R 1L 3R` <- number of `L` commands is = number of `R` commands = 2 here.<br>↵
But we cannot any of the following series: `2L` or `3R` or `2L 3R 4L`.<br>↵
↵
Its not necessary for the series of commands to be alternative for us to remove them. ↵
Example: 2L 1L 3R 5R can be removed.↵
↵
Input format:<br> ↵
T number of test cases, N number of commands, then N lines with each containing Di (integer) and then a char `L or R` <br>↵
Constraints:↵
1<=N<=10^5, 1<=Di<=10^6↵
↵
#### Qn6↵
Given a matrix of NxN dimension. Each cell is either 0 or 1. `Find the number of square submatrices such that 1<=i<=K max element in ith row of submatrix = max element in ith column of submatrix.`<br>↵
Constraints:↵
1<=N<=128 | Testcases uptill 12↵
↵
#### Qn7 ↵
Given an array, return total number of magical subsequences modulo (10^9 + 7).↵
A subsequence is a magical subsequence if we can choose 2 elements from it such that: <br>↵
1) Their absolute difference is `1`<br>↵
2) They are present in the subsequence one after another.<br>↵
↵
Examples: for array `[2,4,3,8,8,5,6]` magical subsequences are -> `[2,5,6]` `[4,3]` `[5,6]` `[4,3,5,6]` `[2,8,8,]`<br>↵
Total 85 are present for the above array.↵
↵
Constraints: <br>↵
1<=N<=1000 — Length of array | 1<=ai=10^5 — Array element.↵
<br><br>↵
↵
<spoiler summary="Ending Note">↵
Please forgive me for any mistakes that I might have made like language, explanation, formatting. <br>↵
Hoping to have a healthy discussion in comments section :)↵
↵
Thanks and Regards.<br>↵
Noob Coder </spoiler>↵
↵
PS.<br>↵
`If you downvoted then please write the reason` in comment section `or give some advice` so that I can learn from my mistake↵
`I want to learn from my mistakes and so since I have no one to help me out so am writing this blog to rely on CF community to help me out.`↵
↵
#### Qn1↵
Given coordinates of points on a 2d plane. <br>↵
You need to `find the minimum cost rectangle such that it encloses atleast k points` <br>↵
Cost is decided by 2*(length + breadth) of the rectangle. <br>↵
↵
Constraints: <br>↵
At max 100 points (0<=x,y<=100)↵
1<=k<=100↵
↵
<spoiler summary="My Approach">↵
I Tried bruteforce that is iterating over all possible starting positions, then choosing all possible lengths and breadths, but this will lead to O(n^4)↵
<pre class="prettyprint"> ↵
int n = 100;↵
int a[n][n];↵
↵
for(int i=0;i<queries;i++)↵
{↵
int x,y;↵
cin>>x>>y;↵
a[x][y]++;↵
}↵
↵
int count[n][n]={0};↵
↵
for(int i=1;i<=n;i++)↵
{↵
for(int j=1;j<=n;j++)↵
{↵
count[i][j] = 0;↵
count[i][j] = count[i-1][j] + count[i][j-1] - count[i-1][j-1] + a[i][j];↵
}↵
}↵
↵
// bruteforce all rectangles↵
for(int i=0;i<n;i++)↵
{↵
for(int j=0;j<n;j++)↵
{↵
for(int xspan=1;xspan<n;xspan++)↵
{↵
for(int yspan=1;yspan<n;yspan++)↵
{↵
int sx=i,sy=j;↵
int ex=i+xspan,ey=j+yspan;↵
↵
if(count[ex][ey]-count[sx-1][sy-1]>=k)↵
{↵
ans = min(ans,2*(xspan+yspan));↵
}↵
}↵
↵
}↵
}↵
}↵
</pre>↵
</spoiler>↵
↵
If anyone has a better approach then please write it in comments section :) ↵
↵
#### Qn2 ↵
Given two numbers `A` and `B`. `Find if it is possible to transform A to B using the following operations any number of times`.<br>↵
1) If `A` is odd then you can subtract 1 from it<br>↵
2) If `A` is even then you can add 1 to it<br>↵
3) If `A` is even you can divide it by 2<br>↵
4) If `A` is even/odd you can multiply it by 2↵
<br>↵
If its possible to transform `A` to `B` then print the minimum number of operations required else print -1.<br>↵
Constraints: 1<=A,B<=10^18↵
↵
#### Qn3 ↵
Given a rooted tree with N nodes. Each node has some value Ci assigned to it. `For each node in the tree, print the MEX (the smallest number not present in a pool of values]) of the values present in its subtree.`<br>↵
Constraints: 1<=N<=10^5, 1<=Ci<=N-1, All Ci values are distinct and unique.<br>↵
↵
↵
#### Qn4 ↵
Given a tree with white and black nodes, `count the distinct pairs of nodes such that both are black and there exists atleast one white node in the path between them`. <br>↵
Constraints: N -> Number of nodes -> 10^5 | Edges -> N-1 (fixed)↵
<br>↵
↵
<spoiler summary="My Approach">↵
I used DFS, started from a corner node and then went on to a leaf node. ↵
↵
Upon reaching any leaf node I returned 1 if it was black (count of black node)↵
↵
Upon return of the dfs function, number of black nodes encountered is returned.↵
↵
If the current node is white then I calculate the answer by pairing all the black nodes already encountered with the remaining ones. ↵
↵
Now after calculation on white node, I set the black node count to 0 that is returned by this function.↵
↵
My Code:<br>↵
<pre class="prettyprint">↵
define ff first<br>↵
define ss second<br>↵
define pb push_back<br>↵
↵
map<int, vector<int>>g;↵
map<int, int>color;↵
map<int, int>vis;↵
↵
int visited_black_nodes = 0;↵
int ans = 0;↵
int n;↵
↵
int white_nodes = 0;↵
↵
int getans(int node)↵
{↵
↵
int black_nodes = 0;↵
int visited_cnt = 0;↵
for (auto i : g[node])↵
{↵
if (!vis[i])↵
{↵
vis[i] = 1;↵
black_nodes += getans(i);↵
visited_cnt++;↵
}↵
}↵
↵
if (visited_cnt == 0)↵
{↵
return color[node] == 0;↵
}↵
↵
if (color[node] == 1)↵
{↵
ans += (n - white_nodes - visited_black_nodes - black_nodes) * black_nodes;↵
visited_black_nodes += black_nodes;↵
return 0;↵
}↵
else↵
{↵
return black_nodes;↵
}↵
}↵
↵
↵
int main() {↵
↵
cin >> n;↵
↵
for (int i = 0; i < n; i++)↵
{↵
cin >> color[i + 1];↵
↵
if (color[i + 1] == 1)↵
{↵
white_nodes++;↵
}↵
}↵
↵
int q = n - 1;↵
while (q--)↵
{↵
int a, b;↵
cin >> a >> b;↵
g[a].pb(b);↵
g[b].pb(a);↵
}↵
↵
int corner_node = -1;↵
↵
for (int i = 0; i < n; i++)↵
{↵
if (g[i].size() == 1)↵
{↵
corner_node = i;↵
}↵
}↵
↵
getans(corner_node);↵
↵
cout << ans << endl;↵
}↵
↵
</pre>↵
</spoiler>↵
↵
#### Qn5 ↵
Given a list of commands for a robot. Each commands is a number with a character, for example `3L`, `4R` etc. Initially the robot is at 0. Now the goal is to `make the robot be at maximum distance from the start point`. To do this we can remove any continuous subsegment consisting of `L` and `R` with the condition that number of L commands removed should be equal to number of R commands removed.<br>↵
↵
Example: we can remove `2L 5R 1L 3R` <- number of `L` commands is = number of `R` commands = 2 here.<br>↵
But we cannot any of the following series: `2L` or `3R` or `2L 3R 4L`.<br>↵
↵
Its not necessary for the series of commands to be alternative for us to remove them. ↵
Example: 2L 1L 3R 5R can be removed.↵
↵
Input format:<br> ↵
T number of test cases, N number of commands, then N lines with each containing Di (integer) and then a char `L or R` <br>↵
Constraints:↵
1<=N<=10^5, 1<=Di<=10^6↵
↵
#### Qn6↵
Given a matrix of NxN dimension. Each cell is either 0 or 1. `Find the number of square submatrices such that 1<=i<=K max element in ith row of submatrix = max element in ith column of submatrix.`<br>↵
Constraints:↵
1<=N<=128 | Testcases uptill 12↵
↵
#### Qn7 ↵
Given an array, return total number of magical subsequences modulo (10^9 + 7).↵
A subsequence is a magical subsequence if we can choose 2 elements from it such that: <br>↵
1) Their absolute difference is `1`<br>↵
2) They are present in the subsequence one after another.<br>↵
↵
Examples: for array `[2,4,3,8,8,5,6]` magical subsequences are -> `[2,5,6]` `[4,3]` `[5,6]` `[4,3,5,6]` `[2,8,8,]`<br>↵
Total 85 are present for the above array.↵
↵
Constraints: <br>↵
1<=N<=1000 — Length of array | 1<=ai=10^5 — Array element.↵
<br><br>↵
↵
<spoiler summary="Ending Note">↵
Please forgive me for any mistakes that I might have made like language, explanation, formatting. <br>↵
Hoping to have a healthy discussion in comments section :)↵
↵
Thanks and Regards.<br>↵
Noob Coder </spoiler>↵
↵
PS.<br>↵
`If you downvoted then please write the reason` in comment section `or give some advice` so that I can learn from my mistake↵
