Tuesday, March 24, 2015

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;
}