Unlock coding problem(in STL) concept doubt

#1

In this problem we are supposed to print the largest permutation possible by doing exactly k swaps for the bomb diffuse code. I am not able to understand the approach that you took to solve this problem. I unlocked the editorial but im still not able to understand why your logic is working. How did you solve this problem elaborate in laymens terms.

#2

#include<bits/stdc++.h>
#include
using namespace std;
void swap(int *a,int *b){
int temp = *b;
*b = *a;
*a = temp;
}
int main() {
long long int n,k;
cin>>n>>k;
int a[n];
map<int,int>mp;
for(int i=0;i<n;i++)
{
cin>>a[i];
mp[a[i]]= i;
}
for(int i=0;i<n;i++){
if(k<=0)
break;
if(a[i]==n-i)
continue;
int h =n-i;
int pos = mp[h];
mp[a[i]]=pos;
mp[a[pos]] = i;
swap(a[i],a[pos]);
k–;
}
for(int i=0;i<n;i++)
cout<<a[i]<<" ";

return 0;

}
first i have stored every element and its index in a map and it is paermutation a N naturak number hence we have to check if the element is (n-i) or not if it is not then you have to swap the value of the array

#3

what problem you are having with the editorial ?

#4

my problem is that i don’t understand what concept did you use to solve this problem, the editorial solution is very random, how did you think of this solution, what concept did you use?

#5

for largest permuation array must be in decsending order. Store initial position of every element in a map. then start with largest element see if this is in the correct position of largest permutation if not then swap the value stored in that position of intial array with this number. this can be easily implemented using map and array. if k swaps are over print the array as it is.

#6

SOLUTION passing all the testcase !

#7

what will be the case if
after 2 swap array is sorted in descending order and total swap give is k = 4;

then how should we handle ?

#8

You dont need to use all the swap

#9

but it is mentioned in question exactly k swap is compulsory.

The defusal code is the largest permutation possible by doing exactly K swaps among a pair of the given permutation.

#10

then after your array is sorted in descending order just swap last and 2nd last element… for rest of k… if left k is even answer will be same if odd last element will come in place of 2nd last…

#11

i didn’t getting following meaning

if left k is even answer will be same if odd last element will come in place of 2nd last…

#12

suppose after largest permuation is build x swaps left. then what we can do is swap last and 2nd last element till all swaps are consumed.

#13

Why are we using hashing to find position of (n-i), cant we use binary search for that?

#14

how can i debug

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
ll n,k,hold,temp;
cin>>n>>k;
ll arr[n];
unordered_map<int,int>map;
for(ll i=0;i<n;i++)
{
cin>>arr[i];
map.insert(make_pair(arr[i],i));
}
ll m=0;
while(m<n && k>0)
{
hold=map[n-m];
if(hold==m)
{
m++;
continue;
}
else
{
temp=arr[m];
arr[m]=arr[hold];
arr[hold]=temp;
map.insert(arr[hold],hold);
map.insert(arr[m],m);
m++;
k–;
}
}
for(auto x:arr)
cout<<x<<" ";

return 0;

}