HILLJUMP - Editorial

[deadwing97]

PROBLEM LINK:

Practice
Contest

Author: Hasan Jaddouh
Primary Tester: Prateek Gupta
Editorialist: Hussain Kara Fallah

PROBLEM EXPLANATION

There are N hills located on a straight line. The height of the i^th one is denoted by H_i. A participant standing at the top of the i^th hill jumps to the nearest hill to the right which is strictly higher than the one he is standing on. If the nearest one is further than 100 hills away, he doesn’t move anywhere.

Giving Q queries of 2 types:

The first type is given by (P,K) , a participant standing on the P^th hill is willing to perform K successive moves, what hill he will be ending at?

The second type is given by (L,R,X), for each hill between the L^th one and the R^th one (inclusive) should be increased by X (it may be negative).

DIFFICULTY:

medium

PREREQUISITES:

Complexity Analysis, Sqrt decomposition

EXPLANATION:

Let’s define an array nxt[N] where nxt_i denotes the next hill the participant standing at the i^th hill is going to jump to (or nxt_i=i if he cannot jump to any other hill).

Let’s break our hills into blocks, each block consisting of exactly S=\sqrt{n} hills.
As you can guess, keeping only the next hill we would jump to from each one, is not really effective. That’s because jumping hills one by one will lead us to at least O(Q * K) solution which exceeds the time limit indeed. Maintaining a sparse table is not a really good idea also, because modifying an element in a sparse table may lead you modifying the whole table.

Let’s make something similar to sparse table, Let’s define a table F[N]. For the i^th hill let F_i denotes the furthest hill (which is located in the same bucket) that we can reach via successive jumps starting from the i^th hill (and how many jumps we need to reach it).

Assuming both of our tables F[],nxt[] are fixed, then answering queries of the first type would be quite easy. Let’s repeatedly jump to the last hill in the current bucket as long as we are not exceeding the remaining jumps, after that moving 1 bucket forward via nxt[] table. So any number of jumps would be decomposed into at most \sqrt{n} mass jumps. At a point if a bucket was longer to finish than the remaining jumps, let’s just find our destination by processing it linearly. So the first query is answered in O(\sqrt{n})

Let’s discuss modifying our arrays.

Regarding modifying heights, this is a naive application of sqrt decomposition which can be done in O(\sqrt{n}), by updating blocks which were included partially in the query in a linear search. Regarding blocks that were completely included into the query we may increment the variable denoting the sum of increments applied to this bucket (each bucket should have a variable).

Observations:

For each i such that (i > R) :: nxt_i will stay the same.

It’s obvious because all participants are jumping to the right. Starting from the (R+1)^th hill, no hill will be changed.

For each i such that (i < L-100) :: nxt_i will stay the same, that’s because a participant cannot skip more than 100 hills, so for each i in the previous range, (i+100 < L), so no participant would be allowed to jump to a hill that is modified through our query.

Consider the i^th hill, if nxt_i=j and we apply the QUERY(L,R,X) for any (L ≤ i AND R ≥ j) then the value of nxt_i won’t change, that’s because the j^th hill is the closest strictly higher hill (to the i^th one), and applying the same query to all hills between won’t change the relative order between any pair of them.

For each i such that (R-100 < i ≤ R) :: nxt_i will be modified and needs to be calculated again.

For each i such that (L-100 ≤ i < L) :: nxt_i will be modified and needs to be calculated again.

As a conclusion, you can see that the nxt value of around 200 hills will be changed. We can process this in nearly O(400) by maintaining a stack. Regarding our table F modification, we should process each bucket that contains at least one hill which has its nxt variable modified. We should process each bucket linearly from right to left and maintain a stack during that. All modified buckets should have its data refreshed. Modification query can be done in O(400 + \sqrt{n})

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution: Can be found here
TESTER’s solution: Can be found here

[priyanshu_95]

How is the nxt value for 200 hills processed in O(400) using stack? I used a min-heap (or bst) to do this in 2O(100log(100)) ~ O(1400), which still passed. I’d like to know the better approach.

[kauts_kanu]

I think http://www.geeksforgeeks.org/next-greater-element/ should help…

[eugalt]

Instead of pointing to the last reachable hill in the same bucket the elements of F table might just point to the first reachable hill in the next bucket - that’s what both the author and the tester seem too do.

A little bit different approach is not to break the array into buckets but instead have the elements of table F point to a reachable hill located within a certain distance to the right. Range updates may be maintained, say, using a binary indexed (Fenwick) tree.

If we use a deque instead of a stack when we process items from right to left we can keep at most 100 items in it by popping items from the other end as soon as the distance from the current hill reaches 100. It can be implemented with a circular buffer instead of a standard deque.

Here is the

[1].


  [1]: https://www.codechef.com/viewsolution/15060098

[arkin]

The problem can also be solved in Q*log^2(N) for the general case,without the 100 restriction.

[mathecodician]

Can’t access the author’s and tester’s solutions

[supriyanta]

What is bucket here?

[yogesh9535]

Unable to check the authors and testers solutions. Access denied it says. Would like some help.
Thanks

[sonu_628]

size of block. total blocks are sqrt(n)