DRGNDEN - Editorial

editorial
, , , , , , , ,
63

HLD (Heavy-Light Decomposition) ka name suna he?

64

does that kind of function have any specific name?

65

Graham scan is close i guess…

66

If you choose height 4 with taste 7,notice it is left one. After it, when you go to 2, the line will cut the mid mountain of height 4 .It is well said, the line shouldn’t go through inside the mountain. Make a drawing of it, you’ll get my point more clearly.

67

Yeah, If you scroll a bit down, I’ve said that I didn’t notice that it was supposed to be a line segment, which I realised eventually. Thanks for the clarification anyway. Cheers.

68

Thanks for the resources :smiley:

69

It’s just an application of stack; it’s actually somewhat of a classic problem.

If you’re referring to me declaring a function in the middle of another function in C++, they’re called lambda functions.

71

Your’e Welcome !!

72

I have also used the same approach with some tweaks and block size of 5k for large n.
My Solution: CodeChef: Practical coding for everyone

73

good problem

1 Like
74

I used a simple approach but i’m having a hard time understanding why it didn’t work, my approach was:-

  • Create two segment trees which returns the first index of the max height element and last index of the max height element in a given range.
  • If b>c then use the tree which returns the first index of the max element in range c to b-1 inclusive. add the deliciousness of that index to ans and then update my b position to that index and again get the max height index in range c to b-1, do this while b!=c
  • if b < c then use the tree which returns the last index of max height in range b+1 to c, add the deliciousness of that index to ans then update b with that index and repeat the same while b!=c.

Using this approach i tested many test cases and all worked fine but when i got WA i have no idea why i got WA and my second concern is TLE. If building the tree takes n time and querying it takes logn time, why did i get TLE. Can someone tell me whats wrong with the logic

75

Imagine the heights look like 10^5, 10^5-1, … 3, 2, 1. Climbing the tree takes O(n) time in such a case

76

As @shisuko pointed out, the approach is O(n) per query.

I would also like to mention, if you want to answer static range max/min queries, a better alternative is to use a Sparse Table. Answering queries with a sparse table is O(1).

3 Likes
77

Oh got it, makes sense, but what about WA, i tested many test cases and it worked fine, why would this logic give wrong answer.

78

here is my python codehttps://www.codechef.com/viewsolution/35704254

I use the graph as mentioned in the editorial to simplify the solution. it gets simplified but still, in some test cases, it shows time limit exceeded. can you help my out, how to improve my code

80

Reading python without indentation is next to impossible. Can you please format your code.

Or even better, just link your submission.

82

hey can anyone tell me where am i going wrong. i know it will give TLE but according to me it should not give WA but it is giving.
in my code i performed a search from lower hill to higher. so that it can see its next higher hill.

here is my code : CodeChef: Practical coding for everyone

83

https://www.codechef.com/viewsolution/35557117

thank you for replying… here is my code.

84

@shisuko @aneee004 @balrams

My code (logic from the editorial) passes all but 1 file in the 3rd subtask which gives TLE. Can anyone help me find out why?

My solution (it’s well indented)

85

here is my python code https://www.codechef.com/viewsolution/35710565

I have also added comment so that you can get what is going on
I use the graph as mentioned in the editorial. it reduce the time complexity but it still give TLE on some test cases in subtask 2 and subtask 3, can you help me out, can you reduce the more time complexity of my code then please help me out. @aneee004