bitarray.java

import java.util.*;
class BitArray implements Comparable<BitArray> {
    public int size;
    public int id;
    public boolean[] a;
    public ArrayList<Integer> e;
    public int size(){
        return size;
    }
    public BitArray(int i, int k){
        a = new boolean[k];
        size = 0;
        id = i;
        e = new ArrayList<Integer>();
    }
    public BitArray clone(){
        BitArray t = new BitArray(id,a.length);
        t.size = size;
        for(int i=0;i<e.size();i++){
            t.a[e.get(i)] = true;
        }
        t.e = new ArrayList<Integer>(e);
        return t;
    }
    public void removeAll(BitArray b){
        for(int i=0;i<b.size();i++){
            if(a[b.e.get(i)]){
                a[b.e.get(i)] = false;
                e.remove(e.indexOf(b.e.get(i)));
                size--;
            }
        }
    }
    public boolean contains(int b){
        return a[b];
    }
    public boolean containsAll(BitArray b){
        for(int i=0;i<b.e.size();i++){
            if(a[b.e.get(i)]==false){
                return false;
            }
        }
        return true;
    }
    public int compareTo(BitArray c){
        BitArray b = (BitArray) c;
        if(size>b.size()){
            return -1;
        }
        return 1;
    }
}
public class msc{ 
    public static int counter=0;
    public static int ub;
    public static ArrayList<Integer> result;
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int e = in.nextInt();
        int n = in.nextInt();
        in.nextLine();
        ArrayList<BitArray> s = new ArrayList<BitArray>();
        for(int i=0;i<n;i++){
            Scanner line = new Scanner(in.nextLine());
            BitArray p = new BitArray(i,e);
            while(line.hasNextInt()){
                int t = line.nextInt()-1;
                p.a[t] = true;
                p.e.add(t);
                p.size++;
            }
            s.add(p);
        }
        result = greedy(e,s);
        ub = result.size();
        BitArray universe = new BitArray(0,e);
        for(int i=0;i<e;i++){
            universe.a[i] = true;
            universe.e.add(i);
        }
        universe.size = e;
        long start = System.currentTimeMillis();
        bb(universe, s, new ArrayList<Integer>());
        System.out.println("Time for Backtracking:
"+(System.currentTimeMillis()-start));
        System.out.println("Amount of Backtracking called: "+counter);
        System.out.println("Minimum Set Cover size: "+ub);
        System.out.println("List of sets to chose: "+result);
    }
    public static void bb(BitArray universe, ArrayList<BitArray> sets,
ArrayList<Integer> chosen){
        counter++;
        //Bound
        //Prune if we have chosen more than the current best
        if(chosen.size()>=ub){
            return;
        }
        //If the universe is empty, we have chosen a set cover
        if(universe.size()==0){
            ub = chosen.size();
            result = new ArrayList<Integer>(chosen);
            return;
        }
        //Bound for constant level speed ups
        //only if there is a set with size = universe set such that
        //we can get a solution of set ub-1
        //what done after it will be the more general version
        if(chosen.size()==ub-2){
            for(int i=0;i<sets.size();i++){
                if(sets.get(i).size()==universe.size()){
                    chosen.add(sets.get(i).id);
                    result = new ArrayList<Integer>(chosen);
                    ub = result.size();
                    chosen.remove(chosen.size()-1);
                    return;
                }
            }
            return;
        }
        Collections.sort(sets);
        remove_subsets(sets);
        //If the sum of the ub-chosen largest sets can't cover the the
universe
        //Prune
        int sum = 0;
        for(int i=0;i<ub-chosen.size()&&i<sets.size();i++){
            sum+= sets.get(i).size();
        }
        if(sum<universe.size()){
            return;
        }
        //Bounding decisions
        //non-negative int = no branch 0;
        //-1 both branchs
        //-2 means no brach 0 or 1
        int bv = branch_value(universe,sets);
        if(bv==-2){
            return;
        }
        if(bv!=-1){
            //Essential Branch 1, prune Branch 0
            chosen.add(sets.get(bv).id);
            remove_set(universe,sets,bv);
            bb(universe,sets,chosen);
            chosen.remove(chosen.size()-1);
        }else{
            //Branch 1, use largest set
            BitArray nu;
            ArrayList<BitArray> ns;
            nu = universe.clone();
            ns = deep_clone(sets);
            chosen.add(sets.get(0).id);
            remove_set(nu,ns,0);
            bb(nu,ns,chosen);
            chosen.remove(chosen.size()-1);
            //Branch 0, not using the largest set
            sets.remove(0);
            bb(universe,sets,chosen);
        }
    }
    public static ArrayList<BitArray> deep_clone(ArrayList<BitArray> sets){
        ArrayList<BitArray> n = new ArrayList<BitArray>();
        for(int i=0;i<sets.size();i++){
            BitArray p = sets.get(i).clone();
            n.add(p);
        }
        return n;
    }
    public static void remove_set(BitArray universe, ArrayList<BitArray>
sets, int pick){
        BitArray r = sets.get(pick).clone();
        sets.remove(pick);
        universe.removeAll(r);
        for(int i=0;i<sets.size();i++){
            sets.get(i).removeAll(r);
        }
    }
    public static int branch_value(BitArray universe,ArrayList<BitArray>
sets){
        //Idea, for each element in the BitArray, check how many sets it
is in.
        for(int i=0;i<universe.a.length;i++){
            if(universe.contains(i)){
                int c = 0;
                int t = 0;
                for(int j=0;j<sets.size();j++){
                    if(sets.get(j).contains(i)){
                        t = j;
                        c++;
                        if(c==2){
                            break;
                        }
                    }
                }
                if(c==0) return -2;
                if(c==1) return t;
            }
        }
        return -1;
    }
    public static int remove_subsets(ArrayList<BitArray> sets){
        int c =0;
        for(int i=0;i<sets.size();i++){
            for(int j=i+1;j<sets.size();j++){
            
while(j<sets.size()&&sets.get(i).containsAll(sets.get(j))){
                    sets.remove(j);
                    c++;
                }
            }
        }
        return c;
    }
    public static ArrayList<Integer> greedy(int e, ArrayList<BitArray> s){
        BitArray greedy = new BitArray(0,e);
        ArrayList<Integer> a = new ArrayList<Integer>();
        int c = 0;
        while(e!=greedy.size()){
            int max_diff = 0;
            int pick = 0;
            for(int i=0;i<s.size();i++){
                BitArray tmp = greedy.clone();
                ArrayList<Integer> ele = s.get(i).e;
                for(int j=0;j<ele.size();j++){
                    if(!tmp.contains(ele.get(j))){
                        tmp.a[ele.get(j)] = true;
                        tmp.e.add(ele.get(j));
                        tmp.size++;
                    }
                }
                if(tmp.size()-greedy.size()>max_diff){
                    pick = i;
                    max_diff = tmp.size()-greedy.size();
                }
            }
            ArrayList<Integer> ele = s.get(pick).e;
            for(int j=0;j<ele.size();j++){
                if(!greedy.contains(ele.get(j))){
                    greedy.a[ele.get(j)] = true;
                    greedy.e.add(ele.get(j));
                    greedy.size++;
                }
            }
            a.add(pick);
            c++;
        }
        return a;
    }
}