i used lcm(ans,b)=((ans%1000000007)*(b%1000000007)/(gcd(ans,b)))%1000000007;
whats wrong int it why it always gave wrong answer
http://www.codechef.com/viewsolution/4298756
Error in that pseudo code is, You can’t take modulo just when LCM is greater then modulo.
That will and result in invalid LCM and hence invalid answer.
1 Like
For everyone using modular multiplicative inverse to find the LCM:
The reason it doesn’t work is because the GCD is affected once modulus is applied.
This is what I was doing:
Let prod = 1
for each length l:
g = gcd(prod, l)
ig = mod_inv(g, MOD)
prod = (prod*l%MOD)*ig%MOD
I spent the entire time thinking the last line was the root of the problem when actually it was the GCD part. When prod exceeds MOD, we end up calculating gcd(prod%MOD, l) which in turn calculates prod%MOD%l which is why we get a WA. I wish I could prove this mathematically. Sigh.
Cursed my stars and my college and everything else for days before finally realizing this just moments back.
3 Likes
Can anyone help me please to find out what’s the mistake of my code?
Thanks in advance 
In challenge 1, is it that while iterating the cycle, in whichever indices bandit 1 (for example) goes, the bandits at these indices also follow the same number of iterations before reaching their original position? Is that why there is visited[s]=1 in the iteration loop?
Hi All , It will be of great help : if anyone can tell the bug in this code . I am getting WA : CodeChef: Practical coding for everyone
I have used the Exact Same Logic as described above.
Someone Please find the mistake in the code.
http://www.codechef.com/viewsolution/4337300
Hi guys, nobody has time to read your code. I’d suggest you to generate test data and compare your output with tester’s solution and debug on your own pace.
-
Python script to generate tests sgarden_gen.py
-
Tester’s solution SGARDEN.cpp
-
In linux you can compare two files with diff command. Simply run:
diff my_output.txt correct_output.txt
Happy coding!
Sir my solution is giving tle…why is it happening…
#include<stdio.h>
#define max 1000000007
long long int cal(long long int a[],long long int b[],long long int c[],long long int n,long long int ans)
{
long long int i,flag,flag1=0;
flag=0;
for(i=1;i<=n;i++)
{
b[a[i]]=c[i];
}
for(i=1;i<=n;i++)
{
c[i]=b[i];
if(b[i]==i)
{
flag++;
}
if(b[i]==a[i])
flag1++;
// printf("%lld ",b[i]);
}
if(flag==n)
return ans;
if(flag1==n)
{
ans++;
return ans;
}
else
{
ans++;
cal(a,b,c,n,ans);
}
}
int main()
{
int t;
scanf("%d",&t);
while(t–)
{
long long int i,n,a[100005],b[100005],c[100005],ans=1;
scanf("%lld",&n);
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
b[i]=i;
c[i]=i;
}
// printf("%lld\n",count);
ans=cal(a,b,c,n,ans);
printf("%lld\n",ans%max);
}
return 0;
}
Why does it show wrong answer when output for all tried test cases is coming out correct?
Why can’t we do it like this…
I am getting right output for the sample test cases, but WA.
int n,i,j,k; long long c=1;
scanf("%d",&n);
long long a[1000001],p[n],na[n];
for(i=1;i<=n;i++){
scanf("%ld",&a[i]);
p[a[i]]=a[i];
}//for
//change the positions accordingly
for(i=1;i<=n;i++){
na[i]=p[i];
}//for
for(j=1;j<=n;j++)
{
if(na[j]==a[j]){continue;}
else {for(k=1;k<=n;k++){na[k]=p[na[k]];}c++;}
}//forj
printf("%lld\n",c%1000000007);
for(i=1;i<=n;i++)
{
count=0;
j=i;
while(!visited[j])
{
visited[j]=true;
j=a[j];
count++;
}
if(count)
{
lcm=(lcm*count)/gcd(lcm,count);
}
}
Why does this give TLE?
take mod each time you calculate ans as it may return you a value that can’t be stored in long long variable too
ans = lcm(ans , L[i])%mod
java biginteger is really useful 
3 Likes
use prime factorization to find LCM.
1 Like
Won’t taking mod each time give the wrong answer?
3 Likes
Hi All , The last pseudo code is wrong and is mentioned above . Even the function name “Wrong_Solution” suggests that it is wrong!
slow logic and the use of swap function is making it slower
and ur using brute force…think of some other logic