CORUS - Editorial

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 :grinning:

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?

@kxp3 can you please explain your 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

Your o/p:
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() {
// your code goes here
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;

}
link to my solution.
https://www.codechef.com/viewsolution/32882502

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

Can someone Please help to figure out why i am getting tle in #6 case.
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

Thank you so much for your reply!

stored string in a variable got frequency of each character stored in a string like- if string is aaaddbbc then first i sorted it alphabetically then my frequency string was 1223 then as per the query i used a loop 0 to c to decrease this string by 1111 then by 111 and so on until it either become 0 or loop ended then converted it to int and summed its digit to get the answer.

if u see u have declared globally map u have to keep clear the map freq after every test case or u can declare map in while (t–) loop