AtCoder DP Contest-Q.Flowers

help
, , , , ,
1

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
2

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
3

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

4

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

4 Likes
5

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.

6

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

Segment Tree - Algorithms for Competitive Programming

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

10 Likes
7

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
8

exactly

1 Like
9

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

10

maybe you can a better link on github

1 Like
11

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