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

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

Cycles finding is similar to this : http://www.codechef.com/problems/PCYCLE

1 Like

java biginteger is really useful :smiley: :stuck_out_tongue:

3 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

use prime factorization to find LCM.

1 Like

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

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

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;

}

one mistake which I found is overflow in variable x .There may or may not be other mistakes.

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

(x/y)%z != (x%z)/(y%z)

1 Like

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

you need to do inverse to calc division modulo

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
//