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

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

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.

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;

}

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

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

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.

kimbbakar · July 14, 2014, 10:56pm

Can anyone help me please to find out what’s the mistake of my code?

Thanks in advance

nisargshah95 · July 15, 2014, 12:33am

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?

adarshhsingh · July 15, 2014, 12:46am

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

priyankpalod · July 17, 2014, 12:27am

I have used the Exact Same Logic as described above.
Someone Please find the mistake in the code.
http://www.codechef.com/viewsolution/4337300

almer · July 17, 2014, 6:46am

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!

agk16 · July 18, 2014, 12:05am

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;

}

kavyanr · July 23, 2014, 2:00am

Why does it show wrong answer when output for all tried test cases is coming out correct?

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

rach8 · July 29, 2014, 1:03pm

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

makeitdonesolo · August 24, 2016, 8:27am

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?

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