# Chef Feeds Cats Codechef Solution

Chef Feeds Cats Codechef Solution: Chef owns NN cats (numbered 11 through NN) and he wants to feed them. There are MM 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 A1,A2,…,AMA1,A2,…,AM.

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.

### Input

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• The first line of each test case contains two space-separated integers NN and MM.
• The second line contains MM space-separated integers A1,A2,…,AMA1,A2,…,AM.

### Output

For each test case, print a single line containing the string `"YES"` if the order is fair or `"NO"` if it is unfair.

### Constraints

• 1≤T≤1001≤T≤100
• 2≤N≤1002≤N≤100
• 1≤M≤1031≤M≤103

### Sample Input 1

```7
3 9
1 2 3 1 2 3 1 2 3
3 9
1 2 3 3 2 1 1 2 3
3 5
2 3 1 1 2
3 6
2 1 1 3 2 3
2 8
1 2 1 2 1 2 1 1
5 3
5 3 1
4 5
1 2 3 1 4
```

```YES
YES
YES
NO
NO
YES
NO
```

### Explanation

Example case 4: Cat 11 will eat twice before cat 33 eats even once, so the order is unfair.

Example case 5: The order is unfair because cat 11 will eat its fifth can before cat 22 eats its fourth can.

Example case 7: The order is unfair because cat 11 will eat twice before cat 44 eats even once.

## Chef Feeds Cats  – CodeChef Solution in JAVA

```import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0)
{
int n = sc.nextInt();
int m = sc.nextInt();
ArrayList<Integer> al = new ArrayList<Integer>();
int [] arr = new int[m];
boolean flag = false;
for(int i=0;i<m;i++)
{
arr[i] = sc.nextInt();
if (al.size() == n) al.clear();
else flag = true;
}
System.out.println(flag ? "NO" : "YES");
}
}
}
```

## Chef Feeds Cats  – CodeChef Solution in CPP

```#include <iostream>
#define  ll long long int
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#define mod 1000000007
#include <cmath>
#define run(a, m)  for(int i = 0 ; i <m;  i++  ) cin>>a[i]
#define run2(a, m)  for(int i = 0 ; i <m;  i++  ){ll v,u; \
cin>>u>>v; \
a[u]push_back(v);}
#define cl cout<<"\n";
using namespace std;
// C++ implementation of Naive method to print all
// divisors
#include <iostream>
using namespace std;
// function to print the divisors
void printDivisors(int n)
{
for (int i = 1; i <= n; i++)
if (n % i == 0)
cout <<" " << i;
}
ll power(ll x,  ll y)
{
ll temp;
if( y == 0)
return 1;
temp = power(x%mod, y / 2);
if (y % 2 == 0)
return ((temp%mod )* (temp%mod))%mod;
else
return ((((x%mod) * (temp%mod))%mod) * (temp%mod))%mod;
}
ll power2(ll x,  ll y)
{
ll temp;
if( y == 0)
return 1;
temp = power(x, y / 2);
if (y % 2 == 0)
return ((temp )* (temp));
else
return ((((x) * (temp))) * (temp));
}
ll countWays(ll n)
{
ll count = 0;
for (ll i = 1; i * i < n; i++)
if (n % i == 0)
count++;
return count;
}
ll gcd(ll i,ll m)
{
ll k = __gcd(i, m);
cout<<"k:"<<k<<endl;
if( k == 1&&i !=1)return 0;
else if( k == 1&&i==1)return 1;
else if(i/k == m)return 1;
else return gcd(i/k,m);
}
void getthebinarystring(ll k, string &p)
{
if(k == 0 )
return  ;
else if(k%2==0)
{
p='0'+p;
}
else p='1'+p;
getthebinarystring(k>>1,p);
}
vector<pair<ll, ll>>boo;
ll solve()
{
ll k , m ;
cin>>k>>m ;
ll vb = 1;
bool truth = true;
vector<bool>n(k+1, false);
while(  vb <= m   ){
ll p ; cin>>p;
if(!n[p]){ n[p] = true ; }
else {   truth =  false ;               }
if( vb %k == 0)n.assign(k+1, false);
vb+=1;
}
if(truth)cout<<"YES\n";
else cout <<"NO\n";
}
int main()
{
ll t= 1;
cin>>t ;
while(t--)
{
solve();
}
return 0;
}
```

## Chef Feeds Cats- CodeChef Solution in Python

```from math import *
import sys
def input():
sys.setrecursionlimit(10**9)
for _ in range(int(input())):
n,m = list(map(int,input().split()))
l = list(map(int,input().split()))
d = {}
for i in range(m):
if l[i] not in d:
d[l[i]] = 1
else:
d[l[i]]+= 1
for j in d.keys():
if d[j] > d[l[i]]:
print("NO")
break
else:
continue
break
else:
print("YES")
```

Disclaimer: The above Problem (Chef Feeds Cats) is generated by CodeChef but the solution is provided by  Chase2learn.This tutorial is only for Educational and Learning purpose.