EDITORIAL for YVNUM (Unofficial)

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 :slight_smile:

Happy Coding

4 Likes

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

Any ideas on why does this solution give a TLE?

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);
      }

Short, Concise and Clear. Thank you so much :slight_smile:

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;
}

why I am getting TLE in this code??

CodeChef: Practical coding for everyone

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.

pls someone tell why i m getting WA, the approach is same as unofficial editorial
i think i m doing mistake in implementing modulo, pls check it once

#include<bits/stdc++.h>

using namespace std;

#define mod 1000000007

typedef long long int ll;

int main()

{
ll ten[100005];

ten[0]=1;

for(ll i=1;i<100005;i++)

ten[i]=(ten[i-1]*10)%mod;

ll t;

cin>>t;

while(t–)

{

char s[100005];

cin>>s;

ll m=0;

ll l;

for(l=0;s[l]!=’\0’;l++);

for(ll i=0;s[i]!=’\0’;i++)

m+= ( (s[i]-48) * ten[l-1-i] )%mod;

ll temp=m;

for(ll i=0;i<l-1;i++)

{

m=( ( (m-(s[i]-48) * ten[l-1]) %mod ) * 10 ) % mod+(s[i]-48)%mod;

m%=mod;

temp=( ( temp*ten[l])%mod+m)%mod;

}

cout<<temp%mod<<endl;

}

return 0;

}

Nice one!!

1 Like

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)

1 Like

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.

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

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.

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);

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

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)

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

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.

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