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?
You don’t have O(1) per query.
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 http://www.codechef.com/viewsolution/6767911
solution accepted for 100 points http://www.codechef.com/viewsolution/6768824.
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.
using dp[17][100000], or just use one dimension array.
How is it not O(1) query? I mean I have compared two array positions only. That should be O(1), isn’t it?
Thank you for your reply. But I am still unable to understand why my code is not O(1)?
thanks for your reply
It should be. You have log(something) which is not O(1)
what is the problem to use dp[100000][17] can someone explain???
dp[17][100000] run faster due to cpu architecture…
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
It cannot be solved for 100 points using segment tree… You have to use Sparse table to answer the queries in O(1).