Chef owns N cats (numbered 1 through N) and he wants to feed them. There are M identical cans of cat food; each can must be used to feed exactly one cat and Chef can only feed one cat at a time. Chef wrote down the order in which he wants to feed the cats: a sequence A_1,A_2,…,A_M.
An order of feeding cats is fair if there is no moment where Chef feeds a cat that has already been fed strictly more times than some other cat. Help Chef — tell him if the order in which he wants to feed the cats is fair.
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
EXPLANATION:
This was the easiest problem of the contest. Because of very low limits a brute-force solution gets an easy AC.
Keep a counter for each cat recording how many times you had fed it before. Before feeding the next cat just loop over all other cats and check if it was fed fewer times than (or equal to) each of them. It’s better to check out my implementation. It runs in O(M*N)
A solution that runs in O(M \, log M) works as follows:
Strip the operations into consecutive blocks of N feeding operations (starting from the first one). Each of these blocks must be a permutation of length N (distinct elements). For each block, you can sort the numbers and verify. The last block may have less than N elements, it would be enough to check that all numbers inside it are distinct.
AUTHOR’S AND TESTER’S SOLUTIONS:
EDITORIALIST’s solution: Can be found here EDITORIALIST’s 2nd solution: Can be found here
By submitting, I meant how do I make it available for others to see. Just like everyone can see the tutorial. I mean is it allowed to submit my solution in the comments?
Thank you, I love those songs as well.
int t;
cin >> t;
while(t--){
int n, m;
cin >> n >> m;
int ar[m+1];
for(int i=1; i<=m; i++)
cin >> ar[i];
bool flag = true;
// Divivde these operation in terms of 'N'
int i, k;
for(i=1, k=1; i<=m; i++){
if(i%n == 0){
// sort every n size block and
// check if all the elemement are distinct
sort(ar+k, ar+i+1);
for(int l=k; l<=i-1; l++){
if(ar[l]!=ar[l+1]){
flag = true;
}
else{
flag = false;
break;
}
}
k = i+1;
}
}
// cout <<" K : " << k << endl;
// Left over check
if(k<m && flag!=false){
sort(ar+k, ar+m+1);
for(int x=k; x<=m; x++){
//cout << ar[x] << " ";
if(ar[x]!=ar[x+1]){
flag = true;
}
else{
flag = false;
break;
}
}
//cout << endl;
}
cout << (flag ? "YES\n" : "NO\n");
}
return 0;