getting WA for SGARDEN

general
1

please help me in finding the reason for this code showing WA

#include<stdio.h>

int main()
{
int t;
long long int divisor,a,dividend,lcm,n,i,length,s;
scanf("%d",&t);
while(t)
{

scanf("%lld",&n);
long long int visit[n+1],arr[n+1];
for(i=1;i<=n;i++)
{
    scanf("%lld",&arr[i]);
    visit[i]=0;
}
lcm=1;
for(i=1;i<=n;i++)
{
    if(visit[i]==0)
    {
        length=1;
        visit[i]=1;
        s=arr[i];
        while(i!=s)
        {
            visit[s]=1;
            length++;
            s=arr[s];
        }
        if(length<lcm)
        {
            a=lcm;
            lcm=length;
            length=a;
        }
        dividend=length;
        divisor=lcm;
        do
        {
            a=dividend%divisor;
            dividend=divisor;
            divisor=a;

        }while(divisor!=0);
        lcm=(length*lcm)/dividend;

    }
}
lcm%=1000000007;
printf("%lld\n",lcm);
t--;
}
return 0;

}

2

is the multiplication process if overflowing? If yes, how can I control it in C++?

3

Go through below link and try to figure out where’s bug in your code… :slight_smile:

http://discuss.codechef.com/questions/47240/sgarden-editorial

4

Thanks, but I have read the tutorial. and i am getting correct answers for all the three test cases given

5

****Challenge 2 : Focus this part would clear your doubt i think. :slight_smile:

Finding the lcm of the lengths.
Since this can be very large number , you need to be extremely careful in many languages about this because of the size limit of the data types.
So , for every length of the cycle we got , we need to separate it in terms of prime numbers alone i.e. length = p1^e1 * p2^e2 … pk^ek , where pi is prime number and ei is the maximum power of each prime number.
We need to maintain a global array of prime numbers in which we will keep the maximum value of power of every prime numbers.From this step we are finding lcm. Finally , when we have got the array , we will find the lcm by multiplying every prime number raised to it’s maximum power modulo given_mod.****

1 Like
6

but breaking such a large number into its prime factors… i mean yes we can stop at <=sqrt(num)but still…

7

and how will we store the result in c++? using array woulb be much complex??

8

One way is store all cycles in separate array… and process iteration and use %mod after every cycle…

9

I am sorry but I still don’t get it… thanks anyways… :slight_smile:

10

@nadimayaz I followed your suggestions and wrote a new code… I have checked it for the given test cases and gone through it multiple times still I can’t find the error… But I am getting WA… Please if you can help!

http://www.codechef.com/viewsolution/4336385