Site Message

Only Premium Users can view the Question

Site Message

Only Premium Users can view the Question

Site Message

Only Premium Users can view the Question

Site Message

Only Premium Users can view the Question

Site Message

Only Premium Users can view the Question

Site Message

Only Premium Users can view the Question

Site Message

Only Premium Users can view the Question

Question: DE Shaw, Online Assesment (DESIS | 17th September 2023) | Range Selection | GetMinRemoval
2
Entering edit mode

ADD COMMENTlink 23 months ago Delta 3.0k
1
Entering edit mode

2. Range Selection

bool ok(vector<ll> starts,ll d,ll m){
    ll st=starts[0]+m;
    for(int i=1;i<starts.size();i++){
        st=max(st,starts[i]);
        if(starts[i]+d<st) return false;
        st+=m;
    }
    return true;
}

ll solve(vector<ll> &starts,ll d){
    sort(starts.begin(),starts.end());
    ll l=0,r=1e15;
    while(l<=r){
        ll m=(l+r)/2;
        if(ok(starts,d,m)){
            l=m+1;
        }else r=m-1;
    }
    return r;
}

ADD COMMENTlink 23 months ago Shristi Chandrakar • 40
0
Entering edit mode

1. GetMinRemoval

    string s;

    cin>>s;

    int k;

    cin>>k;

 

    vector<int> freq(26);

    for(int i=0;i<s.size();i++) {

        freq[s[i]-'a']++;

    }

 

    sort(freq.begin(),freq.end());

    int i=0,j=freq.size()-1;

 

    int ans = 0;

    while(i<=j) {

        if(freq[i]==0) i++;

        else if(freq[j]==0) j--;

        else if(abs(freq[i]-freq[j])>k) {

            ans += abs(freq[i]-freq[j])-k;

            j--;

        } else break;

    }

    cout<<ans<<endl;

ADD COMMENTlink 21 months ago Tarun • 0
0
Entering edit mode

Q1)

void solve()

{

    string s;

    int k;

    cin >> s >> k;

    vector<int> freq(26, 0);

    unordered_map<int, int> freqOfFreq;

    for (char c : s)

        freq[c - 'a']++;

    for (int f : freq)

    {

        freqOfFreq[f]++;

    }

    sort(all(freq));

    int i = 0;

    while (i < 26 and freq[i] == 0)

        i++;

    int j = 25;

    int minAns = 0;

    while (i < j)

    {

        if (freq[j] - freq[i] <= k)

            break;

 

        if ((freq[j] - freq[i] - k) * freqOfFreq[freq[j]] <= freq[i] * freqOfFreq[freq[i]])

        {

            minAns += (freq[j] - freq[i] - k) * freqOfFreq[freq[j]];

            j -= freqOfFreq[freq[j]];

        }

        else

        {

            minAns += freq[i] * freqOfFreq[freq[i]];

            i += freqOfFreq[freq[i]];

        }

    }

    cout<< minAns << endl;

}

ADD COMMENTlink 6 months ago Vakkalanka Ram Charan • 0

Login before adding your answer.

APPLY NOWSimilar Posts
Loading Similar Posts