UVa 11088 - End up with More Teams

Problem Statement:
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;
}