You are not logged in. Please login at www.codechef.com to post your questions!

×

HILLJUMP - Editorial

3
2

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 ith one is denoted by Hi. A participant standing at the top of the ith 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 Pth 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 Lth one and the Rth 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 nxti denotes the next hill the participant standing at the ith hill is going to jump to (or nxti=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 ith hill let Fi denotes the furthest hill (which is located in the same bucket) that we can reach via successive jumps starting from the ith 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) :: nxti 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) :: nxti 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 ith hill, if nxti=j and we apply the QUERY(L,R,X) for any (L ≤ i AND R ≥ j) then the value of nxti won't change, that's because the jth hill is the closest strictly higher hill (to the ith 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) :: nxti will be modified and needs to be calculated again.

For each i such that (L-100 ≤ i < L) :: nxti 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

This question is marked "community wiki".

asked 18 Aug '17, 06:55

deadwing97's gravatar image

3★deadwing97
118822
accept rate: 0%

edited 18 Aug '17, 16:16

admin's gravatar image

0★admin ♦♦
19.0k348495533


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.

link

answered 18 Aug '17, 17:15

priyanshu_95's gravatar image

3★priyanshu_95
111
accept rate: 0%

(18 Aug '17, 18:26) kauts_kanu5★

https://www.codechef.com/viewsolution/15904454

Can anyone say why this give me Tle for two subtask:i think it must pass with low time but why it give me TLE? can you give some test case that make TLE?

link

answered 20 Oct '17, 21:53

chemtham's gravatar image

2★chemtham
203
accept rate: 0%

edited 20 Oct '17, 21:54

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

link

answered 21 Aug '17, 04:53

eugalt's gravatar image

4★eugalt
1584
accept rate: 5%

edited 21 Aug '17, 07:53

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

link

answered 21 Aug '17, 16:02

arkin's gravatar image

5★arkin
1
accept rate: 0%

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

link

answered 01 Sep '17, 13:13

mathecodician's gravatar image

5★mathecodician
2.6k629
accept rate: 7%

What is bucket here?

link
This answer is marked "community wiki".

answered 06 Sep '17, 21:55

supriyanta's gravatar image

1★supriyanta
11
accept rate: 0%

size of block. total blocks are $sqrt(n)$

(14 Jun, 16:43) sonu_6284★

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

link

answered 15 Sep '17, 19:56

yogesh9535's gravatar image

4★yogesh9535
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×14,474
×2,412
×193
×115
×65
×24

question asked: 18 Aug '17, 06:55

question was seen: 2,811 times

last updated: 14 Jun, 16:43