CORUS - Editorial

Author: Sahil Chimnani
Tester: Danya Smelskiy
Editorialist: Sahil Chimnani

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.

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.

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;
}

2 Likes

https://www.codechef.com/viewsolution/32994848 can someone help me with this. what’s wrong in my code?

1 Like

Getting a TLE in Task #6
https://www.codechef.com/viewsolution/32899916
Explanation:
N is the number of people,
Q is the number queries
S is the string input
letters is a set that I create which contains only the unique characters in S
C is the number of isolation centers .

I iterate over letters and if the count of characters in S is greater than C then I add it to the count using the formula = S.count(k) - C where k is a character from letters
Then I print count which is the remaining queue

Can someone tell me why i am getting WA in this solution …I am getting correct answer when i do it in local editor…But getting WA when submitting here … I am new to programming so Plz help!
Link to the solution - https://www.codechef.com/viewsolution/32972475

You have used S.count() which takes another O(N) for every query. Try using frequency array(pre-computed count for every char) as mentioned in the editorial

@nisarg_140600. You are changing modifying the value of string s1 on every query and therefore your code fails. Try for
I/p:
1
4 2
aaab
0
1

0
0

Expected o/p:
0
2

Also, your code is not optimized which will cause TLE for subtask 2.

@sahi1422 I am new to programming and I did not know about O(N) and frequency array till now(I googled it) but are there any resources which I can use to learn more about execution time and optimizing my code (any specific keyword I should use to search on Google)

Thank you so much for your reply but can u please little more explain regarding the part “modifying the value of string s1 on every query and therefore your code fails.” … that would be great

i get tle in last case but my approach is o(n) (correct me if I am wrong)

#include
using namespace std;

int main() {
int t;
cin >> t;
while(t–)
{
int n,q;
cin >> n;
cin >> q;

    string s;
cin >> s;

for(int j=0;j<q;j++)
{
int c;
cin >> c;
int a[26];
int i;
for(i=0;i<26;i++)
{
a[i]=0;
}
for(i=0;i<n;i++)   // storing frequency of each character
{
int k=s[i]-97;
a[k]++;

}
int sum=0;
for(i=0;i<26;i++)
{
int r=a[i]-c;
if(r<0)
r=0;
sum=sum+r;

}

cout << sum << endl;

}

}

return 0;


}
https://www.codechef.com/viewsolution/32882502

https://www.codechef.com/viewsolution/32623598

Thank You.

can someone help me with this. what’s wrong in my code?

https://www.codechef.com/viewsolution/32647921

you are calculating frequency of letters every time you answer query in line 22-30.calculate frequency of letter only one time because string will not change.So there is no point in calculating frequency of same string Q times.

1 Like

Do not store frequency of each character every time you answer Query.you are calculating frequency of character of same string Q times. Calculate the frequency of character outside the loop .

1 Like

@tushar_wiz you will always see a constraint section in the problem statement which is used to figure out the time complexity of the solution. You can google for “Time Complexity of Algorithms”

1 Like

You are changing the value of given string S for every query. Only the no. of isolation centers change for every query and not the string S. Try debugging the sample input I gave u

@advitiya08, naman is right. Also your code runs in O(Q * N) but expected is O(Q + N)

1 Like