YVNUM Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest

Author and Editorialist: Hussain Kara Fallah
Tester: Michael Nematollahi

PREREQUISITES:

NONE

PROBLEM:

Given a decimal integer N (with no zeroes at all even as intermediate digits). Consider all left cyclic shifts of N. The left cyclic shift is the operation of removing the leftmost digit from the number and appending it to the end.

Suppose N = 123 then all left cyclic shifts are {123,231,312}. So you start with N and repeat the mentioned operation N-1 times.

Yalalovichik number of N is equal to the concatenation of all these cyclic shifts.

For the previous example:

Y = 123231312.

Given N, you need to compute the value of Y modulo 10^9+7

Length of N may reach 10^5

EXPLANATION:

Let’s assume that length of N is equal to L. We know that:

N = a_0*10^{L-1} + a_1*10^{L-2} + a_2*10^{L-3} + ... + a_{L-1}

Assuming that digits are indexed from 0 to L-1 and from left to right. a_0 represents the leftmost digit. So let’s assume we need to do one shift operation, how to erase the leftmost digit?

N' = N - a_0*10^{L-1}

N' is equal to the value of N after removing the leftmost digit.

Let’s assume that the number resulting from the shift is M so:

M = N' * 10 + a_0

so now the number resulting from the shift is M we need to append it to our final answer. At the beginning the answer ans = N. To append it let’s shift ans to the left by L digits and simply add M.

ans = ans * 10^L + M

This is for the first shifting operation, to solve the problem repeat this operation N-1 times, but don’t forget to continue working on the shifted number.

We only need to calculate 10^L and 10^{L-1}, this can be done in linear time or faster if you prefer.

To maintain the answer modulo 10^9+7 we calculate the powers mentioned above modulo 10^9+7 and we always take our results modulo 10^9+7 after each subtraction or multiplication or addition.

Refer to the implementations for more details.

Total Complexity O(L)

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution

TESTER’s solution

1 Like
2

Thanks, very simple and good editorial.

3

A Python implementation.

4

Why did you do cur+=MOD ?

5

Thanks, for this easy explanation . i am constantly getting TLE for this but now i can solve this

6

i just want to know that is the constraint that N<=10^5 for integer or string of length 10^5

2 Likes
7

The link to my solution:

8

Can anybody help? Simple solution but doesn’t work: nEqSN1 - Online C++0x Compiler & Debugging Tool - Ideone.com

9

I was getting TLE as i was doing in O(L*L),now i can do it,good editorial.

10

It could be rewritten M = N * 10 - a_0 * (10^L - 1). So we only need to calculate 10^L.

And we can do it while calculating N.

12

I can understand the explanation and logic pretty well…but I am not getting anything seeing the solution… :disappointed_relieved::disappointed_relieved

1 Like
13

Nice Editorial :100:

14

have you been able to understand the reason??? I understand that it is to avoid negative number in the previous operation but how that happens I would also like to know.Please help us @watcher…
Thanks in advance

15

Hello,@itz_pankaj can you explain to me the cur+=MOD operation as well cur%=MOD operation??I get that these operations are compensating any negative result that may have been produced in previous step but not able to understand how it is being achieved.

16

my code is correct but i am getting wrong answer can anyone please point out my mistake.

#include<bits/stdc++.h>
using namespace std;
long long int m=1000000007;
long long int power(int x, int y)
{
long long int res = 1;

while (y > 0) 
{ 
    
    if (y & 1) 
        res = (res*x)%m; 

    
    y = y>>1; 
    x = ((x*x)%m);  
} 
return ((res)%m);

}
int main()
{
long long int t,i,j,d,k,n;
cin>>t;
for(i=0;i<t;i++)
{
cin>>n;
n=abs(n);
int c=0;
int x=n;
while(x!=0)
{
c++;
x=x/10;
}
x=n;
int a[c],c1=0;
while(x!=0)
{
d=x%10;
a[c1]=d;
c1++;
x=x/10;
}
x=power(10,c);
long long int ans=n;
long long int nn,mm;
for(j=1;j<c;j++)
{
nn=(n-(a[c-j](power(10,c-1))%m))%m;
nn=((nn10)%m+a[c-j])%m;
cout<<nn<<endl;
ans=((ans*x)%m+nn)%m;
n=nn%m;
ans=ans%m;
}
cout<<ans<<endl;
}
return 0;
}

17

I will see your code…but I would advise you for this problem that you first think out the algo without thinking about Modulus.Then after you have done so…apply modulus at each stage of any operation
you do.I hope you will get AC

19

i am getting runtime error … dont know why…
here is code

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long int mod = 1000000007;
    long long int arr[100099];
    arr[0] = 1;
    for (int i = 1; i < 26; i++)
    {
        arr[i] = (arr[i - 1] * 10) % mod;
    }
    int t;
    cin >> t;
    while (t--)
    {
        string n;
        cin >> n;
        string answer = "";
        for (int i = 0; i < n.length(); i++)
        {
            string x = "";
            for (int j = i; j < n.length(); j++)
            {
                x += n[j];
            }
            for (int j = 0; j < i; j++)
            {
                x += n[j];
            }
            answer += x;
        }
        long long int to_out = 0;
        string reverse = "";
        for (int i = answer.length() - 1; i >= 0; i--)
        {
            reverse += answer[i];
        }
        for (int i = 0; i < reverse.length(); i++)
        {
            int temp = reverse[i] - '0';
            int tejus = arr[i];
            //    cout << temp << " " << tejus << "\n";
            tejus = (tejus * temp) % mod;
            to_out = ((to_out % mod) + (tejus % mod)) % mod;
        }
        cout << to_out << "\n";
    }
    return 0;

}

20

This is my briefly-commented solution using prefix-sum to calculate each shifted value by separating it into two parts.