darkworld1's blog

By darkworld1, history, 4 years ago, In English

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
please help me to optimize my solution.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By darkworld1, history, 4 years ago, In English

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?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By darkworld1, history, 4 years ago, In English

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 ??

Full text and comments »

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

By darkworld1, history, 6 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • -6
  • Vote: I do not like it

By darkworld1, history, 6 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • -12
  • Vote: I do not like it

By darkworld1, history, 6 years ago, In English

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

Full text and comments »

  • Vote: I like it
  • -6
  • Vote: I do not like it

By darkworld1, history, 6 years ago, In English

i get stuck with this dp problem in this problem i don't know how to represent a state please help me . link of problem is https://beta.atcoder.jp/contests/abc113/tasks/abc113_d

Full text and comments »

Tags #dp
  • Vote: I like it
  • -6
  • Vote: I do not like it