Citadel 电面

上周电面的Citadel NXT,面试官简短介绍了一下公司,就开始了coding interview。题目很经典,LRU Cache


Given 3n people that the i-th person can pass a test with probability p_i,
now you are required to divide them to n groups that each group has 3 people.
The score of one group equals 1 if at least two people pass the test, 0 otherwise.
In order to maximize the expectation of total score, how do you group them?

感觉得用 Integer programming,没法直接算