Daenerys_Targaryen_1's blog

By Daenerys_Targaryen_1, history, 7 weeks ago, In English

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

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

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

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

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

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.

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

Question 2:

It really helps if we think of the operations when we consider A in base 2.

Subtract 1 if odd: 11001010011->11001010010

Add 1 if even: 11001010010->11001010011

Divide by 2 if even: 11001010010 -> 1100101001

Multiply by 2: 1100101001 -> 11001010010

Notice that this is equivalent to in one operation either swaping the last digit or adding or removing a zero to the end. Also notice that we can transform any number in any other number doing that.

The main observation is that since you can only affect the last digit, you see which is the longest prefix that is common between A and B and simulate "taking all of the suffix out of A" and replacing it with what needs to be there for it to be equal to B. We can do this in O(logB + logA).

Question 3: This can be solved with small to large. If you don't know the idea and assuming you know dfs, think about mantaining a set containing all the values in the subtree of the children of a vertice when doing it, and then instead of just creating a new one each time you need to merge them, reutilize the set from the child with that has the most ammount of numbers in it. It can be proven that by doing that each element will be reassigned at most logn times, and for each reassignment you need O(logn), so the total complexity is O(nlog^2).

You will also need to mantaing the current MEX when doing this and updating it when the value of it is put into the set. Finding the next MEX will give you something like O(n) amortized (maybe O(nlogn) havent thought much about this) since even though in one operation you can iterate through O(n) values in one operation, since each value will only be iterated through once when you add everything up it will still be O(n).

Question 4: good job :D

Question 5 and 6: will have to think more, if i find a solution i'll talk about it

Question 7: so, [2,8,8,] contradicts with the statement but i'll assume you wanted to type [2,8,8,5,6] and something went terribly wrong.

Like LanceTheDragonTrainer said, this is a dp problem but his solution makes no sense. Let's define dp[x] to be the number of sequences in which v[x] is a number on it that has an absolute difference of 1 to the number right before it AND it doesn't conflict with dps. When calculating dp[i], we can iterate through all j < i and if abs(v[i]-v[j]) == 1, it means that it will make a valid sequence. Since we can choose either to put or not put any number in the sequence before or after it, the number of such sequences with i and j as numbers that initially fit the requirements will be (2^(j-1)+ 1) * 2^(n-i) .

This will work fine for dp[1] because no other dps will conflict with it but when going above that you will do double counting [2,3,5,6] would be counted both for dp[3] and dp[7]. To fix that, we define dp2[x] as the number of sequences using numbers from indexes 1 to x and don't have to adjacent numbers with absolute difference of 1. This one is easy to calculate as dp[x] will be 1 + all dp[y] such that y < x and abs(v[y]-v[x])!=-1. Now, when calculating dp[i] and try to pair it with j, the number of sequences added will be (1 + dp2[j])*2^(n-i), as any sequences with numbers that fit the requirement would have already counted sequences using i and j.

Just a question at the end. Where were these problems from? Were them from a specific contest or site? They were pretty interesting to solve :)

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

    Sorry for the small mistake in Qn7

    It was actually
    1) Their absolute difference is at max 1 instead of 1) Their absolute difference is 1

    Can you please find the new approach now?

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

      It actually doesn't change much. If you just do the ssme thing but check for at most 1 it will work

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

    The problems are from online rounds of companies like Curefit, Urban company, Uber, Google, Sprinklr etc etc

    I like to collect and solve online round problems :)

    They have completed their hiring so I thought now I can discuss about the approach of these problems :)

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

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

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

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