## 11008 - Antimatter Ray Clearcutting

Moderator: Board moderators

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
I have changed my solution:
1. I find all sets of points that lie on the same line and there are no two sets that one of them is the subset of another.
2. I use structure Cache to store solutions for subtasks.
std::map< int, /* quontity of trees to be cut off * /
std::map<
PointSet,/* set for that we know solution * /
int /* number of shoots * /
>
>
Cache;
3. Let Si is sets of points that lie on the same line, founded in 1. I try to find solution:
3.1. if for some k = 0,1,...,(m - 1) i've found solution for F(SetOfTrees,k) and this solution can be used for k = m, then I return this solution.
3.2. else to find solution I use formula F(SetOfTrees,m) = 1 + min(F(SetOfTrees - Si,m - Intersection(SetOfTrees,Si)))
Is my algorithm correct?

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
deleted
Last edited by asif_rahman0 on Mon Mar 20, 2006 9:52 pm, edited 1 time in total.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
deleted
Last edited by asif_rahman0 on Mon Mar 20, 2006 9:54 pm, edited 1 time in total.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Sorry, that is a mistake. You cut down 3 trees and then 4 trees. I sent a corrected problem statement to the administrators. It should be fixed soon.
If only I had as much free time as I did in college...

andresw1
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm
Hello,
I just wanted to give some hints for this problem. Basically you try every line for every set of cutted trees. However what you might do is DFS which gives TLE. Try BFS which is faster. Additionally bitmasks speed up the things a lot:)

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
deleted
Last edited by asif_rahman0 on Mon Mar 20, 2006 10:34 pm, edited 1 time in total.

andresw1
New poster
Posts: 27
Joined: Sat Mar 18, 2006 5:04 pm
Don't try Xs or Ys, try lines defined by points

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
thnx andresw1.
i got it:)

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
hi
can some one helps me on this problem i got WA on this problem over and over my approach for this problem is :
i consider the lines that contains at least 3 trees , then i check to see how many trees will cover by these lines if these lines cover all the trees i find the best result , otherwise i assign the value of M1 to the number of trees that cover by the lines that i found and again i calculate the best answer by DP , now the value of M1 is less than M ( that was mentioned in the problem statement ) then i add to the result " ceil (( float ) ( M-M1 /2 ) ) "
is it correct ?
Arsalan Mousavian

Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
Hi Arsalan,
1. You should add ceil((float)(M - M1) / 2.00) instead of ceil (( float ) ( M-M1 /2 )) .
2. You could use integer arithmetic instead of floats : add to result (M - M1) / 2 + (M - M1) % 2
3. I am Hadi Moshayedi from Amirkabir TU. Which university are you from? Or you are just getting prepaired for Computing Olympiads?

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
1. You should add ceil((float)(M - M1) / 2.00) instead of ceil (( float ) ( M-M1 /2 )) .
2. You could use integer arithmetic instead of floats : add to result (M - M1) / 2 + (M - M1) % 2
3. I am Hadi Moshayedi from Amirkabir TU. Which university are you from? Or you are just getting prepaired for Computing Olympiads?
1.i am still getting WA , do you have time to see my code ?
2.i am arsalan Mousavian from Iran University of Science & tech
3.nice to meet you
4.i like to cooperate with each other
5. happy Norooz
yours
Arsalan

Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:
Happy Norouz!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
can any one plz tell me why my code is getting WA?

Code: Select all

``````#include<stdio.h>
#include<algorithm>
using namespace std;

#define INF 1000000

int n;
int ANS[70000];
char OK[70000];
int cnt;

struct TREE
{
int x,y;
}T[30];

bool operator<(TREE a,TREE b)
{
if(a.x < b.x)
return 1;
else if(a.x==b.x && a.y<b.y)
return 1;

return 0;
}

bool operator==(TREE a,TREE b)
{
if(a.x == b.x && a.y == b.y)
return 1;

return 0;
}

int LINEAR(int i,int j,int k)
{
if( T[i].x*T[j].y + T[i].y*T[k].x + T[j].x*T[k].y -	T[i].y*T[j].x - T[i].x*T[k].y - T[j].y*T[k].x == 0)
return 1;

return 0;
}

int BIT_MAP(int state,int from,int to_kill)
{
int ans=INF,i,j,k,temp,STATE,taken,state1,extra;

if(OK[state] == 1)
return ANS[state];

if(to_kill<=0)
{
OK[state]=1;
ANS[state]=0;
return 0;
}

cnt++;

if(from >= n)
{
OK[state]=1;
ANS[state]=-1;

return -1;
}

for(i=from;i<n;i++)
if((state>>(i) & 1) == 0)
{
extra=0;
state1=state|(1<<i);

while(i+1<n && T[i+1]==T[i])
{
state1=state1|(1<<(i+1));
i++;
extra++;
}

temp=BIT_MAP(state1,i+1,to_kill-1-extra);

if(temp!=-1 && ans > temp)
ans=temp;

for(j=i+1;j<n;j++)
if( (state1>>(j) & 1) == 0)
{
STATE=state1;
STATE=STATE|(1<<j);
taken=2+extra;

for(k=j+1;k<n;k++)
if( (state1>>(k) & 1) == 0 && LINEAR(i,j,k))
{
taken++;
STATE=STATE|(1<<k);
}

temp=BIT_MAP(STATE,i+1,to_kill-taken);

if(temp!=-1 && ans > temp)
ans=temp;

}
}

ANS[state]=ans+1;
OK[state]=1;

return ans+1;
}

int main()
{
//freopen("test.in","r",stdin);
//	freopen("test1.out","w",stdout);

int cases,ks,m,i;

scanf("%d",&cases);

for(ks=1;ks<=cases;ks++)
{
cnt=0;
if(ks>1)
printf("\n");

scanf("%d%d",&n,&m);

for(i=0;i<n;i++)
scanf("%d%d",&T[i].x,&T[i].y);

sort(T,T+n);

for(i=0;i<65536;i++)
OK[i]=0;

printf("Case #%d:\n%d\n",ks,BIT_MAP(0,0,m));
}

return 0;
}

``````
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
why isn't the code window does not working?
Self judging is the best judging!

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
You fail on this test case:

Code: Select all

``````1
5
5
0 0
1000 1000
1000 -1000
-1000 1000
-1000 -1000
``````
And you have to uncheck the "Disable BBCode in this post" checkbox at the bottom when you post.
If only I had as much free time as I did in college...