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

×

FRMQ - Editorial

-11
3

PROBLEM LINK:

Practice
Contest

Author: Vasia Antoniuk
Tester: Sergey Kulik
Editorialist: Adury Surya Kiran

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Range Maximum Queries

PROBLEM:

You are given an array of integers, and are asked a lot of queries (at most 10^8) like give two indices find the maximum of all the integers in the array whose index lies between those two.

EXPLANATION:

The generation of the queries as given in the question is
x = x + 7 (mod N - 1)
y = y + 11 (mod N)
l = min(x, y)
r = max(x, y)
You need to find maximum of a[i] such that l <= i <= r.

The generation of (l, r) pairs is like a pseudo random procedure, so its very very hard task to find a pattern in that. Now as we got (l, r) for each query the finding maximum is quite a standard task of range queries.

There are a lot of ways to find range queries. Some of them are
1. O(1) per Update and O(N) per query : Using an array, we can update each element in O(1) and when queried iterate through all elements from l to r.
2. O(log N) per Update and O(log N) per query : There are a lot of ways to do this. We can use Segment trees, Binary index trees, etc.
3. O(N) per Update and O(1) per query : We can use Sparse Table to solve this case.

The methods used for 2 and 3 are very standard and their explanation can be found at a lot of places.

Some useful links for solving Range Queries using Method 2 are
1. Utkarsh Lath's Blog using Segment trees
2. Geeks for Geeks using Segment trees
3. Using BIT

You can find very useful explanation of all methods including the sparse table method here in this Topcoder Tutorial.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution
Tester's solution

This question is marked "community wiki".

asked 14 Apr '15, 15:05

adurysk's gravatar image

4★adurysk ♦
92842028
accept rate: 11%

edited 01 Jun '16, 20:21

admin's gravatar image

0★admin ♦♦
17.4k347487515


14

I expect to see a lot of comments like "I wrote a correct solution but got TL, why?!" below :D

What was the reason for giving such constraints? There are no idea at all in given task, only problem is because of constraints. If you want to prevent logN solutions from passing - much lower constraints are enough; if you want to make task challenging and teach people to write well-optimized code - you may set TL even stricter (0.75 is still not hard to reach)... This problem is already awful even with 1 second, so why to stop at it?

link

answered 14 Apr '15, 17:04

lebron's gravatar image

7★lebron
2.5k314
accept rate: 27%

The reason of arr[logN][N] getting accepted is that since x and y are increased only by a small amount, the row number tends to remain constant, and column number increases only by a small amount. So subsequent accesses tend to happen within the same memory block. This increases the number of cache hits.

link

answered 14 Apr '15, 18:11

a7i7's gravatar image

5★a7i7
15125
accept rate: 0%

And all the time i was thinking that the intended solution will be sleeker and awesome...what a disgrace
Such problems must not be allowed to appear in Long Contests.. worst problem ever on CC.. waste of time!!

link

answered 15 Apr '15, 20:03

usaxena95's gravatar image

7★usaxena95
221129
accept rate: 0%

1

just by changing a[n][logn] to a[logn][n] the solution gets passed.. It doesn't make any sense for us to spend hours on end to think of such optimizations.. a constraint of m<=10^7 would have easily sufficed in this problem -_-

