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


Code optimization

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

dragonemperor's gravatar image

accept rate: 10%

edited 21 Apr '15, 20:15

admin's gravatar image

0★admin ♦♦

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


answered 16 Apr '15, 18:33

alexvaleanu's gravatar image

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) dragonemperor3★

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

(16 Apr '15, 20:47) alexvaleanu4★

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 solution accepted for 100 points 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

ayush_awasthi's gravatar image

accept rate: 0%

edited 16 Apr '15, 19:19

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

(16 Apr '15, 19:39) dragonemperor3★

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

(16 Apr '15, 20:49) alexvaleanu4★

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


answered 16 Apr '15, 19:23

mickeyandkaka's gravatar image

accept rate: 0%

thanks for your reply

(16 Apr '15, 19:39) dragonemperor3★

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


answered 17 Apr '15, 21:15

shubh_gupta_'s gravatar image

accept rate: 0%

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

(17 Apr '15, 21:54) raja44ever3★

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


answered 17 Apr '15, 22:17

aniruddha_paul's gravatar image

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) unrealsoul0075★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 16 Apr '15, 17:57

question was seen: 2,036 times

last updated: 21 Apr '15, 20:15