FSTSQ - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Pavel Sheftelevich
Tester: Sergey Kulik
Editorialist: Pawel Kacprzak

DIFFICULTY:

Easy

PREREQUISITES:

Adhoc

PROBLEM:

This problem is very simple stated. You are given a positive integer X and you want to compute its square. The good thing is that X consists only of N repetitions of the same digit. Sounds very simple, but the problem is that X can be very large here. In all subtasts, you have to handle at most 20 test cases. In order to return the result, you are asked to compute its hash with the given hash function. Since this can be done in linear time in terms of the length of the result, from now, we assume that you only need to compute the result as X \cdot X.

QUICK EXPLANATION:

Since squaring a number is multiplying it by itself, use long multiplication, which is sometimes called grade-school multiplication or Standard Algorithm, and speed up the computation using prefix and suffix sums of digits of the intermediate result.

EXPLANATION:

SUBTASK 1

In the simplest subtask, since N is at most 9, we know that X fits in 32-bit integer and hence, the result fits in 64-bit integer, so you can compute it as the product of two 32 bit integers.

SUBTASK 2

In the second subtask, N is at most 100, so the previous method cannot be used here. The good news, that N is not as big to prevent us from using standard, taught in elementary school, long multiplication. Using this method, we can easily compute the result for a single test case in O(N^2) time.

SUBTASK 3

In this subtask, we have N up to 2 \cdot 10^4, and you can solve this task using any reasonable speed up of a quadratic multiplication algorithm, so in other words, you can solve the multiplication of two long number problem in general. This can be done, probably in the easiest way, by representing X in some significantly larger base than 10 and then applying the standard long multiplication algorithm. Other, well-known methods, for multiplying fast two long numbers are FFT and Karatsuba algorithm, but since they are not so easy to implement, they are not so good choices here.

SUBTASK 4

In the last subtask, you have to deal with a really big number, consisting of up to 10^6 digits, and any of above methods will not work here. In order to solve this problem, we will strongly use the fact that X consists of the same digit repeated many times. Let’s take a closer look at the long multiplication algorithm:

                                                         d d ... d d d = X
                                                       * d d ... d d d = X
                                                         -------------
                                         m[k] m[k-1] ... m[3] m[2] m[1]
                                    m[k] m[k-1] ... m[3] m[2] m[1]
                               m[k] m[k-1] ... m[3] m[2] m[1]

                               .
                               .
                               .
     m[k] m[k-1] ... m[3] m[2] m[1]</sub> 
m[k] m[k-1] ... m[3] m[2] m[1]</sub>

Let M = d \cdot X and m[k], m[k-1], \ldots, m[1] be the digits of M. First important thing to notice, is that M can have N or N + 1 digits. Now, in order to get the result, we need to compute the following sum: M + 10 \cdot M + 10^2 \cdot M + \ldots. We can do this by accumulating the sum of each column from above schema independently. Notice that, the exact digits we need to accumulate in a certain column, depends only on the number of digits of M.

After that, in order to get the final result, we have to normalize the results from each column to base 10. This is easy to do by iterating over sums of columns from right to left, and computing for each one its sum modulo 10 as the digit corresponding to this column in the result, and carrying the outcome of dividing this sum by 10 the the next column.

However, if we accumulate the sum of each column naively, the method has quadratic time complexity, which is too much for this subtask. In order to speed it up, let’s take a closer look at the above adding schema. The result for each column is the sum of the first l digits of M for some l or the sum of the last l digits of M for some l. So in order to get the sum of each column, we can first precompute prefix sums and suffix sums of digits of M and then we can get the sum for each column in constant time, which is a big speed up over summing these digits naively.

This method has linear time complexity, but be aware of the your implementation, especially avoid copying and reversing arrays. In addition, it is better to implement the solution using static array rather than dynamic ones.

AUTHOR’S AND TESTER’S SOLUTIONS:

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

RELATED PROBLEMS:

2

Another way of solving the large test case (10^6 digits) is to represent the number as 111…111(n times 1) x d. Now the square of the number is equal to square of(1111…111) x square of d.

As we know, square of 1111…111 always follows a fixed pattern of digits. We represent the square of 111…111 as a char array and then just use a standard digit multiplication algorithm to compute the result into another char array.

then it’s just finding the hash from the result array.
Hence, the entire problem is solved in 0(N).

Link to the solution: https://www.codechef.com/viewsolution/8631646

14 Likes
3

Getting tle in last subtask in O(n) complexity. link to my solution https://www.codechef.com/viewsolution/8634719

4

One difference to my implementation; You don’t have to use modulo each time when summing up the hash. In fact the sum fits into a long long, so computing the modulo once is enough. Maybe that’s already enough to pass.

5

Getting Access Denied when trying to access author’s and tester’s solution.

6

please someone tell me why i am getting WA…please help…

7

awsm solution @gnsp… (y)

8

Why i am getting WA. I can’t get my error . Although test cases work well. Please see this:
https://www.codechef.com/viewsolution/8631377

9

Plz tell problem in my code.all the test cases are working http://ideone.com/2yRhIp

10

I am calculating the square in O(N).
But my last test case is still giving TLE. Help Anyone? :slight_smile:

Link to solution: https://www.codechef.com/viewsolution/8639946

11

Try changing t2 = (s[i]*p[siz-i])%MAXV; to t2 = (s[i]*p[siz-i]); Changing that redundant mod operation and using unsigned long long in inplace of signed long long int worked for me for the last case :slight_smile:

12

Thanks :slight_smile: It worked!

13

@gnsp

I used the same logic but I still don’t know why does my code not give a correct answer for at least the 1st 3 subtasks. Given below is the link to my solution. I am not able to find the test case for which my code goes wrong. Please help me out.
https://www.codechef.com/viewsolution/8640859

14

My program is working well on pc,but is giving runtime error after submisson.Please tell me what is error in my code http://ideone.com/J6pQKI

15

I got the error in your logic. You are assuming that the square of 111…111(n times) is 1234…n…4321. But that’s correct only upto n=9.

For example square of 111111111111111 (1 repeated 15 times) is 12345679012345654320987654321.

In fact the pattern is implemented like the following:

16 

const char *pat1 = "123456790";
const char *pat2 = "987654320";

int setNum(int n){
	int len = n*2-1;
	int b = len/9;
	int rm = len%9;
	int ind;
	if(b%2==1) rm += 9;
	b /= 2;
	ind = 0;
	for(int i=0; i=1; i--)
		num[ind++] = char('0'+i);
	num[ind-1] = '0';
	for(int i=0; i<b; i++)
		for(int j=0; j<9; j++)
			num[ind++] = pat2[j];
	num[ind-1] = '1';

	return len;
}