Unofficial Editorial For Yalalovichik Numbers (YVNUM) COOK101

Problem: [Problem Link][1]

Prerequisites: Basics of Modular Arithmetic

We will solve the problem by breaking into three parts:

Let MOD = 109+7

Part 1: Finding the MOD of large number

Let the given number be A, where |A| denotes the number of digits in A. Let Ai represents the ith digit and l = |A| then

A%MOD = Σ Ai×10l-i % MOD

= Σ (Ai×(10l-i % MOD))%MOD

For example

12345%MOD = (1×104)%MOD + (2×103)%MOD + (3×102)%MOD +(4×101)%MOD + (5×100)%MOD

One important point here is 10i is used many times, hence we can calculate and store them.

Here is my code example:


    vector<int> arr(100005);
    vector<ll> dig = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // for converting char to digits
    arr[0] = 1;
	for(int i=1, i < 100005; i++)
		arr[i] = ((arr[i-1]×10)%MOD);
	// let s contains the number in string format ( since number is very large) and l contains the length
	int mi = 0;
	for(int i = s.size()-1; i>=0; i--){
		mi += ((dig[s[i]-'0']×arr[l-i-1])%MOD);
	}
	mi = mi%MOD;

Part 2: Generating next shift from previous

For generating the next shift from previous shift

Anext = Aprev ×10 - 10l × Aprev1 + Aprev1

For Example :

23451 = 12345*10 - 105×1+1

= 123450 - 100000 + 1

Yeah, sure you should perform subtraction first and then multiplication to prevent overflow, but I used long long.

Here is my Code example


    int l = s.size();
    // for having the ith shift where mi contains the i-1th shift
    mi = (((mi×10)%MOD + dig[s[i]-'0'])%MOD - (dig[s[i]-'0']×arr[l])%MOD)%MOD;

Part 3: Combining the result

If you are with me till now, this part is the most simplest among the all. The idea is how you can generate the number using the digit. For example

12345 = (1×104) + (2×103) + (3×102) +(4×101) + (5×100)

= ((((( 1 ) × 10 + 2 ) × 10 + 3 ) × 10 + 4 ) × 10 + 5 )

For input 123, we can get the combine result as follows :

total = ((( 123 ) × 103 + 231 ) × 103 + 312 )

Working on the similar lines, you can combine the next shift with the previous result. Let total represent the total score till now, then combining process involves


    total = ((total×arr[l])%MOD + mi)%MOD;

Time complexity: ◯(n), where n = |N|

Code: [Solution Link][2]
[1]: https://www.codechef.com/COOK101A/problems/YVNUM
[2]: https://www.codechef.com/viewsolution/22071480

9 Likes

This is a nice approach.
Thank you !

Thanks for the “Part 2: Generating next shift from previous”, It seems so easy now! Thanks XD

This part idea I got from Rabin-Karp String Matching algorithm from CLRS

Can you tell me the mistake in this solution?

I converted it to a string first, performed the shift operation and then appended it to the original string. Kept repeating the same operation and then finally calculated the modulo. But it is giving WA.

The input number is so large that you cannot take the input as int. Second point I will like to mention that the number can 10^5 long, and appending all of the rotation will make the string 100005^100005 long which not feasible…so think of something else.