CareerCup

Run through the list and do a bitwise 'and', and maintain a list of the non-intersecting results. If the bit-and intersects any of the previously non-intersecting items , update the item with the new bit-and result. If it doesn't, add that fan to the non-intersecting list. At the end you'll have a list of all combinations of players which don't intersect with each other. Choose one player from each item, and you're done.

You have to run through the raw fan list once at O(K). The largest the non-intersecting list can possibly get is N. In the worst case the first n-1 fans individually only like the first N-1 players, and the rest of the fans only like the Nth player -- O(N) for each fan for the non-intersecting checks. Making this O(KN).

Here is working PHP code:

<?php

$test = array(
    '11111', 
    '01000',
    '00100', 
    '11110',
    '00001'

    /*
    '10101', 
    '01010',
    '00001', 
    '10000',
    '01110'
    */
);

function compactAnswer(&$arr) {
  $disparates = array();
  
  foreach ($arr as $i) {
    $i = bindec($i);
  
    $match = false;
    foreach ($disparates as $dNum => $dItem) {
      $matchNum = $i & $dItem;

      if ($matchNum) {
      	$disparates[$dNum] = $matchNum;
        $match = true;
        break;
      }
      
    }
    
    if (! $match) {
      $disparates[] = $i;
    }
  }
  
  return $disparates;
}

echo "\n\n\n";

echo 'Original: ';
foreach ($test as $i) echo $i, ', ';
echo "\n";

$test = compactAnswer($test);

echo 'Compacted: ';
foreach ($test as $i) echo decbin($i), ', ';
echo "\n", 'need ', count($test), ' players', "\n\n\n";

?>

You can use an algorithm similar to the quine-mccluskey algorithm for finding prime implicants.
Consider the likematrix above:

players_needed=0
likematrix=
10101
00001
01011

-player 5 is essential so increment the players_needed counter and remove the player column as well as all rows containing that player

players_needed =1
likematrix= empty

-likematrix is empty, therefore we are done. players_needed is 1

adding some details to @mohd.husn001's answer

we got to create a sum array that contains sum of likes per player (i.e. per column). At each step, the player with the max number of likes will be selected.

10101
00001
01011

sum array - 11113

at first step player 5 will be selected. now the 5th column and the rows for which 5th element is 1 (in this case all of them) are removed.

What about a greedy approach? We have a set of fans and an array of players, sorted according to numbers of fans they have. Till the set is not empty, we choose a player that is liked by the biggest amount of fans (first in the sorted array). Now we remove those fans from the set, update the table (if fan F was removed, then decrease the counter of fans number, for a player, that had F as a fan) and resort. Repeat. The number of iterations, would be the searched minimum. I dind't look for a counter example, but still can't prove it works.

how about treat this question as looking for min dist from node 00000 to node 11111 using BFS? each node is accessed once so i guess its O(n)?

Here is the java implementation of the solution. Logic used has been as suggested by jvermette:

int[][] likeMatrix = { {1, 1, 1, 1, 1},  
			        {0, 1, 0, 0, 0}, 
				{0, 0, 1, 0, 0},
				{1, 1, 1, 1, 0},
				{0, 0, 0, 0, 1}}; 
int[] rating = converter(likeMatrix);
ArrayList<Integer> result = finalizePlayers(rating);
print(result, likeMatrix[0].length);
}



public static int[] converter(int[][] likeMatrix){
		int result [] = new int[likeMatrix.length];
		int rating;
		for (int i = 0; i < likeMatrix.length; i++) {
			rating = 0;
			for (int j = 0; j < likeMatrix[0].length; j++) {
				if (likeMatrix[i][j] == 1) {
					rating += Math.pow(2, (likeMatrix[0].length - 1 - j));
				}
			}
			result[i] = rating;
		}
		return result;
	}