(16 Apr '15, 05:03) gvaibhav217★

To me Codechef long challenge is very important and seeing such a poor "code optimization" problem makes me sad. Codechef, I have high hopes from you, please take care before serving the problems. The efforts being made are great but this is one scar on the repute.

link

answered 15 Apr '15, 20:20

saurv4u's gravatar image

5★saurv4u
312
accept rate: 0%

I think M<=10⁷ or N,M<=10⁶ would have perfectly make the M*logN solutions time out, there was no need at all for M<=10⁸ (which is supposed to be TLE on other tasks btw)

Why is nowadays every problem so much about crazy optimization?

I mean, why do we have to spend hours trying to find out whether if we (don't) inline a function/use post-increment operator outside of while()/swap the dimensions of an array/take modulo one time less/other useless optimizations, then the running time will decrease by 0.01sec and will be inside the limit? It just doesn't make sense in my opinion, since you can't know, what will decrease and what will actually increase the running time. E.g. I changed N times post-increment on X to X+=N; and the program actually ran 0.10sec slower on one single test case.

link

answered 15 Apr '15, 13:57

emarci15's gravatar image

6★emarci15
211
accept rate: 0%

I have no idea about sparse table someone please give me some tutorial

link

answered 15 Apr '15, 22:27

nil96's gravatar image

2★nil96
18071842
accept rate: 5%

I did just the same thing and was getting 70 points.
I used and array for the sparse matrix as arr[N][logN] ,but as soon as I changed my array to arr[logN][N] ,it gave 100 Points..
What's the reason for this?
Why did the running time decrease?

link

answered 14 Apr '15, 18:01

amanmj's gravatar image

4★amanmj
692
accept rate: 18%

1

Read about cache

(14 Apr '15, 18:07) alexvaleanu4★

https://www.youtube.com/watch?v=0rCFkuQS968
Found an MIT lecture on this. Complexity: { O(N) (update),O(1) (query) }

link

answered 18 Apr '15, 11:39

codedecode0111's gravatar image

5★codedecode0111
3201114
accept rate: 0%

that's sweet, thanks

(07 May '15, 15:36) ashish17293★

Can someone explain "Method 3"? How to use splay trees with O(N) update and O(1) query?

link

answered 14 Apr '15, 18:00

alexvaleanu's gravatar image

4★alexvaleanu
5591312
accept rate: 7%

edited 14 Apr '15, 18:01

It have been fixed now; when edotorial was published, there was "We can use Splay Tree to solve this case." in case 3.

(14 Apr '15, 20:06) lebron7★

Ok, thank you.

(14 Apr '15, 20:07) alexvaleanu4★

Can any one give me a useful link for splay tree ?

link

answered 14 Apr '15, 18:02

shakil_ruet's gravatar image

5★shakil_ruet
112
accept rate: 0%

This problem was kind of a disaster . Its very sad that all those people who didnt use a kind of worthless optimisation atleast from the respect of goals of codechef didn`t get the points and hence the ranking they deserved. Very sad .

link

answered 15 Apr '15, 00:35

dreamplay's gravatar image

5★dreamplay
1485
accept rate: 0%

2

On the other hand, such "worthless optimization" may give you one more solved problem at regional contest or even world finals. For me it happened 10-15 times during trainings already. I don't think that this problem is good, for me picking such constants looks like easy way to make problem "harder" and simply get more money for it :D But people who can't solve a problem - don't deserve higher rankings.

(15 Apr '15, 00:55) lebron7★

@prasadram126 the O(M*N) solution is really supposed to get 20 points, you should implement the third one to get 100p

link

answered 15 Apr '15, 13:58

emarci15's gravatar image

6★emarci15
211
accept rate: 0%

can anyone post a link to a resource where i can learn this approach of using sparse tables.

link

answered 15 Apr '15, 17:50

ashish1729's gravatar image

3★ashish1729
1534
accept rate: 10%

http://www.codechef.com/viewsolution/6745851

i have implemented my solution based on topcoder tutorial of sparse table algorithm during the contest! But still i got 70 points! Please have a look at it !

link

answered 15 Apr '15, 21:49

grab's gravatar image

2★grab
211
accept rate: 0%

1

Can you give the link to tutorial of sparse table

(15 Apr '15, 22:34) nil962★

arr[N][logN] worked for me (after lots of optimizations of course)

link

answered 16 Apr '15, 11:56

fauzdar65's gravatar image

6★fauzdar65
29114
accept rate: 21%

segment tree is the best to be understood if someone knows DIVIDE AND CONQUER METHOD.I finally gt it

link

answered 16 Apr '15, 22:26

aniruddha_paul's gravatar image

2★aniruddha_paul
35211
accept rate: 0%

can i get some better explanation for sparse table ,,,it's difficult to understand,,plz explain or give some link by which it can understand more easily

link

answered 17 Apr '15, 20:24

shubh_gupta_'s gravatar image

5★shubh_gupta_
11
accept rate: 0%

edited 17 Apr '15, 20:25

i used segment tree to solve this question but in last two test cases i am getting runtime error can anyone explain me why i am getting runtime error link text i think so my solution is well optimized and i don't know for which test cases i am getting runtime error if i increased the size of array around 10^7 then i am getting tle please anyone explain me why i am getting runtime error and tle if i increase the size of array?

link

answered 24 Apr '15, 22:28

viperx's gravatar image

4★viperx
3114
accept rate: 0%

Answer is hidden as author is suspended. Click here to view.

answered 02 May '15, 12:07

bangga's gravatar image

0★bangga
(suspended)
accept rate: 0%

Anybody solved this problem with BIT ?

link

answered 04 May '15, 19:57

mayur_shingote's gravatar image

2★mayur_shingote
1
accept rate: 0%

I solved the problem using segment tree which takes O(logn) time.I got only 70 points,for the last sub-task I am getting a TLE.Can someone please help me? solution- https://www.codechef.com/viewsolution/7497214 Any help is appreciated.

link

answered 18 Jul '15, 17:00

gospelslide's gravatar image

3★gospelslide
37
accept rate: 0%

-1

will 10^8 run in one second? i used to assume around 10^7 calculations per second. what should is assume as upper limit for computations in one sec.

link

answered 14 Apr '15, 17:58

ashish1729's gravatar image

3★ashish1729
1534
accept rate: 10%

1

order of 10^8 operations per second is a good approximation on an upper bound.

(15 Apr '15, 11:07) gvaibhav217★

thanks, upper bound for codechef increased,

but i feel its risky in competitions where you can make one submission or you get penalty for wrong one.

(15 Apr '15, 17:15) ashish17293★
-1

I wrote the solution with sparse table but it took only 70 points. I managed to get 100 with these 2 further optimizations:

  • When you have something like (A + b) % C and b is very small compared to C, using C++ the code(a + b) % c is far slower than a += b; if(a > c) a -= c; Don't ask me why because I don't know, but I noticed that only this was enough to take 100 point (from more than 1s to 0.8).
  • N is O(10^5) so x can have at most 10^5 -1 different values, and y 10^5 different values. We can find the length of the two cycles ( length of x cycle = N / 7, length of y cycle = N/11, because 7 and 11 are prime numbers). Then you can find L = lcm of these 2 numbers and if L < M you can just make L queries and if sum[ i ] is the sum of answers at i-th iteration answer will be sum[ L ]* (M/L) + sum[ M % L]
link

answered 15 Apr '15, 03:11

smokemother's gravatar image

5★smokemother
-1
accept rate: 0%

edited 15 Apr '15, 03:12

-1

Hi i used method 1 to solve this problem. this is my code with this i got only 20pts. Can any please tell me why i got only 20pts?

link

answered 15 Apr '15, 08:30

prasadram126's gravatar image

2★prasadram126
21
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:

×12,344
×1,081
×184
×46
×44
×27

question asked: 14 Apr '15, 15:05

question was seen: 8,345 times

last updated: 01 Jun '16, 20:21