Doubt in Problem-Sort the Array of Amritapuri Practice Round-6

Competitive Programming
1

I have a doubt in problem Sort the array- Link
How is just checking whether the product of the index at which the element is currently placed and the index at which it should be in sorted array is a perfect square, guarantees the solution of the problem. Can someone explain how is this code giving AC?

 #include <bits/stdc++.h>
  using namespace std;
  #define int long long
   bool isPerfectSquare(int x)
   {
   int sq=sqrt(x);
   return (x==sq*sq);
   }
    signed main() {
// your code goes here

int t,n;
cin>>t;
while(t--)
{
    cin>>n;
    int arr[n];
    vector<pair<int,int>> vect;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
        vect.push_back({arr[i],i+1});
    }
    bool flag=1;
    sort(vect.begin(),vect.end());
    for(int i=0;i<n;i++)
    {
        int x=(i+1)*(vect[i].second);
        if(isPerfectSquare(x)==0) 
        {
            flag=0;break;
        }
    }
    if(flag==1)
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
}
return 0;
}
1 Like
2

Suppose y*z=k1^2. Then we can derive the following two relations:

  • x*y=k2^2

  • x*z=k3^2, where x!=y!=z

We can assume x to be the desired index of any element a[y] in the sorted array, and y to be the original index.
Similarly, z would serve as any index such that a[y] can be swapped with a[z]. By above logic, if we can swap a[x] and a[z] (which we would have to do at least once to move it to the correct index), we can swap a[x] and a[y] as well. Therefore checking for x,y to be a perfect square should suffice.

1 Like