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
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.
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.
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.
