×

# FRMQ TLE - Sparse Table

 0 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 3●6 accept rate: 0% 0★admin ♦♦ 19.8k●350●498●541

 0 Loose the % operation. answered 19 Apr '15, 16:22 559●1●3●12 accept rate: 7% I didn't get you. Can you please elaborate? (19 Apr '15, 20:37)
 0 i tried that but still getting TLE on last dataset. my code http://www.codechef.com/viewsolution/6778959 answered 19 Apr '15, 16:54 1 accept rate: 0%
 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]. answered 19 Apr '15, 20:53 6★na2a 1 accept rate: 0% It ran slower http://www.codechef.com/viewsolution/6800086. (20 Apr '15, 00:58)
 0 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? answered 20 Apr '15, 21:53 3●6 accept rate: 0%
 0 Change all long long variables to long (or int) except 'ans' answered 20 Apr '15, 22:40 3★p00r 139●1●6 accept rate: 10%
 0 Thank you evrybody, I finally got it and its working! answered 20 Apr '15, 22:49 3●6 accept rate: 0%
 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:

×729
×47
×33
×7

question asked: 19 Apr '15, 15:41

question was seen: 1,749 times

last updated: 21 Apr '15, 20:19