Kindly help me with the solution of this problem from IIT BHILAI coding contest
Contest Page | CodeChef.
Thanks in advance…
@ssrivastava990 @shubham_avasth @taran_1407 @shashwat07…kindly help me if you find time…
1 Like
Anyone else interested kindly help me
Thanks for your response Sir. Hope someone else sees this…
Well, you can make 2D dp[i][j] which denotes the minimum number of changes you need to make in array [1..i] such that you have atmost j indices satisfying that condition(A_k != A_{k+1}). Then you have the recursion: dp[i][j] = \min\limits_{x=0}^{i-1} dp[i-x-1][j-1] + x+1-f, where f denotes the frequency of element which occurs maximum number of times. What I am doing here is that I am considering the interval [i-x, i] with same element, finding changes in this interval and then using pre-computed answer for [1..i-x-1].
You can construct this dp in O(K*N^2*log(N)).
AC Code
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--)
{
int n, k;
cin >> n >> k;
int arr[n+1];
int i;
for(i=1;i<=n;i++)
cin >> arr[i];
int dp[n+1][k+1], freq[1001] = {0};
int j;
for(i=0;i<=n;i++)
for(j=0;j<=k;j++)
dp[i][j] = 1e9;
set<pair<int, int>> s;
for(j=0;j<=k;j++)
dp[0][j] = 0;
for(i=1;i<=n;i++)
{
int cnt = freq[arr[i]];
if(s.find({cnt, arr[i]}) != s.end())
s.erase({cnt, arr[i]});
freq[arr[i]]++;
cnt = freq[arr[i]];
s.insert({cnt, arr[i]});
pair<int, int> p = *s.rbegin();
dp[i][0] = (i - p.first);
}
for(i=1;i<=n;i++)
for(j=1;j<=k;j++)
{
map<int, int> mp;
s.clear();
for(int x = 0; x < i; x++)
{
if(mp.find(arr[i-x]) != mp.end())
s.erase({mp[arr[i-x]], arr[i-x]});
mp[arr[i-x]]++;
s.insert({mp[arr[i-x]], arr[i-x]});
pair<int, int> p = *s.rbegin();
dp[i][j] = min(dp[i][j], dp[i-x-1][j-1] + x+1-p.first);
}
}
cout << dp[n][k] << '\n';
}
}
4 Likes
Aaareww Sir,many many thanx