×

# Code optimization

 0 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 asked 16 Apr '15, 17:57 893●2●11●35 accept rate: 10% 0★admin ♦♦ 19.8k●350●498●541

 0 You don't have O(1) per query. answered 16 Apr '15, 18:33 559●1●3●12 accept rate: 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? (16 Apr '15, 19:38) It should be. You have log(something) which is not O(1) (16 Apr '15, 20:47)
 0 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. answered 16 Apr '15, 19:17 16●1●1●3 accept rate: 0% Thank you for your reply. But I am still unable to understand why my code is not O(1)? (16 Apr '15, 19:39) @ayush_awasthi You do NOT have O(1)/query. (16 Apr '15, 20:49)
 0 using dp[17][100000], or just use one dimension array. answered 16 Apr '15, 19:23 1 accept rate: 0% thanks for your reply (16 Apr '15, 19:39)
 0 what is the problem to use dp[100000][17] can someone explain?????? answered 17 Apr '15, 21:15 1●1 accept rate: 0% dp[17][100000] run faster due to cpu architecture..... (17 Apr '15, 21:54)
 0 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 http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/ answered 17 Apr '15, 22:17 35●2●13 accept rate: 0% It cannot be solved for 100 points using segment tree... You have to use Sparse table to answer the queries in O(1). (18 Apr '15, 21:36)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×720
×234
×47

question asked: 16 Apr '15, 17:57

question was seen: 2,036 times

last updated: 21 Apr '15, 20:15