i am still unable to find tle in this code…could anyone spare some time to give me suggestions?thanking you in advance!
#include<stdio.h>
void main()
{
int t;
scanf("%d",&t);
while(t–)
{
int n,cc,mc,j;
scanf("%d %d %d %d",&n,&j,&cc,&mc);
int b[2*n],i,flag=0;
for(i=0;i<n;i++)
{ b[i]=b[n+i]=i; }
for(i=cc;i<(cc+n);i+=j)
{
if(b[i]==mc)
{ flag=1;
break;}
}
if(flag==1)
printf(“YES\n”);
else
printf(“NO\n”);
}
}
link for the problem is https://www.codechef.com/problems/CVDRUN
You need to find whether
(X+K)%N equals to Y
Let’s say you added K to X a times. So, you have the value X+aK. You need to check whether this expression gives a remainder Y when divided by N. In other words, we need to check whether
X+aK = Y+bN
Rearranging, we get
X-Y= bN-aK
Adjusting the constants, we get
X-Y= b’N+a’K
Above equation is a linear Diophantine equation which has an integral solution iff X-Y is divisible by gcd(N,K).
So, to solve the problem, all you need to do now is to check whether abs(X-Y)%gcd(N,K) is 0. If it’s 0, then YES, else NO.
You can use this one to reduce time complexity to O(lg n)
In second for loop :
for(i=cc; i<(cc+n);i+=j)
When j is 0, it will run infinitely giving tle.
sure…thanks alot
going to try…if failed,will ask u for one more time.
i see… :)thanks for this one!!!