PROBLEM LINK:Author: Sergey Kulik DIFFICULTY:SIMPLE PREREQUISITES:Ad hoc, Palindrome PROBLEM:
QUICK EXPLANATION:
EXPLANATION:
// we assume that N > 0 bool is_palindromic(N): digits = [ ] while N > 0: digits.append(N % 10) N /= 10 i = 0 j = digits.size()  1 while i < j: if digits[i] != digits[j]: return False i += 1 j = 1 return True
Being able to perform the palindromic check, we can accumulate the result iterating over all integers in range $[L, R]$. A pseudocode for it might look like this: res = 0 for N = L to R: if is_palindromic(N): res += N
How to speed it up?
Let $F[N] := \texttt{the result for a range } [0, N]$ If we are able to compute $F[N]$ for all possible $N$, then the answer for a single query $[A, B]$ equals $F[B]  F[A  1]$, because $F[B]$ contains the result for all numbers not greater than $B$, so if we subtract $F[A  1]$, i.e the result for all number smaller than $A$, from it, we will get the result for all numbers in range $[A, B]$. If you did not know this technique, please remember it, because it is very useful. Using the above method, we can precompute: $S[N] := \texttt{sum of palindromic number not greater than } N$ in the following way: S[0] = 1 for N = 1 to 100000: S[N] = S[N  1] if is_palindromic(N): S[N] += N The above method runs in $O(10^5 \cdot \log(10^5))$ time, and we can use the S table to answer any single query $[L, R]$ in a constant time. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 20 Sep '15, 22:38

I didn't use the method given for speeding up the queries but still my solution didn't timed out. Don't know why??? https://www.codechef.com/viewsolution/8256629 and the links for problem statement are wrong. answered 27 Sep '15, 14:37

I used same approach as given above but still it was showing wrong answer. https://www.codechef.com/viewsolution/8260332 answered 27 Sep '15, 14:42
it is not giving correct answer even for test cases. u can have a look at https://www.codechef.com/viewsolution/8253282
(27 Sep '15, 15:08)
i know that but if you look at my program and the approach mentioned above ,you will find that both are exactly same. If anyone can tell where i am wrong.
(27 Sep '15, 15:45)

The link provided for author's and tester's solution is not valid. Please check answered 27 Sep '15, 18:31

We can also try the below approach:
Total Complexity would be Number of Testcases X 10^4 X O(Log(10^5)) What do you think? For a single test case this should be better solution.
link
This answer is marked "community wiki".
answered 27 Sep '15, 18:39

Help , Why this code : http://ideone.com/WIZx1G give WA even the test case same like the problem , can someone give me some of explanation ? answered 27 Sep '15, 21:05
You have not included right limit 'b' which is supposed to be included. Question asks you to include both the given numbers in the sum if they are palindromes. Try the testcase 1 11 where your code produces 45 while the correct answer should be 56
(28 Sep '15, 17:42)

include<bits stdc++.h="">using namespace std; define n 312457int digits[20]; int k=0; int sum[n]={0}; bool isp(int x) { int m,j,k=0; while(x>0) {
} void pre() { for(int p=1;p<=1000;p++) { if(isp(p)==true) { sum[p]=p; } sum[p]+=sum[p1]; } } int main() { long long int i,j,k,t,l,r; cin>>t; pre(); while(t) {
} answered 29 Sep '15, 13:11

can we not do this without using array. my code is giving wrong answer. can someone explain me why. https://www.codechef.com/viewsolution/8801313. please answered 17 Nov '15, 17:30

include<stdio.h>int main() { int t,l[100],r[100],i,j,rev=0,sum=0,dig,n; scanf("%d",&t); printf("\n"); for(i=0;i<t;i++) { scanf("%d %d",&l[i],r[i]); printf("\n"); } for(i=0;i<t;i++) { sum=0; if(l[i]<=r[i]) { for(j=l[i];j<=r[i];j++) { l[i]=n; rev=0; while(n) { dig=n%10; rev=rev10+dig; n=n/10; } } if(l[i]==rev) { sum=sum+l[i]; } } else { for(j=r[i];j<=l[i];j++) { r[i]=n; rev=0; while(n) { dig=n%10; rev=rev10+dig; n=n/10; } if(r[i]==rev) { sum=sum+r[i]; } } } printf("%d\n",sum); } return 0; } answered 14 Jan '16, 13:41

I tried this code but it was good only for subtask 1 and not for subtask 2. Can anyone tell me why? include<stdio.h>include<string.h>int main(){ int cases,k; scanf("%d",&cases); for(k=0;k<cases;++k){ long int a,b,len,i,sum=0;
} answered 20 Jan '16, 21:48

I tried this code but it was good only for subtask 1 and not for subtask 2. Can anyone tell me why? include<stdio.h>include<string.h>int main(){ int cases,k; scanf("%d",&cases); for(k=0;k<cases;++k){ long int a,b,len,i,sum=0;
} answered 20 Jan '16, 21:49

is it necessary to take the help of data structrure (array) answered 25 Mar '16, 05:30

why the decimal representation of N have log(N) digits? answered 05 Jul '16, 17:20

Wow! This method is freaking amazing! My program execution time decreased from 1.30 seconds to 0.06 seconds. The change is amazing! Wow! answered 27 Jun, 16:20

Can Anyone can explain the following lines, how it works? I'm not getting it. Examples might be used to better explaination. Thanks In Advance.
answered 24 Jul, 22:48

Practice link redirects to Pattern Matching Problem.
What's the name of the technique, you have mentioned? So, that we know more about it using that keyword?