SGARDEN - Editorial

PROBLEM LINK:

Practice
Contest

Author: Dmytro Berezin
Tester: Shang Jingbo and Gerald Agapov
Editorialist: Devendra Agarwal

DIFFICULTY:

EASY

PREREQUISITES:

LCM of numbers.

PROBLEM:

There are N bandits from 1 to N. Given a permuatation of 1 to N which determines that the bandit at ith position should move to jth position. At every whistle the bandit staying on position i should run to the j-th position. Now you need to find minimum number of whistle such that each bandit is at it’s original location.

Quick Explanation

Find all independent cycle of rotation and then find the lcm of the length of each cycle.

Explanation

Cycle here denotes the positions with which a bandit at position i moves to come to position i.
For example : 2 3 1 5 4 [ Sample Test Case 2 ]
Bandit at position 1, 2 and 3 come to their original position after every 3 whistles.
Bandit at position 4 and 5 come to their original position after every 2 whistles.

Finding lcm will give you the minimum whistle required so that every bandit is in their original position. Proof is left as an exercise for the reader to complete it.

Challenge 1 : Finding the cycle lengths.

Cycle length can be found simply by iterating through each cycle.Please have a look at pseudo code for more insights.

Pseudo Code

Let Visited[] be 0 initialized.
Matching[] is the initial given array.
for(int i=1;i<=N;i++)
	if( Visited[i]==0 )  
		length =1,s=Matching[i];
		Visited[i]=1;
		//iterating the cycle
		while(  s != i )
			Visited[s]=1;
			length++;
			s= Matching[s];

Challenge 2 : 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.

For Example:

let the given array be
2 3 4 1 6 7 5 9 10 11 12 8 14 13

Cycle 1 : 2 3 4 1
Cycle 2 : 6 7 5
Cycle 3 : 9 10 11 12 8
Cycle 4 : 14 13

Length of Cycles are : 4,3,5 and 2
Max_Power_Of 2 is 2
Max_Power_Of 3 is 1
Max_Power_Of 5 is 1
So the Answer is 22 * 31 * 51 = 60

I will urge the readers to figure out the error in the given pseudo code below :

Wrong_Solution ( Length L[] ) //given array of lengths
	ans = 1
	for ( i = 1 ; i<=L.size() ; i = i+1 )
		ans = lcm ( ans,L[i] ) 
		if ans >= mod :
			ans %= mod

Complexity:

O(N) , you just need to find cycles in O(N) time and factorization is done in sqrt(N) time.

AUTHOR’S and TESTER’S SOLUTIONS:

Author’s solution to be uploaded soon.
Tester’s solution

12 Likes

sir my code gave me tle again and again… what should i improve ?

#include<iostream>
using namespace std;
long int a[100000];
long int b[100000];
long int c[100000];
long int t,ctr,i,flag,n,temp;
void swap(long int b[],long int c[])
{
 for(i=1;i<=n;i++)
 {
  temp=a[i];
  a[i]=b[i];
  b[i]=temp; 
 }
}
int main(void)
{
 ios_base::sync_with_stdio(false);
 cin.tie(NULL);
 cout.tie(NULL);
 cin>>t;
 while(t--)
 {
  flag=0;
  ctr=0;
  cin>>n;
  for(i=1;i<=n;i++)
  {
   cin>>a[i];
   b[i]=i;
  }
  while(!flag)
  {
   ctr++;
   ctr=ctr%(1000000000);
   for(i=1;i<=n;i++)
   {
    c[a[i]]=b[i];
   }
   swap(b,c);
   for(i=1;i<=n;i++)
   {
    flag=1;
    if(b[i]!=a[i])
    {
     flag=0;
     break;  
    }
   }
  }
  cout<<ctr+7<<"\n";
 }
 return 0;
}

I got WA multiple times :frowning: . I can not find out the bug.
my code:
http://www.codechef.com/viewsolution/4328586

Please guys help me here!
used the same logic!!
But my solution keeps getting WA… help!
http://www.codechef.com/viewsolution/4321429

Hai, I don’t know whether I can post this or not ,Here are some unofficial test cases categorised into small,medium,large.Who are getting mainly WA but also RTE,TLE,… can also check.You may need not worry about the constraints.the values are guarenteed to be in the given constraints.

5 Likes

I was getting RTE . will anyone please tell me why ?

#include<bits/stdc++.h>

using namespace std;
#define mod 1000000007
long long game[100009];
long long color[100009];
long long isp[100009];
long long ar[100009];
long long T;
vectoradj[100009];
vectorprimes[100009];
int members;
long long dfs(long long q)
{

color[q]=1;
for(long long aa=0; aa<adj[q].size(); aa++)
{
    if(color[adj[q][aa]]==0)
    {
        members++;
        dfs(adj[q][aa]);
    }
}

return members;

}

void sieve()
{
T=0;
isp[0]=0;
isp[1]=0;
long long i,j,s;
s=sqrt(100009);
for(i=2; i<=100009; i++)
{
isp[i]=1;
}
for(i=2; i<=s; i++)
{
if(isp[i]==1)
{
ar[T]=i;
T++;
for(j=i*i; j<=100009; j+=i)
{
isp[j]=0;
}
}

}

}

int main()
{
sieve();

long long test,x,value,start,group_member,in,ind,grp_value;
cin>>test;
while(test--)
{
    cin>>x;
    for(long long qq=1; qq<=x; qq++)
    {
        adj[qq].clear();
    }
    for(long long zz=1;zz<=100000;zz++)
    {
        primes[zz].clear();
    }
    memset(color,0,100000);
    memset(game,0,100000);
    for(long long  i=1; i<=x; i++)
    {
        cin>>value;
        adj[i].push_back(value);

    }

    ind=0;
    for(long long k=1; k<=x; k++)
    {

        members=0;
        if(color[k]==0)
        {
            in=dfs(k);
            ind++;
            game[ind]=in+1;

        }
    }




    int count_prime,sq;
    for(long long  s=1; s<=ind; s++)
    {

        grp_value=game[s];
     
        sq=sqrt(grp_value);

        for(long long t=0; t<=sq; t++)
        {
            count_prime=0;
            while(grp_value%ar[t]==0)
            {
               
                count_prime++;
               
                grp_value/=ar[t];
            }
            if(count_prime)
            {
                primes[ar[t]].push_back(count_prime);
               
            }

        }
        if(grp_value>1) primes[grp_value].push_back(1);
    }

    long long mul=1;
    long long  max,ss,xx;
    for( xx=2; xx<=100000; xx++)
    {
        max=0;
        if(primes[xx].size()>0)
        {
          
            for(ss=0; ss<primes[xx].size(); ss++)
            {
                if(primes[xx][ss]>max)
                {
                    max=primes[xx][ss];

                }
            }
            while(max--)
            {
                mul*=xx;
                mul%=mod;
            }

        }
    }
    cout<<mul%mod<<endl;


}
return 0;

}

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

please tell me what is wrong with my algorithm.
http://www.codechef.com/viewsolution/4308976

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

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 : http://www.codechef.com/viewsolution/4331278

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.

  1. Python script to generate tests sgarden_gen.py

  2. Tester’s solution SGARDEN.cpp

  3. 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?

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

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