SPALNUM - Editorial

ad-hoc
editorial
ltime28
palindrome
simple

#1

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* != 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] := exttt{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** - F[A - 1], because F** 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] := exttt{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][333]. Tester's solution can be found [here][444].

#2

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.


#3

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


#4

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


#5

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.


#6

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 ?


#7

#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*!=digits[j])
	{
		return false;
	}
	
}

	return true;

}

void pre()
{
for(int p=1;p<=1000;p++)
{
if(isp§==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;

}


#8

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


#9

#include<stdio.h>
int main()
{
int t,l[100],r[100],i,j,rev=0,sum=0,dig,n;
scanf("%d",&t);
printf("
“);
for(i=0;i<t;i++)
{
scanf(”%d %d",&l*,r*);
printf("
“);
}
for(i=0;i<t;i++)
{
sum=0;
if(l*<=r*)
{
for(j=l*;j<=r*;j++)
{
l*=n;
rev=0;
while(n)
{
dig=n%10;
rev=rev10+dig;
n=n/10;
}
}
if(l
==rev)
{
sum=sum+l*;
}
}
else
{
for(j=r*;j<=l*;j++)
{
r*=n;
rev=0;
while(n)
{
dig=n%10;
rev=rev10+dig;
n=n/10;
}
if(r
==rev)
{
sum=sum+r*;
}
}
}
printf(”%d
",sum);
}
return 0;
}


#10

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*!=str[(len-1)-i]){
				palin=0;
				break;
			}
		}
		if(palin==1)
			sum+=a;
		
		a++;
	}
	
	printf("%li

",sum);
}
return 0;
}


#11

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*!=str[(len-1)-i]){
				palin=0;
				break;
			}
		}
		if(palin==1)
			sum+=a;
		
		a++;
	}
	
	printf("%li

",sum);
}
return 0;
}


#12

You can also reverse the number and then compare it with the original number to find out if the number is a palindrome or not.It works for both all the test cases.


#13

is it necessary to take the help of data structrure (array)


#14

why the decimal representation of N have log(N) digits?


#15

Wow! This method is freaking amazing! My program execution time decreased from 1.30 seconds to 0.06 seconds. The change is amazing! Wow!


#16

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.

query [A,B][A,B] equals F**−F[A−1]


#17

it is not giving correct answer even for test cases. u can have a look at https://www.codechef.com/viewsolution/8253282


#18

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.


#19

Practice link redirects to Pattern Matching Problem.


#20

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