11008 - Antimatter Ray Clearcutting

StatujaLeha · Post by **StatujaLeha** » Wed Mar 15, 2006 10:36 pm

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 · Post by **asif_rahman0** » Fri Mar 17, 2006 9:24 pm

deleted

asif_rahman0 · Post by **asif_rahman0** » Fri Mar 17, 2006 9:27 pm

deleted

Abednego · Post by **Abednego** » Fri Mar 17, 2006 9:35 pm

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.

andresw1 · Post by **andresw1** » Mon Mar 20, 2006 9:28 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 · Post by **asif_rahman0** » Mon Mar 20, 2006 9:49 pm

deleted

andresw1 · Post by **andresw1** » Mon Mar 20, 2006 9:57 pm

Don't try Xs or Ys, try lines defined by points

asif_rahman0 · Post by **asif_rahman0** » Mon Mar 20, 2006 10:33 pm

thnx andresw1.
i got it:)

arsalan_mousavian · Post by **arsalan_mousavian** » Fri Mar 24, 2006 10:38 am

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

Hadi · Post by **Hadi** » Fri Mar 24, 2006 11:02 am

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 · Post by **arsalan_mousavian** » Fri Mar 24, 2006 1:23 pm

Hadi wrote: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?

hi hadi
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

Hadi · Post by **Hadi** » Fri Mar 24, 2006 3:16 pm

Happy Norouz!
Send your source code to hadi@mail2man.com .
I will answer rest of your questions via email

shanto86 · Post by **shanto86** » Sun Apr 02, 2006 6:36 am

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

shanto86 · Post by **shanto86** » Sun Apr 02, 2006 6:38 am

why isn't the code window does not working?

Abednego · Post by **Abednego** » Sun Apr 02, 2006 6:39 am

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.