11088 - End up with More Teams

Solution:

This problem looks innocent enough, until it bit me with a few WA and TLE. The idea to solve this problem is by using a bitmask DP technique, which I will elaborate. This solution took \( O(kN2^N) \) time.

Firstly let B be the set for which \( i \in B\) if and only if i-th person is already chosen as a member of some team. Let a[i] be the "ability" value of i-th person, we know that a[i] \( \leq 30\). Lastly, let D[B][val] be the maximum number of groups that can be formed using people in B, and such that if the total number of people in B is not divisible by 3, val will be the total ability of the extra people in B not in any group yet. For every j not in B yet, we do:

1. Let B' be the set formed after adding j into B

2. For every val, update D[B'][val+a[j]] to D[B][val] if larger.

3. In the case that B is divisible by 3, we do the following check:

- Amongst all val in [0..19], store the maximum of D[B][val] as prev. This means that the last 3 person in B can only have a total ability of at most 19, hence cannot be a group.

- Amongst all val in [20..90], store the maximum of D[B][val] as cur. This means that the last 3 person in B can form a group with total ability at least 20.

- Update D[B][0] to max {prev, cur+1}.

To cut for the time limit, you can group all D[B][val] for all val in [20..90] into one compartment, hence reduces the search time by almost 100 times.

Implementation:

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int dp[1<<15][100]; int a[20]; int N; void solve(){ for(int b=0;b<(1<<15);++b){ for(int i=0;i<100;++i){ dp[b][i] = -1; } } dp[0][0] = 0; int ans = 0; for(int K=0;K<=N;++K){ for(int b=0;b<(1<<N);++b){ int n = 0; for(int i=0;i<N;++i) if(b & (1<<i)) ++n; if(n!=K)continue; if(n!=0 && n%3==0){ int cnt = dp[b][20]; dp[b][20] = -1; int prev = -1; for(int i=0;i<=19;++i) { prev = max(dp[b][i], prev); dp[b][i] = -1; } dp[b][0] = max(cnt+1, prev); ans = max(dp[b][0], ans); } for(int i=0;i<=20;++i){ if(dp[b][i]!=-1){ for(int j=0;j<N;++j){ if(b & (1<<j)) continue; dp[b|(1<<j)][min(20, i+a[j])] = max(dp[b|(1<<j)][min(20,i+a[j])], dp[b][i]); } } } } } printf("%d\n", ans); } int main(){ int tc=1; while(scanf("%d",&N), N!=0){ for(int i=0;i<N;++i)scanf("%d",&a[i]); printf("Case %d: ", tc++); solve(); } return 0; }