https://www.codechef.com/MACE2021/problems/MCODE03

PROBLEM LINK: Contest Page | CodeChef

Practice

Author: Setter’s name

Tester: Tester’s name

Editorialist: Editorialist’s name

DIFFICULTY : INTERMEDIATE

PREREQUISITES:

Nill

PROBLEM:

Harry Potter and his friends are hell bent on stopping the evil sorcerer Voldermort and his allies. Harry has to find one last horcrux safely guarded behind Hades gate .The key to open the door is solve a riddle. In front of the gate numerous cards have been laid out with numbers on them. The riddle to determine the minimum number of swaps so that differences between adjacent numbered cards are minimal throughout the set of cards. Guide Harry through this quest because time is running out.

#QUICK EXPLANATION:

The solution is sort the array in ascending order with minimum swaps. In a sorted array the difference between the element will be minimal

#EXPLANATION:

Assume that the numbers in card are elements of array arr

  • For each index in arr[].
  • Check if the current element is in it’s right position or not. Since the array contains distinct elements from 1 to N, we can simply compare the element with it’s index in array to check if it is at its right position.
  • If current element is not at it’s right position then swap the element with the element which has occupied its place.
  • Else check for next index.

SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>

using namespace std;

bool __cmp(int a,int b){

return a>=b;

}

int helper(int curr,int idx,vector&visit,int len,map<int,int>&mp,vector&cp){

if(visit[idx])

return len-1;

visit[idx]=true;

return helper(cp[mp[curr]],mp[curr],visit,len+1,mp,cp);

}

int ctSwp(int n,vector&arr,vector&cp,int ans=0){

map<int,int> mp; for(int i=0;i<n;i++) mp[arr[i]]=i;

vector visit(n,false);

for(int i=0;i<n;i++)

if(visit[i]==false)

ans+=helper(cp[i],i,visit,0,mp,cp);

return ans;

}

int main() {

int n; cin >>n;

vector arr(n); for (int i=0;i<n;i++) cin >> arr[i];

vector inc(arr);sort(inc.begin(),inc.end());

vector dec(arr);sort(dec.begin(),dec.end(),__cmp);

printf("%d\n",min(ctSwp(n,arr,inc),ctSwp(n,arr,dec)));

return 0;

}

Tester's Solution

Same Person

Editorialist's Solution

Same Person