Code optimization

general
, ,
1

Can anyone give some tips on code optimization? I tried solving FRMQ of april15 long challenge and I could get 70 points even after following the optimizations mentioned in the comment section of the problem’s editorial. What else can be done?

My code

2

You don’t have O(1) per query.

3

You had to do O(1) Query using the Sparse Table but even after that you had to make an array of 17x10^5 because of CPU cache issues as making an array of 10^5x17 takes a lot of time. You can refer to my solution
solution accepted for 70 points using sparse table CodeChef: Practical coding for everyone
solution accepted for 100 points CodeChef: Practical coding for everyone.
For leaning sparse table you can go to topcoder link. It requires NlogN preprocessing and answers range maximum/minimum querry in O(1) time after preprocessing provided there are no updates which is the case given in the question. All optimizations used Fast I/O , Inline functions , Unsigned 32 bit integers , Array of 17x10^5 instead of 10^5x17.

4

using dp[17][100000], or just use one dimension array.

5

what is the problem to use dp[100000][17] can someone explain???

6

It can be solved by segment tree.
here the link uses the same concept except the max is used in the question and here the min is found in the given range

7

How is it not O(1) query? I mean I have compared two array positions only. That should be O(1), isn’t it?

8

Thank you for your reply. But I am still unable to understand why my code is not O(1)?

9

thanks for your reply

10

It should be. You have log(something) which is not O(1)

11

@ayush_awasthi You do NOT have O(1)/query.

12

dp[17][100000] run faster due to cpu architecture…

13

It cannot be solved for 100 points using segment tree… You have to use Sparse table to answer the queries in O(1).