Thursday, 18 August 2016

Find out the maximum number of topics a 2-person team can know. And also find out how many teams can know that maximum number of topics. pick 2 people out of N people

ACM ICPC Team:-
Problem Statement
You are given a list of N people who are attending ACM-ICPC World Finals. Each of them are either well versed in a topic or they are not. Find out the maximum number of topics a 2-person team can know. And also find out how many teams can know that maximum number of topics.
// pick 2 people out of N people

Input Format
The first line contains two integers N and M separated by a single space, where N represents the number of people, and M represents the number of topics. N lines follow.
Each line contains a binary string of length M. In this string, 1 indicates that the ith person knows a particular topic, and 0 indicates that the ith person does not know the topic.
//N people , M topic

Output Format
On the first line, print the maximum number of topics a 2-person team can know.
On the second line, print the number of 2-person teams that can know the maximum number of topics.
// condiser each topic's character array AS a binary or integer
// then screen all combination by taking "OR" operation and find a maximum number of "1" and the team
// to put the result , use a HashMap then put the team number and max count "Map<Integer,Integer>"
// key is to do "OR" operation in given array element.
//1. receive all necessary input parameters
//2. store to character array
//3. convert character array to integer array for "OR" operation
//4. screen all combination but there's no need to concern an order
//5. after 4, check number of "1" value and compare to previous max value if it exceeds or same
//6. iterate above
//7. print max and number of teams value - hashmap size

Constraints
2 ≤ N ≤ 500
1 ≤ M ≤ 500

Sample Input
4 5
10101
11100
11010
00101


Sample Output
5
2


Explanation
(1, 3) and (3, 4) know all the 5 topics. So the maximal topics a 2-person team knows is 5, and only 2 teams can achieve this.
Code


import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class ACMICPC {
    public static void main(String[] args) {
       
        Scanner in = new Scanner(System.in);
       
        //no of people
        int N = in.nextInt();
       
        //no of topic
        int M= in.nextInt();
       
        char[][] t = new char[N][M];
       

        //each pereons's topic data
        for(int i=0;i<N;i++){
            t[i]=in.next().toCharArray();
        }
       
        //convert to int type for "OR" operation
        int [][] p = new int[N][M];
       
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
            p[i][j]=(int)(t[i][j]-'0');
            }
        }
       
        //map for storing teams data
        Map<Integer,Integer> hmap = new HashMap<>();
       
        int count=0;
        int max=0;
       
       
        for(int i=0;i<N;i++){
         //first person
            int[] a=p[i];
            for(int j=i+1;j<N;j++){
             //second person
                int[] b=p[j];
                count=0;
                //"OR" operation and count total number of "1"
                for(int k=0;k<M;k++){
                    if((a[k]|b[k]) ==1)
                        count++;
                }
                //new MAX found , previous max and map data will be removed
                if(count>max){
                    max=count;
                    hmap.clear();
                    hmap.put(i,j);
                //same as max , count
                }else if(count==max){
                    hmap.put(i,j);
                }
            }           
        }
       
        //max number of "OR"
        System.out.println(max);
        //number of team who meet "max"
        System.out.println(hmap.size());
       
    }
}
Post a Comment