Chef and Recipe CodeChef Solution: In Chefland, types of ingredients are represented by integers and recipes are represented by sequences of ingredients that are used when cooking. One day, Chef found a recipe represented by a sequence A1,A2,…,ANA1,A2,…,AN at his front door and he is wondering if this recipe was prepared by him.
Chef is a very picky person. He uses one ingredient jar for each type of ingredient and when he stops using a jar, he does not want to use it again later while preparing the same recipe, so ingredients of each type (which is used in his recipe) always appear as a contiguous subsequence. Chef is innovative, too, so he makes sure that in each of his recipes, the quantity of each ingredient (i.e. the number of occurrences of this type of ingredient) is unique ― distinct from the quantities of all other ingredients.
Determine whether Chef could have prepared the given recipe.
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 a single integer NN.
- The second line contains NN space-separated integers A1,A2,…,ANA1,A2,…,AN.
Output
For each test case, print a single line containing the string "YES" if the recipe could have been prepared by Chef or "NO" otherwise (without quotes).
Constraints
- 1≤T≤1001≤T≤100
- 1≤N≤1031≤N≤103
- 1≤Ai≤1031≤Ai≤103 for each valid ii
Sample Input 1
3 6 1 1 4 2 2 2 8 1 1 4 3 4 7 7 7 8 1 7 7 3 3 4 4 4
Sample Output 1
YES NO NO
Explanation
Example case 1: For each ingredient type, its ingredient jar is used only once and the quantities of all ingredients are pairwise distinct. Hence, this recipe could have been prepared by Chef.
Example case 2: The jar of ingredient 44 is used twice in the recipe, so it was not prepared by Chef.
Chef and Recipe CodeChef Solution in JAVA
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
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[] a = new int[n];
int []freq=new int[1001];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
freq[a[i]]++;
}
int flag =0;
int []uni = new int[1001];
for(int i=0;i<1001;i++){
if(freq[i]>0){
uni[freq[i]]++;
}
}
for(int i=0;i<1001;i++){
if(uni[i]>1){
flag=1;
break;
}
}
if (flag==1){
System.out.println("NO");
}
else{
int[] vis=new int[1001];
vis[a[0]]=1;
int i=0;
for( i=1;i<n;i++){
if(a[i]==a[i-1])
continue;
if(vis[a[i]]==1){
break;
}
vis[a[i]]=1;
}
if (i==n)
System.out.println("YES");
else{
System.out.println("NO");
}
}
}
}
}
Chef and Recipe CodeChef Solution in CPP
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
int A[n];
for (int i=0;i<n;i++)
cin >> A[i];
int freq[1001] = {0};
for (int i=0;i<n;i++)
{
freq[A[i]]++;
}
int unique[1001]={0};
int flag = 0;
for (int i=0;i<1001;i++)
{
if (freq[i]>0)
{
unique[freq[i]]++;
if (unique[freq[i]] >1)
{
flag = 1;
break;
}
}
}
if (flag == 1)
{
cout << "NO" << endl;
}
else
{
int visited[1001] = {0};
visited[A[0]] = true;
int i;
for (i=1;i<n;i++)
{
if (A[i] == A[i-1])
{
continue;
}
if (visited[A[i]] == true)
{
cout << "NO" << endl;
break;
}
visited[A[i]] = true;
}
if (i == n)
cout << "YES" << endl;
}
}
return 0;
}
Chef and Recipe CodeChef Solution in Python
t = int(input())
for i in range(0, t):
j = int(input())
l = input().split()
ans = "YES"
occurrences = []
h = 0
for c in range(0, j):
if int(l[c]) > h:
h = int(l[c])
for m in range(0, h):
occurrences.append(0)
for o in range(0, j):
a = int(l[o])
if occurrences[a-1] > 0:
if int(l[o-1]) == a:
occurrences[a-1] += 1
else:
ans = "NO"
break
else:
occurrences[a-1] += 1
if ans == "NO":
print(ans)
else:
for p in range(0, h):
for q in range(p+1, h):
if occurrences[p] == occurrences[q]:
if occurrences[p] > 0:
ans = "NO"
break
if ans == "NO":
print(ans)
break
if ans == "YES":
print(ans)Disclaimer: The above Problem (Chef and Recipe) is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.