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

×

SPALNUM - Editorial

PROBLEM LINK:

Practice
Contest

Author: Sergey Kulik
Tester: Yanpei Liu
Editorialist: Pawel Kacprzak

DIFFICULTY:

SIMPLE

PREREQUISITES:

Ad hoc, Palindrome

PROBLEM:


Let palindromic number be a number whose decimal digits form a palindrome. For example, $1, 22, 414, 5335$ are palindromic numbers, while $13$ and $453$ are not. Your task is to find the sum of all palindromic numbers in a range $[L, R]$ inclusive. In one test file, you have to solve this task for at most 100 test cases.

QUICK EXPLANATION:


Precompute the sum of palindromic number not greater than $K$, for $1 \leq K \leq 10^5$, and store these values in an array. Provide an answer for a single test case $[L, R]$ using precomputed sums for $R$ and $L - 1$.

EXPLANATION:


Let's first consider solving the problem for a single test cases. We are given two number $L$ and $R$ and we have to compute the sum of palindromic numbers from $L$ to $R$ inclusive. If we can check if a number $N$ is palindromic, then we can iterate over all numbers $N$ in a range $[L, R]$ and add $N$ to the result if and only if $N$ is palindromic. How to check if a number $N$ is palindromic? Well, it is pretty straightforward, we can list the sequence of digits of $N$ from right to left, and check if that sequence is a palindrome comparing corresponding digits. A pseudocode of that method can look like that:

// 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


This check runs in $O(\log(N))$ time, because the decimal representation of $N$ has $O(\log(N))$ digits.

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


This method works in $O((R - L) \cdot \log(R))$ time for a single test case, but since we have to handle at most $100$ of them and a range $[L, R]$ can have up to $10^5$ elements, this method will pass only the first subtask and will timeout on the second.

How to speed it up?


The crucial observation here is that, during the whole computation described above, we might check in a number $N$ is palindromic many times! This is not good, but fortunately, there is a common technique to avoid that.


Often when we are asked many times to compute some result for objects in some range [$A, B]$, we can do the following:

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:


Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 20 Sep '15, 22:38

pkacprzak's gravatar image

5★pkacprzak ♦♦
65383273
accept rate: 15%

edited 27 Sep '15, 14:11

admin's gravatar image

0★admin ♦♦
13.9k347483500

Practice link redirects to Pattern Matching Problem.

(27 Sep '15, 16:30) madhur1234★

12next »

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.

link

answered 27 Sep '15, 14:37

strangeknight's gravatar image

2★strangeknight
11
accept rate: 0%

I used same approach as given above but still it was showing wrong answer. https://www.codechef.com/viewsolution/8260332

link

answered 27 Sep '15, 14:42

manishsingla's gravatar image

2★manishsingla
11
accept rate: 0%

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) likecs6★

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) manishsingla2★

The link provided for author's and tester's solution is not valid. Please check

link

answered 27 Sep '15, 18:31

deepak_13's gravatar image

2★deepak_13
1
accept rate: 0%

We can also try the below approach:

  1. Start with L, sum=0

  2. Find Next Palindrome Number, //complexity O(Log(10^5))

  3. if PalindromeNumber <= R

         Sum+=PalindromeNumber
    

    else

         return sum
    
  4. Repeat Step 2 // O(10^4)

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

ybatra1988's gravatar image

2★ybatra1988
11
accept rate: 0%

edited 27 Sep '15, 18:43

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 ?

link

answered 27 Sep '15, 21:05

harry30's gravatar image

2★harry30
1
accept rate: 0%

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) drgn_hart2★

include<bits stdc++.h="">

using namespace std;

define n 312457

int digits[20]; int k=0; int sum[n]={0}; bool isp(int x) { int m,j,k=0; while(x>0) {

    digits[k]=x%10;
    x=x/10;
    k++;
}
 for(int i = 0, j = k - 1; i < k; ++i, --j)
{
    if(digits[i]!=digits[j])
    {
        return false;
    }

}

    return true;

}

void pre() { for(int p=1;p<=1000;p++) { if(isp(p)==true) { sum[p]=p; } sum[p]+=sum[p-1]; } }

int main() { long long int i,j,k,t,l,r; cin>>t; pre(); while(t--) {

    cin>>l;
    cin>>r;
    cout<<sum[r]-sum[l-1]<<endl;

}



















return 0;

}

link

answered 29 Sep '15, 13:11

shashi%20jey's gravatar image

2★shashi jey
11
accept rate: 0%

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

link

answered 17 Nov '15, 17:30

ps_3790's gravatar image

0★ps_3790
1
accept rate: 0%

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; }

link

answered 14 Jan '16, 13:41

abhishek181297's gravatar image

4★abhishek181297
1
accept rate: 0%

its showing run time error. can anyone tell me what is this run time error??

(14 Jan '16, 13:43) abhishek1812974★

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;

    scanf("%li%li",&a,&b);
    while(a<=b){
        char str[8];
        int palin=1;

        sprintf(str,"%li",a);

        len=strlen(str);

        for(i=0;i<=(len/2);++i){
            if(str[i]!=str[(len-1)-i]){
                palin=0;
                break;
            }
        }
        if(palin==1)
            sum+=a;

        a++;
    }

    printf("%li\n",sum);
}
return 0;

}

link

answered 20 Jan '16, 21:48

abhishek15006's gravatar image

4★abhishek15006
1
accept rate: 0%

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;

    scanf("%li%li",&a,&b);
    while(a<=b){
        char str[8];
        int palin=1;

        sprintf(str,"%li",a);

        len=strlen(str);

        for(i=0;i<=(len/2);++i){
            if(str[i]!=str[(len-1)-i]){
                palin=0;
                break;
            }
        }
        if(palin==1)
            sum+=a;

        a++;
    }

    printf("%li\n",sum);
}
return 0;

}

link

answered 20 Jan '16, 21:49

abhishek15006's gravatar image

4★abhishek15006
1
accept rate: 0%

toggle 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

Tags:

×9,528
×691
×638
×132
×35

Asked: 20 Sep '15, 22:38

Seen: 4,506 times

Last updated: 11 Jan, 20:34