Answers to: FRMQ-APRIL CHALLENGE PROBLEMhttps://discuss.codechef.com/questions/67728/frmq-april-challenge-problem<p>I submitted the problem using segment trees but got 70 points only...then i saw the inherent pattern in the queries..that were being generated by the formulae...by the corresponding N values...
and came with a faster dp approach but still got 70 points....
finally i wrote a sparse table...for quering in O(1) ...but still got 70 points...
people got AC using sparse table...where did i go wrong?
here is my solution <a href="http://www.codechef.com/viewsolution/6754646">http://www.codechef.com/viewsolution/6754646</a></p>enTue, 14 Apr 2015 13:21:06 +0530Answer by sumeet_varmahttps://discuss.codechef.com/questions/67728/frmq-april-challenge-problem/67805<p>i can't understand the purpose behind asking this question... ? First of all giving 70 points just for writing a classic segment tree solution... and even worse..100 points for just optimising the sparse table solution.. ! </p>sumeet_varmaTue, 14 Apr 2015 13:21:06 +0530https://discuss.codechef.com/questions/67728/frmq-april-challenge-problem/67805Answer by coolsduyhttps://discuss.codechef.com/questions/67728/frmq-april-challenge-problem/67737<p><a href="/users/7736/karanaggarwal">@karanaggarwal</a> : yes i tried solving it using maths...first i found the pattern in queries...
no matter what the initial x and y were the query pattern repeated after N-1 for x and after N for y
when x=(x+7)%(t-1)
and y=(y+11)%t;
that means the queries will repeat exactly after N<em>(N-1) queries...so if M was greater than N</em>(N-1)..
q=N<em>(N-1)
i calculated only the sum of N</em>(N-1) queries and multipled it M/q times...and processed the remaining M%q queries...
also queries for x depended on N in such way that if(N%7==1)...then x repeated after N/7 times...
and queries for y depended on N in such way that if(N%11==0)...then y repeated after N/11 times...
so the q term would be (number of time x repeated) * (no. of times y repeated)...
and then using above dp approach...but it still fell apart when the N was neither N%7==1 or N%11==0
thats why i used sparse tables</p>coolsduyMon, 13 Apr 2015 18:48:48 +0530https://discuss.codechef.com/questions/67728/frmq-april-challenge-problem/67737Answer by karanaggarwalhttps://discuss.codechef.com/questions/67728/frmq-april-challenge-problem/67735<p>Did anyone actually used any maths to solve this problem ?</p>karanaggarwalMon, 13 Apr 2015 18:36:18 +0530https://discuss.codechef.com/questions/67728/frmq-april-challenge-problem/67735Answer by lebronhttps://discuss.codechef.com/questions/67728/frmq-april-challenge-problem/67733<p>First of all, you have stuff like "(b+11)%(t);" there. % operation is very slow; try to rewrite it using subtraction instead. Also you may change M[maxi][17] to M[17][maxi] to avoid large jumps over memory.</p>lebronMon, 13 Apr 2015 18:34:56 +0530https://discuss.codechef.com/questions/67728/frmq-april-challenge-problem/67733Answer by sampritipandahttps://discuss.codechef.com/questions/67728/frmq-april-challenge-problem/67730<p>For performance improvements, you need to use int M[17][maxi]. This makes your code much faster.</p>sampritipandaMon, 13 Apr 2015 18:32:43 +0530https://discuss.codechef.com/questions/67728/frmq-april-challenge-problem/67730