PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Sahil Chimnani
Tester: Danya Smelskiy
Editorialist: Sahil Chimnani
DIFFICULTY:
SIMPLE
PREREQUISITES:
Basic programming, String, Frequency Array
PROBLEM:
There are 26 types of viruses, named aorona, borona, corona, …, zorona. You are given a string S of length N. There are N people (numbered 1 through N) and for each valid i, the i-th person is infected by exactly one type of virus named S_i orona.
Answer Q queries of the following type:
- There are C isolation centers and a pending queue, both with infinite capacity where only isolation centers have a restriction that two people infected with the same virus cannot stay in the same isolation center.
- Place each of the N people in either one of the isolation centers or pending queue.
- Find a way to place the people such that the number of people in the pending queue is the smallest possible.
QUICK EXPLANATION:
Distribute the people in 26 sets such that each set contains people infected with the same virus. Compute a frequency array A of size 26 containing frequencies of characters in S. For every query, iterate in A:
- If A_i \leq C, each person from A_i will get a place in one of the centers
- otherwise place C people from A_i to C centers and the rest A_i-C to the queue.
EXPLANATION:
To get the minimum size of the pending queue, we have to place the maximum number of people in isolation centers.
Subtask 1
The Constraints are very small, therefore a brute force approach works. For each query:
- Create C isolation centers.
- For each valid i in S, try to place the person with S_i orona virus to one of the isolation centers ensuring that no person with the same virus is already present in that isolation center.
- If is not possible, this person will be placed in the pending queue.
Subtask 2
Observe that the order of placing these N people doesn’t matter, at the end every person will be assigned to some isolation center or to the pending queue. Let’s distribute all N people in 26 sets such that each set contains people infected with the same type of virus. Let’s compute a frequency array A of size 26 containing the frequencies of the characters in S. For every query, iterate in A (Note that A_i people are infected with the virus i orona).
- If A_i \leq C, each person from A_i will get a place in one of the centers, therefore, no one will be placed in the queue
- otherwise, place C number of people from A_i to C centers (each in one center) and the rest A_i-C to the queue.
for i = 1 ... 26:
if A[i] > C:
#(A[i]-C) people won't get a center. Therefore must be placed in queue.
ANS = ANS + (A[i] - C)
Thanks for reading, hope you enjoyed the editorial 
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin >> t;
while(t--){
ll n, q;
cin >> n >> q;
string s;
cin >> s;
vector<int> hash(26,0);
for(int i = 0;i < n;i++)
hash[s[i] - 'a']++;
while(q--){
ll ic, count = 0;
cin >> ic;
for(int i = 0;i < 26; i++)
if(hash[i] > ic)
count += hash[i] - ic;
cout << count << "\n";
}
}
return 0;
}
Tester's Solution
#include <iostream>
#include <string>
#include <cassert>
#include <cstdio>
#include <vector>
using namespace std;
void solve(int test_id) {
int n, q;
string s;
cin >> n >> q;
cin >> s;
vector<int> cnt(26, 0);
for (int i = 0; i < n; ++i) {
++cnt[s[i] - 'a'];
}
for (int i = 0; i < q; ++i) {
int ic;
cin >> ic;
int result = 0;
for (int j = 0; j < 26; ++j)
result += max(0, cnt[j] - ic);
cout << result << '\n';
}
return;
}
int main(int argc, const char * argv[]) {
#ifdef __APPLE__
freopen("/Users/danya.smelskiy/Documents/Danya/Resources/input.txt","r",stdin);
#endif
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int tests;
cin >> tests;
assert(1 <= tests && tests <= 100000);
for (int i = 0; i < tests; ++i) {
solve(i);
}
return 0;
}
