AtCoder DP Contest-Q.Flowers

Hi, I was trying the question Flowers from AtCoder DP contest and thought of solving this question using persistent segment tree to get the time complexity of nlogn (basic n2 approach with improvement) but don’t know why getting TLE. Can someone please help me out ?
my solution
@l_returns @aryanc403 @anyone_else ??

Update : array implementation of persistent segment tree gives AC quite easily (I didn’t change my logic even a little bit). Any clue why ?
Thanks to @blake_786 for teaching me this awesome implemetation.

1 Like

Thanks for the appreciation @harshraj22. First of all the answer to your question is that pointers access and update have an extra overhead as compared to array, so try to stick to array implementation as much as you can. Secondly I don’t think you require persistent segment tree to solve the question as you are updating the same head again and again. You can maintain a simple segement tree and that would also work.

2 Likes

I solved the problem using two for loops .How did you use segment tree .I also want to know how to implement segment tree in such problems.Thanks in advance

sort all the flowers on the basis of height,
now try to find the beauty value such that current flower is the last(or first both will work)in that sequence in term of height
now update the segment tree to this flower actual index

2 Likes

I do not know cpp.I am not able to understand your code.I know only python and javascript. would you explain with the help of pseudocode.

I have used the segment to optimize the time complexity (for updation purpose and also for the query purpose)

you can learn about segment tree from here

https://cp-algorithms.com/data_structures/segment_tree.html

4 flowers
n = 4
4
3 1 4 2
10 20 30 40

data = [flower height, flower beauty value, index]
flowers = [[3, 10, 1], [1, 20 , 2], [4, 30, 3], [2, 40, 4]]
sort these flowers on the basis of the height (means on the basis of data[0] )

sorted data
flowers = [[4, 30, 3], [3, 10, 1], [2, 40, 4], [1, 20, 2]]

we will iterate over all the flower, try to find out what is maximum value of the beauties we can have as a sequence such that the current flower’s height is least in that sequence

answer = [0, 0, 0, 0] => that will stored our current maximum beauties, which are zeros initially

iterate over flowers:

  flower1:
  [4, 30, 3]
  we will check for index [3 , n] what is the maximum beauty value which is 0 
  beauty = 30 + 0
  update the answer list with beauty 30 at index 3
  answer = [0, 0, 30, 0]

  flower2:
  [3 ,10, 1]
  we will check for index [1 , n] what is the maximum beauty value which is 30
  beauty = 30 + 10 = 40
  update the answer list with beauty 40 at index 1
  answer = [40, 0, 30, 0]

 flower3:
  [2 ,40, 4]
  we will check for index [4 , n] what is the maximum beauty value which is 0
  beauty = 40 + 0 = 40
  update the answer list with beauty 40 at index 4
  answer = [40, 0, 30, 40]

 flower4:
  [1 ,20, 2]
  we will check for index [2 , n] what is the maximum beauty value which is 40
  beauty = 40 + 20 = 60
  update the answer list with beauty 40 at index 4
  answer = [40, 60, 30, 40]

answer = [40, 60, 30, 40]

maximum value is 60

5 Likes

I got it .you used segment tree to optimize n^2 sollution to nlog(n).So segment tree is needed to get the maximum in [L,R] in log(n) to avoid inner loop time complexity of O(n).

2 Likes

exactly

1 Like

I implemented the same using segment tree it worked.I want to know one more thing where can I learn these advance data structures .I need only pseudo codes or python implementation bcoz I do not understand cpp stuffs


maybe you can a better link on github

1 Like

Thank You @ajaymalik. People like you, are a great resource for beginners