You are not logged in. Please login at www.codechef.com 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

3★dragonemperor
89321135
accept rate: 10%

edited 21 Apr '15, 20:15

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 16 Apr '15, 18:33

alexvaleanu's gravatar image

4★alexvaleanu
5591312
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 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.

link

answered 16 Apr '15, 19:17

ayush_awasthi's gravatar image

4★ayush_awasthi
16113
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.

link

answered 16 Apr '15, 19:23

mickeyandkaka's gravatar image

4★mickeyandkaka
1
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??????

link

answered 17 Apr '15, 21:15

shubh_gupta_'s gravatar image

5★shubh_gupta_
11
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 http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/

link

answered 17 Apr '15, 22:17

aniruddha_paul's gravatar image

2★aniruddha_paul
35213
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
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:

×720
×234
×47

question asked: 16 Apr '15, 17:57

question was seen: 2,036 times

last updated: 21 Apr '15, 20:15