YouTube Video Tutorial - HILLJUMPING

editorial
, ,
1

Hi

I’ve put in a lot of my efforts this time, kept the video detailed so that a lot of people including beginners are able to understand how to solve this tough squareroot decomposition problem HILLJUMPING from Codechef August 17 Long Challenge.

Check out the video editorial here.
I am sorry for the low sound quality. Please use headfones at full volume. YouTube itself decreased the volume level after upload :frowning:

If you do not want the problem description, skip to 3:25
Then I explain my approach till 14:50 after which code discussion begins.

8 Likes
2

you said video is of 10 mins and code discussion begins from 14:50 weird XD

3

Lmao XDDDD

4

Video is not available.Fix this soon.

5

Resolved, Check the new link.

1 Like
6

I meant there is around 3.5 mins of problem description followed by 10 mins of explanation and then the rest of video is about code discussion.

7

This question can be solved by using Segment trees with lazy propagation also right? If anybody knows the Segment tree approach to this question please share it here.

8

I dont think its possible to solve this question with segment tree. I would be blown away if someone has solved it with segTree.

9

Use volume booster chrome extension.

10

I have solved it using only segment trees and lazy propagation, comment space is too small, see the answer below…

1 Like
11

I have solved it using just segment trees and lazy propagation. Actually combining two different approaches:

First Approach:

If number of updates is high use segment tree with lazy propagation where each node contains:
a) Max value in interval
b) Index of this max value
c) delayed add value

Combine function is trivial.

Now when querying - start query 100 steps to the right from start (or last query point) , then from
maxindex -1, and again… forming the sequence or just counting , then continue again 100 steps away. if returns value below the current max - break out as there is a gap of 100, if found Kth - return it

Second Approach:

Different segment tree if the number of updates is less frequent then queries - in this case index tree is “almost” a merge tree , node value contains vector of pairs (val,index) containing strongly increasing sequence.
plus “add” value for lazy propagation of the updates.
When merging (combining) - just find lower bound of the right end of the left segment in the right vector and merge right part of the right vector to the left vector. (Take care about “add” values of both parts as they shift whole vector up or down)

Plenty of optimisation is possible and this potentially could even work for high update number. But combination of these two solutions in one - solves the problem with 100 points.

solution link: Link to the AC Solution

2 Likes
12

@lboris I followed a similar approach as yours except that in the second approach I stored the next 200 values instead of the next 100 and I got AC.

My AC solution

13

I solved it using segment tree but I feel @rachitiitr approach is better and faster to think of and implement in this problem.

2 Likes