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

×

FRMQ TLE - Sparse Table

For the question : http://www.codechef.com/problems/FRMQ , I used the sparse table agorithm given here :http://wcipeg.com/wiki/Range_minimum_query to create a chache and then process the queries. Im getting only 70 points and subtask 3 shows TLE. My code : http://www.codechef.com/viewsolution/6793372. Can anyone give me any suggestions?

asked 19 Apr '15, 15:41

almondpie's gravatar image

4★almondpie
36
accept rate: 0%

edited 21 Apr '15, 20:19

admin's gravatar image

0★admin ♦♦
19.8k350498541


Loose the % operation.

link

answered 19 Apr '15, 16:22

alexvaleanu's gravatar image

4★alexvaleanu
5591312
accept rate: 7%

I didn't get you. Can you please elaborate?

(19 Apr '15, 20:37) almondpie4★

i tried that but still getting TLE on last dataset. my code http://www.codechef.com/viewsolution/6778959

link

answered 19 Apr '15, 16:54

ab_coding's gravatar image

2★ab_coding
1
accept rate: 0%

You can precalc the

next_x[i] = (i + 7) % n  
next_y[i] = (i + 11) % (n - 1)

for each i in 0...n-1
then just make x = next_x[x], y = next_y[y].

link

answered 19 Apr '15, 20:53

na2a's gravatar image

6★na2a
1
accept rate: 0%

edited 19 Apr '15, 20:54

(20 Apr '15, 00:58) almondpie4★

I optimised the solution and was able to make it till here : http://www.codechef.com/viewsolution/6802172 .I am not able to go more further than this. Can somebody help?

link

answered 20 Apr '15, 21:53

almondpie's gravatar image

4★almondpie
36
accept rate: 0%

Change all long long variables to long (or int) except 'ans'

link

answered 20 Apr '15, 22:40

p00r's gravatar image

3★p00r
13916
accept rate: 10%

Thank you evrybody, I finally got it and its working!

link

answered 20 Apr '15, 22:49

almondpie's gravatar image

4★almondpie
36
accept rate: 0%

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:

×729
×47
×33
×7

question asked: 19 Apr '15, 15:41

question was seen: 1,749 times

last updated: 21 Apr '15, 20:19