The idea and motivation behind these hints is that you should only open them up after spending a decent amount of trying to solve the problem yourself. Also open the hints in sequential order.
Example: Try the problem for 40 mins, then open hint 1. Then using hint 1 only, try the problem for another 20-30 minutes. If still unable to make much progress only, then open hint 2 and so on.
Hint 1
We know that once the matchstick that burns fastest, burns out, rest will burn from both the ends.
How do we use this?
Hint 2
We need to find the time taken when L to R matchstick are lit simultaneously…so what information we need to approach the problem:
- we need to find the fastest burning matchstick from L to R(inclusive).
- We need to find the slowest one from L to R(inclusive).
- We need to find the slowest one except the matchstick L to R(inclusive).
Can you get the point of why this much data is sufficient to solve the problem?
Hint 3
We can find the above information using either a segment tree/Fenwick tree, but how to use this information to produce the answer.
Hint 4
Let’s consider a,b and c denotes the fastest burning matchstick from L to R, slowest burning matchstick from L to R, and slowest burning matchstick except for L to R respectively. Then we can say the answer to this query is:
- answer = a + max((b-a)/2, c)
Can you interpret the formula?
Hint 5
The matchstick that burns fastest in the range L to R burns out and ignites all the other matchsticks on their rear ends.
Hint 1
The query part tells us that we need to apply RMQ but we need to figure it out what information to store.
One thing to notice is that we can’t check all the substrings in each query. Can there be any observation to take?
Hint 2
Let’s start with small queries.
- If R-L = 0 then the answer is NO as it is not possible to find any rich substring.
- If R-L = 1 then the answer is NO as it is not possible to find any rich substring.
- If R-L = 2 then the answer is NO if all the char are different else YES.
- If R-L = 3 then the answer is NO if there is no rich substring of length 3 else YES.
- If R-L = 4 then the answer is NO if there is no rich substring of length 3 else YES.
- If R-L = 5 then the answer is NO if there is no rich substring of length 3 else YES.
And so on.
Why is this working??
Hint 3
Lemma: We can say if a string S is rich then there exist 2 ones which are less than either adjacent or 1 zero apart. This implies that for a rich string, a substring of length 3 is also rich so we need to check for 3 length substrings only.
Can you apply RMQ now?
Hint 4
We just need to maintain an array for each 3 length substring whether they are rich or not and apply RMQ over it to get the answer.
Hint 1
Pay attention to the fact that the array values are sorted, so we can use binary search to find the value for k in each query.
But how to know the value of I?
Hint 2
We can see the binary search structure in the value of i. Let suppose i = x then i = x+1, i = x+2 and so on also the correct answer but i = x-1, i = x-2, and so on are not.
But how can we find i = x is a possible answer?
Hint 3
We can say that if a[x+1] - a[x] \le d, a[x+2] - a[x+1] \le d, ... , a[k-1] - a[k] \le d then we can say that i = x is a possible answer.
It could be solved by an RMQ. We just need to apply the RMQ over the difference of the adjacent array element.
Hint 1
We need to solve the RMQ over an array with online queries.
It is pretty straight forward.
Hint 1
We can say if the array has X inversions then:
If K \le X then the answer is X - K.
else the answer is (K-X)%2.
Can you guess why it is happening?
Hint 2
Hint 3
To find the inversion count, we can use the standard merge sort algorithm.
Hint 1
We answer every query by traversing the array but it gets TLE. So, what we are doing extra. Can sorting help here and what to sort?
Hint 2
Yes. We can sort the queries here according to y coordinate, but why is it helpful?
As the answer for any y = k does not collide with some line then there are two possibilities, either the line lies above it or below it. If it lies above it then all the y < k also not collide with this one else it lies below it then all the y > k also not collide with this one.
What does it indicate?
Hint 3
We can run a sweep line algorithm over the y coordinate. In other words, The idea of this sweep line algorithm is to imagine a horizontal line sweeping from y = −∞ to y = ∞.
Hint 4
Let’s denote 1 if it is intersecting with the current sweep line or else 0. Now, we need a data structure that efficiently maintains the information for us.
That can be done by RMQ.
Hint 1
If we remove the constraint for K then the problem can be solved using LCA, but what can we do here?
Up to now, you can understand that all problems of these types have the first step to sort the queries according to some parameter, in this question we are using K.
Hint 2
Let suppose initially the tree has a cost of each edge is equal to zero.
When we process the queries ascending order of K than in each query K = x, we add cost to all the edges which have cost \le x. This way, we only have the required edges for each query.
But how do we know the answer for each path?
Hint 3
We know Euler’s tour of a tree. Can we use that to solve our problem? We are using zero for all the edges as it does not affect the xor.
Hint 4
We can know that by processing that order, we can apply RQ over this order to answer our problem.
“Consider any node x that does not lie in the (u, v) path. Notice that x occurs twice or zero times in our specified query range. Therefore, the nodes which occur exactly once in this range are precisely those that are on the (u, v) path! (Try to convince yourself of why this is true: It’s all because of dfs() properties.)”
Hint 1
We need to find the cheapest drink which can satisfy the conditions explained in the question. It can be done by checking all drinks for each query, but it gets TLE.
Can we arrange the drinks in any order to reduce the complexity?
Hint 2
Yes. Let’s try to sort the array according to C value and then we can say that this offers us binary search over it as if the answer exists in some range of this sorted arrangement of drinks then all the ranges which contain this range also have the answer.
Now, the task is how to find the answer to any range efficiently?
Hint 3
It is easy to see that we need to build an RMQ to this sorted arrangement of drinks to answer it efficiently. We are changing the value of l and r according to the value of m.
For more details: click