MASNUM - Editorial (Kodeathon 15.2)

NOTE

This editorial is aimed at people new to competitive programming , making it quite verbose.

PROBLEM LINK:

Practice

Contest

Author: Pulkit Sharma

Tester: Satyam Gupta

Editorialists: Pulkit Sharma , Satyam Gupta

DIFFICULTY:

EASY

PREREQUISITES:

Math

PROBLEM:

consider an N digit number A (not having any leading zeroes) . We have to find the number of possible A s such that , A + Rev(A) = 10^N - 1 , where Rev(A) is the number
formed by reversing the order of digits of A.

EXPLANATION:

Lets represent A as d_1d_2d_3d_4...d_n
So, for N = 3 and A = 312

d_1 = 3

d_2 = 1

d_3 = 2

Now B = Rev(A) = d_nd_{n-1}...d_3d_2d_1

In our case , the target is 10^N-1 , therefore all elements of the target will be 9

So, what we need to do

(d_1 d_2 d_3d_4...d_n) + (d_n d_{n-1}...d_3d_2d_1) = 99...

We can have two cases

Case 1 : N is odd
Consider N = 3

A = d_1d_2d_3

Therefore,

B = d_3d_2d_1

We need to satisfy the following equations :
d1+d3 =9 , d2+d2 = 9 , d3+d1 =9

The first and the last equations are identical, So we can discard any one of them.
After discarding we are only left with 2 equations

d1+d3 =9 , d2+d2 = 9

Consider the second equation , ( d2+d2=9)

2*d2 = 9

d2 = 9/2

d2 = 4.5

But , since d2 is a digit of a number, it can never be a floating value.

Therefore , whenever N is odd , we cannot have any solution as the middle element comes out to be 4.5 to satisfy the problem’s requirements,but that is not possible.

Case 2 : N is even
Consider N = 4

A = d_1d_2d_3d_4

Therefore,

B = d_4d_3d_2d_1

We need to satisfy the following equations:
d1+d4=9,d2+d3 = 9,d3+d2 = 9, d4+d1 = 9

As before, 2 equations are identical.
After eliminating them , we have
d1+d4 = 9 , d2+d3 = 9

Consider d1+d4=9

It can be easily seen , that the above equation has 10 solutions.
Namely,(0,9), (1,8), (2,7), (3,6), (4,5), (5,4), (6,3), (7,2), (8,1), (9,0)

But according to the question d1 cannot be zero. Therfore there are 9 solutions in total

Now,lets see the next equation (d2+d3=9)

Similar as above , this equation has 10 solutions and all of them are valid.

As the two equations are independent of each other, Therefore we have a total of 90 solutions in total for the case where N=4

DERIVING THE FINAL FORMULA

Now we are quite close to the solution. Whenever N is odd, the answer will be 0
And Whenever N is even we will have , 9 solutions for the first equation(made of first digits of A and B)
and 10 solutions for each of the remaining equations.
The number of remaining equations = (N/2 - 1) (As half of them are same, and we already considered the equation made of the first digits)

Final formula = 9*10^{N/2-1}

But there is a minor twist .

As N can go up to 10^5 therefore the resultant number from the formula will be very large.Therefore, instead of storing the number somewhere , we have to just print the result, digit by digit.

So print 9 and N/2-1 number of zeroes.

AUTHOR’S SOLUTION:

#include<bits/stdc++.h>
using namespace std;
int main()
{
	long int t,n;

	cin>>t;

	while(t--)
	{
		scanf("%ld",&n);

		if(n&1 || n<2)
		{
			printf("0\n");
			continue;
		}

		n=(n/2) - 1;

		printf("9");

		while(n--)
		printf("0");

		printf("\n");
	}

	return 0;
}
//