EDITORIAL for YVNUM (Unofficial)

lovemaydie · December 24, 2018, 11:21am

PROBLEM LINK:

Practice

Contest

Author:
deadwing97

Editorialist (Unofficial):
Abhishek Mohanty

DIFFICULTY:

Easy

PREREQUISITES:

Modular Arithmetic

PROBLEM:

Given N.
Compute all its distinct left shifts and append them together in the same order. Finally find the mod of the resulting number wrt 1000000007

For example, if N=123, the left shifts are 123,231,312 and thus Y_N = 123231312.

output = Y_N % (10^9+7) = 123231312

EXPLANATION:

Constraints

Here the number of digits in N can go upto 10^5

i.e. N < \bf{10^{10^5}}

Result

Let

m = 10^9 + 7

a = no.\ of\ digits\ in\ N\ (this\ can\ go\ upto\ 10^5\ )

then
123231312 \% m = ((123 * 10^6)\%m + (231 * 10^3)\%m + (312 * 10^0)\%m) \%m

Thus the above output can be written in terms of the modulus of the individual left shifts as follows

Y_N = (\ \displaystyle\sum_{i=0}^{a - 1} 10^{ia} * N_{a - 1 - i}\ )\ \% m

If we can compute all the left shifts i.e N_i\ \forall i in \mathcal{O}(1) we can solve the problem

Computing left shifts

We will compute all the prefixes and suffixes modulus wrt m.

For N\ =\ 12345,\ a = 5

Prefixes modulus would be

 P[0] = 0 (for the full string)
 P[1] = 1 % m 
 P[2] = 12 % m 
 P[3] = 123 % m
 P[4] = 1234 % m
 P[5] = 12345 % m

Suffixes modulus would be

 S[1] = 5 % m 
 S[2] = 45 % m 
 S[3] = 345 % m 
 S[4] = 2345 % m 
 S[5] = 12345 % m

All the left shifts can now be computed as

N_i\ =\ (S[a - i] * 10^i + P[i])\ \% m

Complexity:

We first compute the prefixes and suffixes modulus with \mathcal{O}(a)

We then compute all the left shifts with \mathcal{O}(a)

We then compute Y_N where the computing 10^{ia} will cost \mathcal{O}(log a) and the loops will cost \mathcal{O}(a)

Thus complexity of algorithm is \mathcal{O}(aloga)

where a = \mid N\mid = 10^5

EDITORIALIST’S SOLUTION:

Solution

PS : Its my first ever post on codechef, please bear with me if I violated any standards

Happy Coding

arnavvarshney · December 24, 2018, 11:28am

Nice one!!

pavitra_ag · December 24, 2018, 1:00pm

code Why is my solution giving TLE I also followed as explained in editorial

lovemaydie · December 24, 2018, 1:17pm

sep(i,l-2,-1){
s2+=s1;
}
appending string takes linear time. So the operation inside takes O(|n|) and the loop itself is running |n| times. Thus complexity becomes O(|n|^2)

frextrite · December 24, 2018, 4:21pm

Any ideas on why does this solution give a TLE?

lovemaydie · December 24, 2018, 9:56pm

Yes, the line
Y = ( Y + ( k_shift[i] * power((ll)10, digits * (digits - i - 1)) ) MOD ) MOD;

is the source of problem. digits is declared as int, so multiplying digits with itself can give rise to 10^10 in the worst case which will become negative, given it is int. The power function never completes as it keeps computing negative powers (infinite recursion). Thus TLE.

Make it
Y = ( Y + ( k_shift[i] * power((ll)10, (ll)digits * (digits - i - 1)) ) MOD ) MOD;
and it will work.

PS : I would like to appreciate, you have written really clean and neat code.

partheshsoni · December 24, 2018, 10:23pm

Why is my solution giving wrong answer?

int test=sc.nextInt();
      for (int q0=0; q0<test; q0++) {
        int n=sc.nextInt();
        String shifts[]=new String[(int)Math.log10(n)+1];
        int nod=(int)Math.log10(n)+1;
        int narr[]=new int[nod];
        int exp=n;
        for(int i=nod-1; i>=0; i--){
          int temp=exp%10;
          narr[i]=temp;
          exp/=10;
        }
        shifts[0]=Integer.toString(n);
        String ns=Integer.toString(n);
        for (int i=1; i<nod; i++) {
          //int tarr[]=new int[nod];
          String ts=(ns.substring((i), (ns.length())));
          ts+=ns.substring(0, i);
          shifts[i]=ts;
        }

        int result=0;
        int mod=1000000007;
        for (int i=0; i<nod; i++) {
          result=(result+(Integer.parseInt(shifts[i])*(int)Math.pow(10, (nod-1-i)*nod))%mod)%mod;
        }
        /*String str = String.join("", shifts);
        BigInteger bi=new BigInteger(str);
        BigInteger mm=new BigInteger("1000000007");
        BigInteger result=bi.mod(mm);*/
      w.println(result%mod);
      }

