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

×

FRMQ-APRIL CHALLENGE PROBLEM

I submitted the problem using segment trees but got 70 points only...then i saw the inherent pattern in the queries..that were being generated by the formulae...by the corresponding N values... and came with a faster dp approach but still got 70 points.... finally i wrote a sparse table...for quering in O(1) ...but still got 70 points... people got AC using sparse table...where did i go wrong? here is my solution http://www.codechef.com/viewsolution/6754646

asked 13 Apr '15, 18:27

coolsduy's gravatar image

3★coolsduy
1639
accept rate: 25%

edited 14 Apr '15, 13:39

admin's gravatar image

0★admin ♦♦
17.4k347487515

Plz post the editorial ..of this problem ..

(14 Apr '15, 00:20) sp1rs2★

First of all, you have stuff like "(b+11)%(t);" there. % operation is very slow; try to rewrite it using subtraction instead. Also you may change M[maxi][17] to M[17][maxi] to avoid large jumps over memory.

link

answered 13 Apr '15, 18:34

lebron's gravatar image

7★lebron
2.5k314
accept rate: 27%

For performance improvements, you need to use int M[17][maxi]. This makes your code much faster.

link

answered 13 Apr '15, 18:32

sampritipanda's gravatar image

5★sampritipanda
3621314
accept rate: 31%

Can you explain why?

(14 Apr '15, 01:03) ironmandhruv4★
2

Simple answer: slow RAM, fast CPU and CPU caches. The problem is, that current CPUs are much faster than RAM - see this article for more information about the CPU-RAM gap. As a result, a CPU access to RAM costs a lot of CPU cycles. To reduce this problem, current CPUs have several levels of caches, which usually work best, when accessing memory addresses, that are close to each other.

You can try a simple example. Try running this program and measure its execution time:

#define N 10000

int a[N][N];

int main(void) {
    for (int i=0;i<N;i++) {
        for (int j=0;j<N;j++) {
            a[i][j] = 0;
        }
    }
}

Then switch indices used to access the array - change a[i][j] = 0 to a[j][i] = 0 - and measure the time again. Depending on your machine and compiler optimizations, the second version will be slower (on my machine it is about 5 times slower). You can try the same with different values of N.

In the first version, you access the array (or matrix) row-by-row. As each row is stored as a continuous memory block, you start with the lowest memory address and continue up to the highest memory address assigned to the array. This type of access is cache-friendly. On the other hand, in the second version you access the array column by column, which means skipping to a distant memory address in each iteration.

As for the original question, one of the problems could also be the log2 function, which seems to be quite slow. Try to replace it with a lookup table. See my solution for more details.

(14 Apr '15, 03:13) pavel6★

Did anyone actually used any maths to solve this problem ?

link

answered 13 Apr '15, 18:36

karanaggarwal's gravatar image

4★karanaggarwal
2716
accept rate: 0%

I used the observation that for a particular X suppose the initial Y mapping was Y0 , Then after each subsequent cycles X would be mapped to Y0 - 11 , Y0 - 2*11 and so on . So I could skip all the queries that mapped X to Y later than the leftmost position of maxima between X and Y0 using a simple formula .

(13 Apr '15, 18:59) anuj954★

What would be the complexity of your solution ?

(13 Apr '15, 20:00) karanaggarwal4★

I used this same observation, for each x find sum of [x,y] [x,y-11] and so on . The queries would be uniformly distributed among all x excluding those which are never visited. So, we can find no. of Y's for each x and calculate individual sum for all x's. However complexity-wise this would still be O(M) assuming we use sparse tables.But apparently, this is a better optimized version than going for all the M queries normally because for a chunk of queries, we are keeping x same,only changing Y. This makes significant difference in time of execution.

(13 Apr '15, 21:44) fauzdar656★

i can't understand the purpose behind asking this question... ? First of all giving 70 points just for writing a classic segment tree solution... and even worse..100 points for just optimising the sparse table solution.. !

link

answered 14 Apr '15, 13:21

sumeet_varma's gravatar image

7★sumeet_varma
1258
accept rate: 20%

@karanaggarwal : yes i tried solving it using maths...first i found the pattern in queries... no matter what the initial x and y were the query pattern repeated after N-1 for x and after N for y when x=(x+7)%(t-1) and y=(y+11)%t; that means the queries will repeat exactly after N(N-1) queries...so if M was greater than N(N-1).. q=N(N-1) i calculated only the sum of N(N-1) queries and multipled it M/q times...and processed the remaining M%q queries... also queries for x depended on N in such way that if(N%7==1)...then x repeated after N/7 times... and queries for y depended on N in such way that if(N%11==0)...then y repeated after N/11 times... so the q term would be (number of time x repeated) * (no. of times y repeated)... and then using above dp approach...but it still fell apart when the N was neither N%7==1 or N%11==0 thats why i used sparse tables

link

answered 13 Apr '15, 18:48

coolsduy's gravatar image

3★coolsduy
1639
accept rate: 25%

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:

×46
×27
×6

question asked: 13 Apr '15, 18:27

question was seen: 2,138 times

last updated: 14 Apr '15, 13:39