11008 - Antimatter Ray Clearcutting

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

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
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

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

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

deleted
Last edited by asif_rahman0 on Mon Mar 20, 2006 9:54 pm, edited 1 time in total.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

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.
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

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
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

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

Post by andresw1 » Mon Mar 20, 2006 9:57 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

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

thnx andresw1.
i got it:)

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

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

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

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?

User avatar
arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

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 :lol:
yours
Arsalan

User avatar
Hadi
Learning poster
Posts: 63
Joined: Mon Aug 29, 2005 8:13 am
Location: Tebriz
Contact:

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
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

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



Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

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

why isn't the code window does not working?
Self judging is the best judging!

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

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.
If only I had as much free time as I did in college...

Post Reply

Return to “Volume 110 (11000-11099)”