CATFEED Editorial

PROBLEM LINK:

Practice
Contest

Author: Hasan Jaddouh
Tester & Editorialist: Hussain Kara Fallah

PROBLEM EXPLANATION

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

I have a solution which has the time complexity O(M). How do I submit that solution?

Open this, switch to “Non-IDE mode” and click “Submit”. Link to the practice question is also provided in the main post above.

I like your songs btw. Can you send me an autograph?

1 Like

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.

Just paste your link here in this thread.

Sure :slight_smile:

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

Here is a link to my solution. For each testcase, it will work in O(n).

Whats wrong with my code it is giving WA?
https://www.codechef.com/viewsolution/26874536

#include<bits/stdc++.h>
using namespace std;

int main()
{
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif

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;

}

hey can anyone help me out what’s wrong withmy solution
thanks in advance