### Daenerys_Targaryen_1's blog

By Daenerys_Targaryen_1, history, 2 months ago,

#### Hello everyone :)

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.
You need to find the minimum cost rectangle such that it encloses atleast k points
Cost is decided by 2*(length + breadth) of the rectangle.

Constraints:
At max 100 points (0<=x,y<=100) 1<=k<=100

My Approach

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.
1) If A is odd then you can subtract 1 from it
2) If A is even then you can add 1 to it
3) If A is even you can divide it by 2
4) If A is even/odd you can multiply it by 2
If its possible to transform A to B then print the minimum number of operations required else print -1.
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.
Constraints: 1<=N<=10^5, 1<=Ci<=N-1, All Ci values are distinct and unique.

#### 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.
Constraints: N -> Number of nodes -> 10^5 | Edges -> N-1 (fixed)

My Approach

#### 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.

Example: we can remove 2L 5R 1L 3R <- number of L commands is = number of R commands = 2 here.
But we cannot any of the following series: 2L or 3R or 2L 3R 4L.

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:
T number of test cases, N number of commands, then N lines with each containing Di (integer) and then a char L or R
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. where K = side of the submatrix
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:
1) Their absolute difference is at max 1
2) They are present in the subsequence one after another.

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]
Total 85 are present for the above array.

Constraints:
1<=N<=1000 — Length of array | 1<=ai=10^5 — Array element.

Ending Note

PS.
If you downvoted then please write the reason in comment section or give some advice so that I can learn from my mistake

• +11

 » 2 months ago, # |   0 Auto comment: topic has been updated by Daenerys_Targaryen_1 (previous revision, new revision, compare).
 » 2 months ago, # | ← Rev. 2 →   0 Edit: Qn 7 is indeed a dynamic programming question. But I wrote a wrote state below as I misunderstood part of the question — I thought that consecutive elements in the subsequence should vary by at most -1.Qn 7 is clearly a dynamic programming problem. One possible state is how many subsequences are there in the first i elements of the array that end with X? X is an integer from 1 to 100000.