SGARDEN - Editorial

devuy11 · July 14, 2014, 3:01pm

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 = p₁^e₁ * p₂^e₂ … p_k^e_k , where p_i is prime number and e_i 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 2² * 3¹ * 5¹ = 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

sagar0430 · July 14, 2014, 3:12pm

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

himanshujaju · July 14, 2014, 3:18pm

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

ravi0213 · July 14, 2014, 3:22pm

java biginteger is really useful

karankapoor · July 14, 2014, 3:25pm

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;
}

muttakyn · July 14, 2014, 3:29pm

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

gagaboy · July 14, 2014, 3:30pm

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

himanshujaju · July 14, 2014, 3:31pm

use prime factorization to find LCM.

achaitanyasai · July 14, 2014, 3:38pm

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.

cherry_jain · July 14, 2014, 3:49pm

Won’t taking mod each time give the wrong answer?

devuy11 · July 14, 2014, 3:54pm

Hi All , The last pseudo code is wrong and is mentioned above . Even the function name “Wrong_Solution” suggests that it is wrong!

gagaboy · July 14, 2014, 3:56pm

slow logic and the use of swap function is making it slower
and ur using brute force…think of some other logic

shoumik · July 14, 2014, 3:57pm

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;

}

yoyo123 · July 14, 2014, 4:01pm

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

ants29 · July 14, 2014, 4:08pm

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

achaitanyasai · July 14, 2014, 4:11pm

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

diptesh1ce3 · July 14, 2014, 4:28pm

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.

ag0965 · July 14, 2014, 4:57pm

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

minato_namikaz · July 14, 2014, 5:02pm

you need to do inverse to calc division modulo

galactocalypse · July 14, 2014, 6:34pm

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.