DRGNDEN - Editorial

editorial
, , , , , , , ,
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

86

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
87

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
88

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
89

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

90

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

91

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

92

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

1 Like
93

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
94

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

1 Like
95

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

96

Here is my python solution if anyone wants to check:
https://www.codechef.com/viewsolution/36053473

97

Mo’s Algorithm is an offline solution where as this question requires an online solution.
Hope you’ve got your answer.

98

thnx bro . we need this.