Join Us
Loading Similar Posts
Entering edit mode
//phone pe team formation
#include <bits/stdc++.h>
using namespace std;
int func(int n, vector<int> vect, int k) {
vector<vector<int>> sort_vect;
int i=0;
sort(vect.begin(), vect.end());
while(i<n) {
int curr=vect[i];
int count=0;
while(i<n && curr==vect[i]) {
count++;
i++;
}
sort_vect.push_back({count, curr});
}
sort(sort_vect.begin(), sort_vect.end(), greater<vector<int>>());
vector<vector<int>> groups(k,(vector<int>(2,-1)));
int ans=0;
// min=1;
// max=6; 6-5,=>1, 1+5=>6
for(int i=0;i<sort_vect.size();i++) {
for(int j=0;j<k;j++) {
if(groups[j][0]==-1) {
ans+=sort_vect[i][0];
groups[j][0]=groups[j][1]=sort_vect[i][1];
break;
}
else {
if(sort_vect[i][1]<groups[j][1]-5 || sort_vect[i][1]>groups[j][0]+5) continue;
groups[j][0]=min(groups[j][0], sort_vect[i][1]);
groups[j][1]=max(groups[j][1], sort_vect[i][1]);
ans+=sort_vect[i][0];
break;
}
}
}
for(auto var:groups) {
cout << var[0] << " " << var[1] << endl;
}
return ans;
}
int main()
{
int n,k;cin >> n >> k;
vector<int> v(n);
for(int i=0;i<n;i++) cin >> v[i];
cout << func(n, v, k);
return 0;
}
Entering edit mode
//PhonePe Team formation
int32_t main(){
int n,k;cin>>n>>k;
int a[n];
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
int l=0,r=1;
int team=1;
while(l<n && r<n && team<=k){
if((a[r]-a[l])>5){
l=r;
team++;
// cout<<"l="<<l<<"r="<<r<<endl;
}
r++;
}
// cout<<"r="<<r<<endl;
cout<<r<<endl;
}
Will it work fine for all cases??
Entering edit mode
TC O(n2) DP solution:
#include<bits/stdc++.h>
#define null NULL
using namespace std;
int n,k,x;
map<int,int>mp;
vector<vector<int>>v,dp;
int fun(int i,int j)
{
if(j>k)return -1e9;
if(i==n)return 0;
if(dp[i][j]!=-1)return dp[i][j];
int ans=fun(i+1,j);
int cnt=0;
for(int l=i;l<n;l++)
{
if(v[l][0]-v[i][0]>5)break;
cnt=cnt+v[l][1];
ans=max(ans,cnt+fun(l+1,j+1));
}
return dp[i][j]= ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>k;
for(int i=0;i<n;i++)
{
cin>>x;
mp[x]++;
}
for(auto it:mp)v.push_back({it.first,it.second});
n=v.size();
dp.resize(n,vector<int>(k+1,-1));
cout<<fun(0,0)<<endl;
return 0;
}
Entering edit mode
TC O(10 *n*n)
#include<bits/stdc++.h>
#define null NULL
using namespace std;
string s;
string fun(string str)
{
string str2=str;
reverse(str2.begin(),str2.end());
int n=str.size();
vector<vector<int>>dp(n+1,vector<int>(n+1,0));
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(str[i-1]==str2[j-1])dp[i][j]=1+dp[i-1][j-1];
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
string comp="";
int i=n,j=n;
while(i>0&&j>0)
{
if(str[i-1]==str2[j-1])
{
i--;
j--;
}
else
{
if(dp[i-1][j]>=dp[i][j-1])
{
comp.push_back(str[i-1]);
i--;
}
else j--;
}
}
while(i>0)
{
comp.push_back(str[i-1]);
i--;
}
reverse(comp.begin(),comp.end());
return comp;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>s;
int cnt=0;
while(s.size())
{
cnt++;
s=fun(s);
}
cout<<cnt<<endl;
return 0;
}
Entering edit mode
//Team Formation
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
vector<int>a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
sort(a.begin(),a.end());
int cnt=1;
if(n==1){
cout<<1;
return 0;
}
int mini=a[0];
int ans=1;
for(int i=1;i<n;i++){
if(a[i]-mini>5){
cnt++;
mini=a[i];
}
if(cnt>k){
cout<<ans;
return 0;
}
ans++;
}
cout<<ans;
return 0;
}
