PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
At first sort all employees by the numbers c[i] in decreasing order. So we can assume that c[0]>c[1]>…>c[n-1]. If we choose some friendly group i1, i2, …, ip then the quality of food in the kitchen will be 2c[i<sub>1</sub>]+2c[i<sub>2</sub>]+…+2c[i<sub>p</sub>]. Since all c[i] are different and 2i > 2i-1+…+22+2+1 then comparing friendly groups by food quality is equivalent to the lexicographical comparing.
Hence we can use greedy strategy to find the best friendly group: at each step we must add to the group the employee which compatible with all employees in the group with the largest value of c[i]. We can use several techniques in order to implement this approach efficiently. The simplest way is to loop through all employees and for each employee count the number of compatible with him employees that belong to the current friendly group. If this number coincides with the cardinality of the group then we add him otherwise not.
If we have some friendly group then in order to obtain next friendly group by the value of food quality we need to do the following. Throw away the last employee from the group and starting from the next employee follow the greedy strategy described above (in some cases you can’t add any employees after that but it’s fine it only means that the next friendly group is obtained by simply throwing away the last employee). Thus the overall complexity is O(n log n + k (n+m) ).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.