You are not logged in. Please login at www.codechef.com to post your questions!

×

YVNUM Editorial

1
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

This question is marked "community wiki".

asked 23 Dec '18, 23:10

deadwing97's gravatar image

3★deadwing97
1081032
accept rate: 0%

edited 25 Dec '18, 04:19

admin's gravatar image

0★admin ♦♦
19.8k350498541

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$.

(26 Dec '18, 01:06) eugalt3★

Thanks, very simple and good editorial.

link

answered 25 Dec '18, 20:55

me17b016's gravatar image

4★me17b016
412
accept rate: 0%

link

answered 26 Dec '18, 09:00

eugalt's gravatar image

3★eugalt
2827
accept rate: 4%

Why did you do cur+=MOD ?

link

answered 26 Dec '18, 12:44

skshreyansh's gravatar image

3★skshreyansh
1
accept rate: 0%

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

link

answered 26 Dec '18, 19:56

itz_pankaj's gravatar image

2★itz_pankaj
11
accept rate: 0%

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

link

answered 26 Dec '18, 20:30

akashad1998's gravatar image

3★akashad1998
1
accept rate: 0%

link

answered 29 Dec '18, 03:52

executable's gravatar image

3★executable
11
accept rate: 0%

Can anybody help? Simple solution but doesn't work: https://ideone.com/nEqSN1

link

answered 04 Jan, 17:45

shardic's gravatar image

2★shardic
22
accept rate: 0%

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

link

answered 20 Jan, 10:58

salmanfarsi's gravatar image

3★salmanfarsi
0
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,684
×74
×51

question asked: 23 Dec '18, 23:10

question was seen: 2,298 times

last updated: 20 Jan, 10:58