public static ArrayList<Integer> finalizePlayers(int[] rating){
		ArrayList<Integer> result = new ArrayList<Integer>();
		boolean match;
		int item;
		for (int i = 0; i < rating.length; i++) {
			match = false;
			for (int j = 0; j < result.size(); j++) {
				item = rating[i] & result.get(j);
				if(item > 0){
					result.remove(j);
					result.add(j, item);
					match = true;
					break;
				}
			}
			if(!match){
				result.add(rating[i]);
			}
		}
		return result;
	}

public static void print(ArrayList<Integer> result, int totalPlayers){
		int index = 0;
		System.out.println("Minimum players required are: ");
		for (Integer integer : result) {
			index = 0;
			while(integer>0){
				if((integer & 1) >0){
					index = totalPlayers - index;
					break;
				}else{
					integer = integer>>1;
					index++;
				}
			}
			System.out.print("Player# " + index + " ");
		}
	}

Here is the logic I followed for the code below
for each player i from 0 to (n-1), do the following steps
1) Check whether any fan contains only player i in its list. If so, this player has to be in the output. Add this player to output list.
2) Remove all fans liking player i (since this player is in the output list).
3) Also remove the player i (i.e. set bit i = 0) for all remaining rows (This is done irrespective of whether player i is in output list or not. Player i wont matter in further decision making)
4) If during this process, the number of rows (fans) becomes 0, we will stop and print the output list. This is the minimum set.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;


public class FansAndPlayers {

	public static List<List<Integer>> checkArrayList(List<List<Integer>> list, int playerNo)
	{
		List<List<Integer>> fanList = new ArrayList<List<Integer>>();
		boolean isPlayerNecessary = false;
		for(int i=0;i<list.size();i++)
		{
			List<Integer> temp = list.get(i);
			if(temp.contains(playerNo))
			{
				fanList.add(temp);	//These fans will be removed from the List if this player is necessary
				if(!isPlayerNecessary && temp.size()==1)
				{
					isPlayerNecessary = true;
				}
			}
		}
		
		
		if(isPlayerNecessary)
		{
			for(int i=0;i<fanList.size();i++)
			{
				list.remove(fanList.get(i));
			}
		}
                for(int i=0;i<list.size();i++)
		{
			List<Integer> temp = list.get(i);
			if(temp.get(0) == playerNo)
				temp.remove(0);
		}
		return list;
	}
	
	public static List<Integer> minimumFanList(List<List<Integer>> list, int noOfPlayers, int noOfFans)
	{
		List<Integer> playersNecessary = new ArrayList<Integer>();
		for(int i=0; i<noOfPlayers; i++)
		{
			int oldSize = list.size();		//No need this if you can return a tuple of list,boolean. I was feeling bored
			list = checkArrayList(list, i);
			int newSize = list.size();
			if(newSize!=oldSize)
			{
				//Player is necessary
				playersNecessary.add(i);
			}
			if(newSize == 0)	//All fans satisfied
				break;
		}
		return playersNecessary;
	}
	
	public static void main(String args[])
	{
		BufferedReader br = null;
		try
		{
			br = new BufferedReader(new InputStreamReader(System.in));
			int testCases = Integer.parseInt(br.readLine());
			for(int t = 0;t<testCases;t++)
			{
				int noOfPlayers = Integer.parseInt(br.readLine());
				int noOfFans = Integer.parseInt(br.readLine());
				List<List<Integer>> playersFansList = new ArrayList<List<Integer>>();
				for(int i=0;i<noOfFans;i++)
				{
					List<Integer> temp = new ArrayList<Integer>();
					String str = br.readLine();
					for(int j=0;j<noOfPlayers;j++)
					{
						if(str.charAt(j)=='1')
							temp.add(j);
					}
					playersFansList.add(temp);
				}
				List<Integer> finalList = minimumFanList(playersFansList, noOfPlayers, noOfFans);
				for(int i=0;i<finalList.size();i++)
				{
					System.out.print(finalList.get(i) + " ");
				}
				System.out.println();
			}
		}
		catch(Exception e)
		{
			System.out.println(e.getMessage());
		}
	}
}

Oh,it seems like NP-complete minimal vertex cover problem