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

×

FRMQ - Problem Futher optimization using Sparse Table

I implemented the solution using sparse table but still got 70 points. Using a small change of Sparse_table[maxi][18] to Sparse_table[18][maxi] got me 100 points. Can anybody explain me how this change leads to faster calculation?

This question is marked "community wiki".

asked 14 Apr '15, 16:43

Ankit%20Aggarwal's gravatar image

4★Ankit Aggarwal
46129
accept rate: 0%

edited 15 Apr '15, 13:57

admin's gravatar image

0★admin ♦♦
19.8k350498541


link

answered 14 Apr '15, 18:10

alexvaleanu's gravatar image

4★alexvaleanu
5591312
accept rate: 7%

But its wrong.. The question should not be like this. By just changing the rows and columns you get AC. Codechef should not give such problems in the long contest. Very bad..

link

answered 14 Apr '15, 19:02

navneet1v2313's gravatar image

3★navneet1v2313
1
accept rate: 0%

2

It is NOT wrong. You should know about cache memory. It is not a question about "just changing the rows and columns you get AC".

(14 Apr '15, 19:47) alexvaleanu4★

@alexvaleanu: but a question based on such kind of algorithms is not suited to codechef where the main focus is on algorithms...

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

@navneet1v2313 imo that's what long contest are for. You have enough time to profile your solution.

link

answered 14 Apr '15, 19:25

piotrekg2's gravatar image

4★piotrekg2
413
accept rate: 0%

@alexvaleanu Many Thanks for the link, still, how does transposing the array speed up cache hit? just curious to learn, and would appreciate your answer

link

answered 14 Apr '15, 20:18

njr07121977's gravatar image

2★njr07121977
211
accept rate: 0%

@njr07121977 I believe it is because of the memory layout. When u declare something like int arr[10][1000] and loop over it, a new memory access is carried out once every 1000 times for 10 times . However , for arr[1000][10] the program makes memory access after every 10 operations for a thousand times . It doesn't seem much but apparently it does make a difference :)

link

answered 15 Apr '15, 00:34

rohan123's gravatar image

2★rohan123
315
accept rate: 0%

edited 15 Apr '15, 00:34

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:

×717
×234
×53
×47

question asked: 14 Apr '15, 16:43

question was seen: 3,898 times

last updated: 16 Apr '15, 05:12