DRGNDEN - Editorial

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

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

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

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.

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

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

Or even better, just link your submission.

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

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

thank you for replying… here is my code.

@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)

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

Your logic is perfect, the only flaw is that your travelling the entire path to find the taste. And in worst case this can be O(n). This will happen if the given H is sorted.

To speed up the queries you’ll have to use a BIT or a segment tree.

1 Like

I was not able to spot the bug in your implementation, also I’m not very fluent in python. However I ran some bash tests and your code fails for this test case below. You’re probably not handling the impossible case well. The rest seems to be right.

Test Case
10 1
873 597 892 20 227 716 594 235 875 875 
310 407 169 441 366 721 317 819 562 491 
2 10 4

Expected: -1
Output: 2090
2 Likes

I guess problem is with this statement:

if pre < h[i]:
	taste += t[i]
	pre = h[i]
if h[i] > h[b-1]:
	taste = -1
	break

Don’t you think if pre>h[b-1] you need to print -1 !!

And One more thing you will have solution if and only if you can reach b. If not able to reach then you should print -1. So add one more condition to check it.

2 Likes

pls suggest how to improve this Data Structures on Tree part…thanks in advance!

I’ll say just solve some standard problems on these data structures. Then you will start getting ideas/intuitions to solve such problems.

thank you for the suggestion

can I get the proper understandable solution to this question in python3, because I don’t know how to implement BIT and segmented tree here in this question, please

My language is C++, and I only know the very basics of python.
This submission might help you.

1 Like

thanks a lot for helping me @aneee004
:blush: I have looked at this code but due to lack of comments it is very hard to understand.
by the way thanks for helping me :smiling_face_with_three_hearts: :smiling_face_with_three_hearts:

1 Like

The process of flattening the tree is called euler tour of the tree.
More information : On Euler tour trees - Codeforces

1 Like

Can someone please tell me on which test cases my solution is getting failed.
My sol:CodeChef: Practical coding for everyone