CareerCup

#include<stdio.h>

int main()
{
long int t,n,k,i,j,a[100][100];
scanf("%ld",&t);
for(i=1;i<=t;i++){
long int m=0;
printf("Enter number of dishes:");
scanf("%ld",&n);
printf("Enter number of friends:");
scanf("%ld",&k);
for(i=1;i<=n;i++)
{
for(j=1;j<=k;j++)
{
scanf("%ld",&a[i][j]);
}
}
j=1;
while(j<=k){


for(i=1;i<=n;i++)
{

if(a[i][j]==1)
{
m++;
break;
}
}
j++;
}
printf("%ld",m);
}
}

It requires some clever bit manipulation, i feel !! What do u guys think?

OK. If I were the interviewer asking this question, I'd expect ideal answer to be the following:
1) Prove that this problem is NP-hard by showing its equivalence to well known Set cover problem
2) Reason about limits (e.g. number of kids and dishes will be reasonably small), estimate the search space and conclude that "brute-force"-like solution (e.g. backtracking with pruning of the search space) will be likely practical.
3) Propose an approximated solution - a greedy algorithm. (E.g. at each step take most liked dish, remove"satisfied" kids and repeat). Prove some important properties of of this algorithm (for instance if answer is "1" or "2" then this it is guaranteed to be optimal)
4) Code a solution which
a) starts with a greedy algorithm to find the first estimation
b) terminate if answer is optimal (by the properties of algorithm)
c) run backtracking with pruning
d) optionally limit execution of backtracking by time, ending with best found solution

5) talk about possible alternatives of backtracking and mention at least one randomized search algorithms

How about this solution:

minDish(i,j) = min(minDish(i+1,j), 1+minDish(i+1, SetOf(j-F(i))))

Where i is the dish count
j is set of friends
F(i) is set of frnds who like i-th dish

And base conditions would be
minDish(i,0) = 0
minDish(0,j) = infinity

We can use this algo:
1) find first 1 in string and its index, set it 1 in same index of final dishes string
2) set this string as all zero and find all other strings having 1 at same index and set them all zero too
3) keep iterating with step1 & step2 untill all strings are exhausted
4) final dishes string will contain minimum set of dishes

#include<iostream>
using namespace std;
int main()
{
int n,k,t;int a[500][10];int count;
cout<<"\n enter the test cases\n";
cin>>t;
if(1<=t&&t<=10)
{
for(int i=0;i<t;i++)//t=0
{ count=0;
cout<<"\n enter the number of friends\n";//2
cin>>n;
if(1<=n&&n<=500)
{
cout<<"\n enter the number of dishes\n";//2
cin>>k;
if(1<=k&&k<=10)
{
for(int j=1;j<=n;j++)//row 2
{
for(int p=1;p<=k;p++)//column2
{
cout<<"enter 1 or 0 for dislike or like ";
cin>>a[j][p];

}
}
}

else
cout<<"\n enter the number of dishes between 1 and 10";


}
else
cout<<"\n enter the number between 1 and 500";
int m=1;
while(m<=k)
{
for(int o=1;o<=n;o++)
{
if(a[o][m]==1)
{
count++;
break;

}
}
m++;
}

cout<<"\n"<<count;


}

}
else
cout<<"\n enter the number of test casesbetween 1 and 10";

return 0;
}

#include<iostream>
using namespace std;
int main()
{
int n,k,t;int a[500][10];int count;
cout<<"\n enter the test cases\n";
cin>>t;
if(1<=t&&t<=10)
{
for(int i=0;i<t;i++)//t=0
{ count=0;
cout<<"\n enter the number of friends\n";//2
cin>>n;
if(1<=n&&n<=500)
{
cout<<"\n enter the number of dishes\n";//2
cin>>k;
if(1<=k&&k<=10)
{
for(int j=1;j<=n;j++)//row 2
{
for(int p=1;p<=k;p++)//column2
{
cout<<"enter 1 or 0 for dislike or like ";
cin>>a[j][p];
}
}
}

else
cout<<"\n enter the number of dishes between 1 and 10";
}
else
cout<<"\n enter the number between 1 and 500";
int m=1;
while(m<=k)
{
for(int o=1;o<=n;o++)
{
if(a[o][m]==1)
{
count++;
break;
}
}
m++;
}
cout<<"\n"<<count;
}
}
else
cout<<"\n enter the number of test cases between 1 and 10";
return 0;
}

#include<stdio.h>

int main()
{
long int t,n,k,i,j,a[100][100];
scanf("%ld",&t);
for(i=1;i<=t;i++){
long int m=0;
printf("Enter number of dishes:");
scanf("%ld",&n);
printf("Enter number of friends:");
scanf("%ld",&k);
for(i=1;i<=n;i++)
{
for(j=1;j<=k;j++)
{
scanf("%ld",&a[i][j]);
}
}
j=1;
while(j<=k){


for(i=1;i<=n;i++)
{

if(a[i][j]==1)
{
m++;
break;
}
}
j++;
}
printf("%ld",m);
}
}

That's really confusing. I couldn't get it. Is that a known game?

That's really hard to get. Is that a known game, guys?