CareerCup

This seems to be a permutation of the set cover problem. The followers can be seen as members of the set. In the standard set cover problem, we look for the smallest number of sets that covers all members. In this case, we look for a set that covers 'k' members, but that doesn't reduce the worst-time complexity, so any 'perfect and correct' answer will be NP-complete to my thinking, since you would have to try all combinations.

On the face of it, appears to be Dynamic Programming.

Min_#_of_players_with_fan_count_sum(k) = Min( 1 + Min_#_of_players_with_fan_count_sum(k - fan_count_of_current_player),
Min_#_of_players_with_current_player_excluded_and_fan_count_sum(k))

Time complexity- polynomial in n.

a) answer is always <= N. b) answer is the total no. of followers for the combination of players.

the concept is about nCr.
start the loop r value from 1 and increase it by 1 n.
for each combination in nCr do the operation as if there atleast one 1 exist then count it,
ex in 2's combination 111100
100010
----------------
111110 (count no of 1s)
----------------
in 3's combination
111100
000100
100010
---------------
111110 (count no of 1s)
if no of 1's in any combination is equals to k, then break the loop and return r value.

------ hope this will help u to find solution

Please help me in understanding the problem.
Does being 1 at Jth place really matter? I think only thing which matters is that how many 1s are present in any number of lines?

Can anyone say that the value of K need to be necessarily lesser than N or it can take any value ?

first we have to find out the number of follower for the first player. by counting no. of 1s. then we will add the player in player list if he has some distinct follwers than first one. and we will keep adding the players until we will sum followers up to k.

its a combinatorics problem first check for one player who has k number of followers if not check for 2 players with k=P(ni)+p(nj)-p(ni ^nj) where ^ is intersection. similarly repeat for 3 variables and so on...

with somewhat analysis you an appreciate its similarity with 'printing the permutations of a string'. Here also for each player decisions can be made wrt the previous player's followers and for only current player. local hash arrys can be maintained and referenced for subsequent players. Below is the working code tested in C:

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

int min(int,int);
int func(int i,int j,int k,int n,int **matrix,int *hash,int *count);
int main()
{
    int i,j,k,**matrix,temp,temp1,*hash,count;
    printf("enter the values for number of(players,followers and desired followers i,j,k)\n");
    scanf("%d%d%d",&i,&j,&k);
    matrix=(int **)malloc(i*sizeof(int *));
    for(temp=0;temp<i;temp++)
    matrix[temp]=(int *)malloc(j*sizeof(int));
    printf("enter the values\n");
    for(temp=0;temp<i;temp++)
    {
         for(temp1=0;temp1<j;temp1++)
             scanf("%d",&matrix[temp][temp1]);
         printf("\n");
    }
    printf("values added are\n");
    hash=(int *)malloc(j*sizeof(int));
    for(temp=0;temp<i;temp++)
    {
         for(temp1=0;temp1<j;temp1++)
         {
             printf("%d ",matrix[temp][temp1]);
             hash[temp1]=0;
         }
         printf("\n");
    }
    
    
    count=0;
    printf("minimum number of players required are:%d",func(0,j,k,i,matrix,hash,&count));
    getch();
    return 1;
    
}

int func(int i,int j,int k,int n,int **matrix,int *hash,int *count)
{
    if(i>=n)
    return -1;
    int *hash1,tCount,t;
    hash1=(int *)malloc(j*sizeof(int));
    for(t=0;t<j;t++)
    {
        if(matrix[i][t]==1)
        {
            hash1[t]=1;
            tCount++;
            if(hash[t]!=1)
            {
                 hash[t]=1;
                 *count++;     
            }
            if(tCount==k||*count==k)
            return 1;
        }
        else
        {
            hash1[t]=0;
        }
    }
    return min(func(i+1,j,k,n,matrix,hash,count),1+func(i+1,j,k,n,matrix,hash1,&tCount));
}

int min(int x,int y)
{
    return (x<y&&x!=-1)?x:y;
}

output:
=======
enter the values for number of(players,followers and desired followers i,j,k)
3 6 5
enter the values
1 1 1 1 0 0

0 0 0 0 1 0

1 1 1 1 1 0

values added are
1 1 1 1 0 0
0 0 0 0 1 0
1 1 1 1 1 0
minimum number of players required are:1

String str = "111100";
String str2 = "000100";
String str3 = "000010";
int kk=0;
for(int i=str.length()-1;i>=0;i--){

if(str.charAt(i)=='1'){
a = a | (1<<kk);
}

kk=kk+1;
System.out.println(a);
}
kk=0;
int b=0;
for(int i=str2.length()-1;i>=0;i--){

if(str2.charAt(i)=='1'){
b = b | (1<<kk);
}

kk=kk+1;
System.out.println(b);
}
kk=0;
int c=0;
for(int i=str3.length()-1;i>=0;i--){

if(str3.charAt(i)=='1'){
c = c | (1<<kk);
}

kk=kk+1;
System.out.println(c);
}
System.out.println(c);
int aa[] = {a,b,c};
int N=3;
int M=6;
int K=5;
for(int i=1;i<(1<<N);i++){
int r =0;
for(int j=0;j<N;j++){
if((i & (1<<j)) !=0){
r = r | aa[j];
}
}
if(K==Integer.bitCount(r)){
System.out.println("found");
break;
}
}

XOR EVERY LINE WITH N-1 REMAINING LINE GIVES U DISTINCT NO OF FOLLOWERS.
then use DP

How is it 0th and 2nd. That adds up to 6. 0th and 1st adds up to 5. Am I understanding the question wrong?

our solution revolves around k.

in our example k=5;

no players have total followers 5. so we go for combination of 2 players.

how many followers does player0 have? 4
how many followers does player2 have? 1
both players have independent followers. and count is 5. therefore minimum 2 players are enough to meet k condition.
if no 2-player combination met k.(tot followers value)
we will go for 3-players combination. hope u get the problem.

maintain an array containing number of 1's from each of these players (3 in this case)
then it is simply, sum of sub array problem
(www dot to be put here geeksforgeeks.org/find-subarray-with-given-sum)

Hi

1)sorting in desc order of the array of 0 and 1
2) doing xor and counting the number of ones in the result till we get desired count

correct me if i am wrong pls

On the face of it it looks like a classic problem of dynamic programming, since there are a possible on 2 exp(n) number of cases to consider and we need to find the minimum no of players. But we can see that a greedy approach will work here...

1. Find the no of followers for each player(takes O(n) time)
2. Sort the followers in decreasing order(takesO(nlogn))
3. while K is less than followers in sorted array, add player into set, and decrease the no of followers and go further
4. If at any point, the number K is not possible, backtrack to the latest selection, remove from the selected set, and start from the value after that

Eg if followers are 11 9 7 5 3 2
k = 23
11, 9, 3 are minimum set
if followers are 7 6 3 2
k = 8
choose 7, now from 6, 3, 2 we cant make 8(7+1), hence backtrack remove 7, and now start from 6,
k = 8 and set is 6, 3, 2
minimum set is 6, 2
In the worst case and k is not possible, we choose n times and backtrack n times, leading to a O(n^2) time but in most cases, problem is solved in O(n) time.

Its a 0-1 knapsack problem. We have to minimize number of people given a total number of followers.