When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Daenerys_Targaryen_1's blog

By Daenerys_Targaryen_1, history, 3 years 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

| Write comment?
»
3 years 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 :)

  • »
    »
    3 years 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?

    • »
      »
      »
      3 years 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

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

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

    (2^(j-1)+ 1) * 2^(n-i) must be 2^(j-1) * 2^(n-i) in a 1-based array.

    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)

    "dp[x] will be 1 + all dp[y] such that y < x" should have dp2 here...
    dp2[x]is the number of all non-magic sequences in 1..x-1 actually.
    So, dp2[x] = 1 + Sum(dp2[k]) where k is 1..x-1. 1 is for the empty sequence.
    Now (1 + dp2[j])*2^(n-i) makes sense.

    You don't talk about calculating all non-magical sequences here and that I believe is the crux of the problem.

    Update: dp2[x] calc is not that bad actually

    def magic_seq_cnt2(arr: List[int]):
        """
        Count all non-magical seq's.
        dp[i] - number of non magical subseq's ending in arr[i]
        :return : 2^(len(arr))-1 - #non-magical
        """
        M = 10**9 + 7
        ln = len(arr)
        dp = [1]*ln    # All seq's of length 1 are already non-magical.
        for i in range(1,ln):
            for j in range(i):
                if abs(arr[i] - arr[j]) > 1:
                    dp[i] += dp[j]
        return ((pow(2,ln)-1) - sum(dp))%M
    
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The first thing was my mistake.

      "dp2[x] is the number of all non-magic sequences in 1..x-1 actually."

      Yes, that was the idea.

      "You don't talk about calculating all non-magical sequences"

      So, the part where i was talking about that was the 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, but instead of dp its dp2. I'll edit my comment when i have time, because theres not only there are those issues but the problem statement was different from when i read it (it was saying "difference of 1" instead of "at most 1").

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

Hi!

For Q1.

I feel you can do it in $$$O(n^{3})$$$ through the following approach.

The constraint on $$$x$$$ is pretty low so you can fix the endpoints of the length of the rectangle you are taking which will be $$$O(n^{2})$$$. Now you can run a two pointer approach on the breadth so that you increase the breadth till you have at least $$$k$$$ points.

For every $$$y$$$ coordinate you can easily precompute the number of coordinates between two $$$x$$$ in $$$O(n^2) + O(nlogn)$$$ due to sorting.