ankush_953 · December 25, 2018, 12:31am

Short, Concise and Clear. Thank you so much

lovemaydie · December 25, 2018, 2:20am

int n=sc.nextInt();
int in java can take integers only upto 10^9. We can get a number of the value 10^(10^5) ie it can have 10^5 digits in itself. The input will be wrong in such cases. Thus WA. Try using String for taking the input.

Ex where it will fail is for n = 9999999999999999999999999999999999999999999

goldy06 · December 25, 2018, 3:51am

Can someone help in figuring out which part is Leading to TLE, I think I have maintained the time complexity of nlogn through out.

void solution() {

	String str = nln();
	char[] N = str.toCharArray();
	int n=N.length;
	long[] p=prefix(N);
	long[]s=suffix(N);
	long res=0;
	for(int i=n-1;i>=0;i--)
	{
		long pres = mul2(add(mul2(s[i], pow(10, i)), p[i]), pow(10, n*(n-1-i)));
		res = add(res, pres);
	}
	pn(res);
}

public long[] prefix(char[] N) {
	long[] p = new long[N.length];
	for (int i = 1; i < N.length; i++)
		p[i] = add(mul2(p[i-1], 10), (long)(N[i-1]-'0'));
	return p;
}

public long[] suffix(char[] N) {
	long[] s = new long[N.length];
	s[N.length - 1] = N[N.length - 1] - '0';
	for (int i = N.length - 2; i >= 0; i--) {
		s[i] = add(mul2(N[i]-'0', pow(10, N.length - 1 - i)),s[i+1]);
	}
	return s;
}

public long pow(int x, int n) {
	if (n == 0 || n == 1)
		return n == 0 ? 1 : x;
	return n % 2 == 0 ? mul2(pow(x, n / 2), pow(x, n / 2)) : mul3(x, pow(x, n / 2), pow(x, n / 2));
}

public long add(long a, long b) {
	return ((a % mod) + (b % mod)) % mod;
}
public long mul2(long a, long b)
{
	return ((a % mod) * (b % mod)) % mod;
}
public long mul3(long a, long b, long c)
{
	long i=1;
	i=mul2(a, i);
	i=mul2(b,i);
	i=mul2(c,i);
	return i;
}

frextrite · December 25, 2018, 12:17pm

Thanks! Worked like a charm. And I’d like to appreciate your debugging skills. I spent a lot of time debugging but couldn’t find the problem.

lovemaydie · December 25, 2018, 1:17pm

public long pow(int x, int n) {
if (n == 0 || n == 1)
return n == 0 ? 1 : x;
return n % 2 == 0 ? mul2(pow(x, n / 2), pow(x, n / 2)) : mul3(x, pow(x, n / 2), pow(x, n / 2));
}

This function is consuming your complexity.
Change the line
return n 2 == 0 ? mul2(pow(x, n / 2), pow(x, n / 2)) : mul3(x, pow(x, n To long tmp = pow(x, n / 2); return n 2 == 0 ? mul2(tmp, tmp) : mul3(x, tmp, tmp);

lovemaydie · December 25, 2018, 1:17pm

This will probably work. Please have a try and let us know. The logic is we compute the power and multiply it, saving the time to compute it again as multiplication is O(1) operation. But you are computing it twice which will make the complexity O(n) instead of O(logn).

savaliya_vivek · December 25, 2018, 1:30pm

why I am getting TLE in this code??

https://www.codechef.com/viewsolution/22075846

lovemaydie · December 25, 2018, 2:20pm

for j in range(l-1):
s=str[1:l]
s=s+str[0]
str=s;
my_list=my_list+[str]
First of all you forgot to you “j” inside the loop and s=str[1:l] will take linear complexity(O(l)) and the loop is running in O(l). Thus overall complexity becomes O(l^2)

goldy06 · December 25, 2018, 3:30pm

yeah didnt pay attention to that, but the code is still getting TLE

goldy06 · December 25, 2018, 3:35pm

i am creating a suffix array which is different than the suffix array mentioned in the editorial,I dont really think that is leading to TLE.

savaliya_vivek · December 25, 2018, 4:04pm

Thanks lot!
i don,t know str[1:l] has linear complexity.

lovemaydie · December 25, 2018, 9:26pm

I saw you have submitted it successfully. You precomputed the powers of 10. Maybe its a difference in the strict time limits for different languages!

adshin21 · December 26, 2018, 2:22am

The very same algo is implemented in python2 ( pypy2 ) in case of any help.

link text

PS: PYTHON 3 is denying it.

Any suggestions regarding code are welcome.