Posted:

**Tue Apr 04, 2006 6:35 pm**Could someone please take the time and spot why I keep getting WA?

My algorithm works like this:

- first build a collection of points which lie on the same line, and store every such set of points as a bitmask;

- next, do a basic search for the minimum number of cuts, where gmin(K,MSK) returns the minimum number of shots required to cut K trees, given that the only available trees left are provided by the bitmask MSK;

- use memoization for the step above;

- I used as an optimization from the forum: store only lines with minimum 3 points, and if a valid solution isn't found, assign the rest of the points with each other;

Also, my code will fail if there are multiple trees at the same coordinates, but I noticed there are no such tests.

Here is the code:

Thank you.

My algorithm works like this:

- first build a collection of points which lie on the same line, and store every such set of points as a bitmask;

- next, do a basic search for the minimum number of cuts, where gmin(K,MSK) returns the minimum number of shots required to cut K trees, given that the only available trees left are provided by the bitmask MSK;

- use memoization for the step above;

- I used as an optimization from the forum: store only lines with minimum 3 points, and if a valid solution isn't found, assign the rest of the points with each other;

Also, my code will fail if there are multiple trees at the same coordinates, but I noticed there are no such tests.

Here is the code:

Code: Select all

```
#include <cstdio>
#include <cstdlib>
#include <cassert>
const int MAXN = 17;
int X[MAXN], Y[MAXN];
int LN[MAXN * MAXN], lCount;
int Q[MAXN];
int N, K;
int smin[MAXN][(1<<MAXN)];
bool was[MAXN][(1<<MAXN)];
void read(){
scanf("%d %d", &N, &K);
for(int i = 0; i < N; i++){
scanf("%d %d", &X[i], &Y[i]);
}
}
int gmin(int togo, int msk){
if(was[togo][msk])
return smin[togo][msk];
if(!togo)
return 0;
int ans = N * N;
int an0, cnt;
for(int i = 0; i < lCount; i++){
cnt = 0;
for(int j = 0; j < N; j++)
if((LN[i] & (1<<j)) && (msk & (1<<j)))
cnt += 1;
if(cnt > 0){
int nmsk = msk;
for(int j = 0; j < N; j++)
if(LN[i] & (1<<j))
if(nmsk & (1<<j))
nmsk ^= (1<<j);
an0 = 1 + gmin((togo - cnt) > 0 ? (togo - cnt) : 0, nmsk);
if(an0 < ans)
ans = an0;
}
}
was[togo][msk] = 1;
smin[togo][msk] = ans;
return ans;
}
void lines(){
lCount = 0;
for(int i = 0; i < N; i++)
for(int j = i + 1; j < N; j++)
if(X[i] != X[j] || Y[i] != Y[j])
{
int newLine = 0;
int cn = 0;
for(int k = 0; k < N; k++)
if( (X[k] - X[j]) * (Y[j] - Y[i]) - (Y[k] - Y[j]) * (X[j] - X[i]) == 0){
newLine ^= (1 << k);
cn++;
}
if(cn > 2)
LN[lCount++] = newLine;
}
}
void proc(){
lines();
int msk0 = 0;
for(int i = 0; i <= N; i++)
for(int k = 0; k < (1<<N); k++)
was[i][k] = 0;
for(int i = 0; i < N; i++)
msk0 ^= (1<<i);
int ans;
int K2 = K;
while( K2 >= 0 && (ans = gmin(K2--, msk0)) >= N * N );
K2++;
printf("%d\n", ans + (K - K2) / 2 + (K - K2) % 2);
}
int main(){
#ifndef ONLINE_JUDGE
freopen("11008.in", "r", stdin);
freopen("11008.out", "w", stdout);
#endif
int NT, NN = 0;
scanf("%d", &NT);
while(NT--){
read();
printf("Case #%d:\n", ++NN);
proc();
printf("\n");
}
return 0;
}
```