AOPN - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

practice

contest

Author: Tanuj Khattar

Editorialist: Man Mohan Mishra

DIFFICULTY:

Medium

PREREQUISITES:

Dynamic Programming

PROBLEM:

You are given two positive integers A and B. Find count of numbers having even length palindrome as well as odd (more than 1) length palindrome as substring in range (A,B] (A is excluded, B is included).

SHORT EXPLANATION:

Let Count(N) = count of numbers having even length palindrome as well as odd (more than 1) length palindrome in range [1,N].

Answer of the problem will be Count(B) - Count(A).

Count(N) can be calculated using digit-dynamic programming.

EXPLANATION:

The necessary and sufficient condition for a number to be having even length palindrome as well as odd (more than 1) length palindrome as substring is:

  • Number must have a palindrome of length 2 as substring AND number must have a palindrome of length 3 as substring.

Now, function Count(N) can be implemented using digit-by-digit dp.
We maintain a 6-state Dp dp[index][2nd_last_digit][last_digit][is_odd_palin_found][is_even_palin_found][is_equal]. The states are:

  • index: index of current digit
  • 2nd_last_digit: 2nd last digit of the number formed till now
  • last_digit: last digit of the number formed till now
  • is_odd_palin_found: denotes if a palindrome of odd length (palindrome of length 3 to be precise) is found till now or not
  • is_even_palin_found: denotes if a palindrome of even length (palindrome of length 2 to be precise) is found till now or not
  • is_equal: denotes if the number formed till now is precisely equal to the number formed by first that many digits of the given number or less

Now we can give the recurrence for this dp.
Suppose dig is the vector containing the digits of given number from left to right and cur_digit is the digit that we want to append at the end of the number formed till now.

When is_equal is 0 (number formed till now is less than the number formed by first that many digits of the given number), the recurrence will be following:

  • dp[index + 1][last_digit][cur_digit][is_odd_palin_found | (2nd_last_digit == cur_digit)][is_even_palin_found | (last_digit == cur_digit)][is_equal = 0] += dp[index][2nd_last_digit][last_digit][is_odd_palin_found][is_even_palin_found][is_equal = 0]

When is_equal is 1 (number formed till now is equal to the number formed by first that many digits of the given number), the recurrence will be following:

  • If cur_digit == dig[index]:

    dp[index + 1][last_digit][cur_digit][is_odd_palin_found | (2nd_last_digit == cur_digit)][is_even_palin_found | (last_digit == cur_digit)][is_equal = 1] += dp[index][2nd_last_digit][last_digit][is_odd_palin_found][is_even_palin_found][is_equal = 1]

  • If cur_digit < dig[index]:

    dp[index + 1][last_digit][cur_digit][is_odd_palin_found | (2nd_last_digit == cur_digit)][is_even_palin_found | (last_digit == cur_digit)][is_equal = 0] += dp[index][2nd_last_digit][last_digit][is_odd_palin_found][is_even_palin_found][is_equal = 1]

  • If cur_digit > dig[index]: No change as the number formed by this way will be greater than the number formed by first that many digits of the given number.

Please follow the solution under SAMPLE SOLUTIONS section for implementation details.

SAMPLE SOLUTIONS:

solution

2 Likes
2

#include<stdio.h>
void main()
{
int a[50][50],i,j,m,n;
printf(“enter no of rows”);
scanf("%d",&m);
printf(“enter no of colums”);
scanf("%d",&n);
printf("\nenter the matrix");
for(i=0;i<m;i++)
{

           for(j=0;j<n;j++)
              {
                
                  scanf("%d",&a[i][j]);
              }
       }

printf(“matrix”);
for(i=0;i<m;i++)
{
printf("\n");
for(j=0;j<n;j++)
{

                  printf("%d\t",a[i][j]);
              }
       }

for(i=0;i<m;i++)
{

           for(j=0;j<n;j++)
              {
             if(i<j)
                  printf("\n%3d\t",a[i][j]);
}

}
}

3

/to prove a.a^t=i/
//9 march 2016
#include<stdio.h>
void main()
{
int a[2][2],b[2][2],c[2][2],i,j,k;
//to read and print matrix A
for(i=0;i<2;i++)
{
printf("\n");
for(j=0;j<2;j++)
{
scanf("%d",&a[i][j]);
}
}
printf(“matrix A\n”);
for(i=0;i<2;i++)
{
printf("\n");
for(j=0;j<2;j++)
{
printf("%d\t",a[i][j]);
}
}
for(i=0;i<2;i++)
{
printf("\n");
for(j=0;j<2;j++)
{
b[i][j]=a[j][i];
}
}
printf(“matrix B(transpose)\n”);
for(i=0;i<2;i++)
{
printf("\n");
for(j=0;j<2;j++)
{
printf("%d\t",b[i][j]);
}
}
printf("\n");
//for product c
for(i=0;i<2;i++)
{
printf("\n");
for(j=0;j<2;j++)
{
c[i][j]=0;
for(k=0;k<2;k++)
{
c[i][j]=c[i][j]+(a[i][k]*b[k][j]);
}
}
}
//product matrix
printf(“matrix c\n”);
for(i=0;i<2;i++)
{
printf("\n");
for(j=0;j<2;j++)
{
printf("%d\t",c[i][j]);
}
}

}

4

I think this is not the right place for this comment.

5

Help NEEDED! I’m getting TLE
https://www.codechef.com/viewsolution/34242514

7

@m_17 I am new in digit DP, so facing a bit of difficulty in understanding the approach. Could you elaborate on the role of ‘is_equal’ state with an example?

Thanks in advance.

9

First solve basic digit DP problems. The parameter is_equal is a standard state in many digit DP problems

10

More simple way is little bit of math
1-100, has 9 palindrome
1000-10000 has 910
10000-100000 has has 910*10
And so on

So in the end you will only need to traverse through number of digits to be more exact