### darkworld1's blog

By darkworld1, history, 2 months ago,

Recently I tried to solve the problem Unmerge using FFT.
After making the block array try to compute this polynomial (x^a1+1)(x^a2+1).....(x^am +1) using divide and conquer but I am getting TLE. but my complexity is n(log(n))^2. Here is my solution

• 0

By darkworld1, history, 3 months ago,

Recently I have Doing a problem where an array of the duplicate elements is given and we have to answer Q query given. For each query, we have to tell whether the subarray contains the majority element or not? ( A subarray contain majority element if one of the element occur more than half of the length of subarray).
I know we can do this question by segment tree straight forward.
now I try to solve this question using the median of the subarray. if the occurrence of median is greater than half of it length than the subarray has majority element.
But now I am facing the problem of finding the median of subarray if it contains duplicate elements? I used merge sort Tree for finding the median of array. can anyone suggest me how to find the median of subarray efficiently?

• 0

By darkworld1, history, 3 months ago,

you have given N. you need to find out C(n,1*1)+C(n,2*2)+C(n,3*3)+c(n,4*4) + .....
Here c(n,r) = n!/((n-r)!*(r)!)
one way is find C(n,i*i) for all i between 1 <= i <= sqrt(n)
. Is there exist any efficient solution than this ??

• +13

By darkworld1, history, 18 months ago,

there is a question where i was not able to find the state of dp or any other usefull information help me https://www.hackerrank.com/challenges/tree-pruning/problem

• -6

By darkworld1, history, 18 months ago,

Hello , i got stuck with the problem of dp where , i was not able to build dp state ? Link of the problem is https://atcoder.jp/contests/abc122/tasks/abc122_d

• -12

By darkworld1, history, 23 months ago,

hi everyone i am trying to solve a question . the question goes like this

you have given an array you have to maximize the cost factor of array and cost can be calculated in following way

COST = A*a[i]-B*a[j]+C*a[k]+D*a[l]+E*a[m] where i<j<k<l<m

now you have given A,B,C,D,E , maximize the cost of given array

sample test case n= 5

array = { 10 17 15 6 17}

A=8, B=5, C=4, D=6, E=9

Output is 172

..............................................................................

MY approach is simple i make a dp[n][4] and dp[i][0] calculate the max of A*a[i] till i , dp[j][1] calculate the max of A*a[i]-B*a[j] and so on ..

• -6

By darkworld1, history, 23 months ago,