Problem Statement: You have n people sitting around in a circle. Each person has a skill value arr[i]. You want to assign people to these tasks. The people chosen for a specific task must have all been sitting consecutively and their skill gap (maximum to minimum) must not differ by more than K. Also, each person must be assigned exactly one task. How many ways are there to assign tasks to all the people modulo 1e9+7 Two ways are considered different if person I and j are doing same task in different ways.
Example Input: n=2
k=2
arr[]= {1,2}
Sample Output: 2
Explanation: there are 2 ways, either 1 and 2 do the same task or not. Both are valid statements.
I am stuck in this question. Earlier I tried to solve it like this:
//assuming necessary header files
int solve(int arr[], int n, int k){
map<int,vector<int>> mp;
for(int i=1;i<n;++i){
int temp= abs(arr[i]-arr[i-1]);
if(temp<=k)[
mp[temp].push_back(arr[i]);
mp[temp].push_back(arr[i-1]);
]
}
int ans=0;
for(auto it: mp){
vector<int> p= it.second;
int szz= p.size();
ans+= 2*(szz*(szz-1))/2;
}
return ans;
}
int main() {
int n,k;
cin>>n>>k
int arr[n];
for(int i=0;i<n;++i){
cin>>arr[i];
}
cout<<solve(arr,n,k)<<endl;
return 0;
}
My approach was to store all the consecutive people having skill gap less than k to be kept in a key value pair and then return twice of each key-value pair's size. I got Wrong Answer verdict. Either I am unable to understand the question clearly or I have implemented it the wrong way. Can anyone please correct it and let me know the correct solution for the same? Thank you