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

nonvoid
New poster
Posts: 3
Joined: Wed Mar 15, 2006 7:44 pm

Post by nonvoid » 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:

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;
}
Thank you.

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

Post by shanto86 » Wed Apr 05, 2006 5:52 pm

i am late to say, but well, thanks abednigo! i spotted my mistake corrected it and got AC but in > 9sec! :(
Self judging is the best judging!

nonvoid
New poster
Posts: 3
Joined: Wed Mar 15, 2006 7:44 pm

Post by nonvoid » Wed Apr 05, 2006 9:41 pm

My code runs in about 0.5 secs, but it gets WA, though I tested it on all the inputs from the forum. Still can't figure out what I did wrong.

rajkon
New poster
Posts: 5
Joined: Sun Apr 02, 2006 11:59 am

nice problem :)

Post by rajkon » Thu Apr 06, 2006 11:12 pm

Just want to say that I really liked this problem :)

I got AC in 0.033

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

Post by shanto86 » Wed Apr 12, 2006 10:23 pm

can u plz share ur idea with us?
Self judging is the best judging!

rajkon
New poster
Posts: 5
Joined: Sun Apr 02, 2006 11:59 am

Post by rajkon » Thu Apr 13, 2006 1:14 am

Who, me?

Ok, if it is me, then my idea is same as somebody posted few pages back :

memoization + simple geometry (to see if 3 points belongs to the same line) + using bitmasks ... look at the older posts in this topic, couse they very helpfull ...

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

Post by shanto86 » Thu Apr 13, 2006 1:23 pm

well i did the same thing (u can look at my code, though that is WA but my AC is almost same as that)

Mahbub
Self judging is the best judging!

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

Help me please

Post by StatujaLeha » Thu Apr 13, 2006 7:50 pm

Hi all. I really don't understand what is wrong with my solution. I try to use the approach posted int this topic but get WA :( Please help me.

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <math.h>

int n;

struct Point
{
	int m_x;                        //x-coordinate of point
	int m_y;                        //y-coordinate of point

	Point():m_x(0),m_y(0){}
	Point(int const& x,int const& y):
	m_x(x),m_y(y){}
};

bool operator == (Point const& L,Point const& R)
{return (L.m_x == R.m_x)&&(L.m_y == R.m_y);}

bool operator != (Point const& L,Point const& R)
{return !(L == R);}

struct Line
{
	Point m_A;
	Point m_B;

	Line(Point const& A,Point const& B):m_A(A),m_B(B){}

	bool isOnLine(Point const& X)
	{
		return ((m_B.m_y - m_A.m_y)*(X.m_x - m_A.m_x)
			==
			(m_B.m_x - m_A.m_x)*(X.m_y - m_A.m_y))
			;
	}
};

//stores coordinates of trees
std::vector< Point > PointsCoord(0);

class PointSet : public std::bitset< 16 >
{
public:
	unsigned long long m_Sign;
	/* Returns true if Set is a subset of this set. */
	bool isSubset(PointSet const& Set)const
	{
		for (int i = 0;i < Set.size();++i)
		{
			if(((*this)[i] == false) && (Set[i] == true))
				return false;
		}

		return true;
	}

	PointSet(){}
	PointSet(std::bitset< 16 > const& Orig):std::bitset< 16 >(Orig){}
};

PointSet operator+(PointSet const& L,PointSet const& R)
{
	return PointSet(L | R);
}

PointSet operator-(PointSet const& L,PointSet const& R)
{
	return PointSet(L & (~R));
}

PointSet Intersection(PointSet const& L,PointSet const& R)
{
	return PointSet(L & R);
}


std::vector< PointSet > AtLeast3Points;
std::vector< PointSet > TwoPoints;

void FindOnTheSameLinePoints()
{
	for(int i = 0;i < PointsCoord.size() - 1;++i)
	{
		int k = i + 1;
		for (;k < PointsCoord.size();++k)
		{
			Line line(PointsCoord[i],PointsCoord[k]);
			PointSet tmp;

			tmp[i] = true;
			tmp[k] = true;

			int j = k + 1;
			for (;j < PointsCoord.size();++j)
				if(line.isOnLine(PointsCoord[j]))
					tmp[j] = true;

			bool isSubset = false;
			for (std::vector< PointSet >::iterator z = AtLeast3Points.begin();
				z != AtLeast3Points.end();
				++z)
			{
				if(z->isSubset(tmp))
				{
					isSubset = true;
					break;
				}
			}

			if (!isSubset)
				if(tmp.count() > 2)
					AtLeast3Points.push_back(tmp);
		}
	}
}

typedef std::pair< int/* Number of cut trees */,int/* Number of shoots */ > Solution;

Solution Cache[17][65535];


Solution FindMinCuts(int m,PointSet const& CurrSet)
{
	if(m <= 2)
		return Solution(0,0);

	if(Cache[m][CurrSet.to_ulong()].first == -1)
	{

		Solution  Result(0,0);

		bool found = false;

		for (int i = 0;i < AtLeast3Points.size();++i)
		{
			/* Number of trees that shoot i can cut in this set of trees. */
			int Q = Intersection(CurrSet,AtLeast3Points[i]).count();

			if (Q > 2)
			{
				Solution tmp = FindMinCuts(m - Q,
										   CurrSet - AtLeast3Points[i]
										   );

				if(!found)
				{
					if((Result.first <= tmp.first + Q))
					{
						if(Result.first < tmp.first + Q)
						{
							Result.first  = tmp.first + Q;
							Result.second = tmp.second + 1;
						}
						else
							Result.second = std::min(Result.second,tmp.second + 1);

						/* If founded solution cut enough quantity of trees. */
						if(m <= Result.first)
							found = true;
					}
				}
				else
				{
					/* If last founded solution cut enough quantity of trees but required less quantity
					of shoots than solution founded before this solution. */
					if (m <= tmp.first + Q)
						if(Result.second > tmp.second + 1)
						{
							Result.first  = tmp.first + Q;
							Result.second = tmp.second + 1;
						}
				}
			}
		}

		Cache[m][CurrSet.to_ulong()] = Result;

		return Result;
	}
	else
		return Cache[m][CurrSet.to_ulong()];
}

bool Pred(PointSet const& L,PointSet const& R)
{return L.count() > R.count();}

int Find(int m)
{
	if (m == 0)
		return 0;

	if (PointsCoord.size() == 1)
	{
		if(m == 0)
			return 0;
		else
			return 1;
	}

	FindOnTheSameLinePoints();

	std::sort(AtLeast3Points.begin(),AtLeast3Points.end(),Pred);

	PointSet AllPoints;
	for (int i = 0;i < n;++i)
		AllPoints[i] = true;

	Solution Result;

	Result = FindMinCuts(m,AllPoints);

	/* If we have cut not enough quantity of trees. */
	if(Result.first < m)
		Result.second += (m - Result.first + 1)/2;

	return Result.second;
}

//returns number of trees to be cut off
int GetInput()
{
	AtLeast3Points.clear();
	TwoPoints.clear();
	PointsCoord.clear();

	for(int i = 0;i < 16;++i)
		for(int j = 0;j < 65535;++j)
			Cache[i][j].first = -1;

	int m;

	std::cin >> n >> m;

	for (int i = 0;i < n;++i)
	{
		Point tmp(0,0);

		//gets coordinates of next tree
		std::cin >> tmp.m_x >> tmp.m_y;
		PointsCoord.push_back(tmp);
	}

	return m;
}

int main()
{
	int N;
	std::cin >> N;

	for (int i = 1;i <= N;++i)
	{
		std::cout << "Case #" << i << ":" << std::endl;
		std::cout << Find(GetInput()) << std::endl;
		std::cout << std::endl;
	}

	return 0;
}

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Sat Apr 29, 2006 6:22 pm

What is not very clear to me is the following:
OK, we have n trees and we need to cut down m. Does that mean
that if we cut down more than m trees this is also a solution or
are we required to cut down exactly m trees

I think (not 100% sure), I just have the feeling that ... Well,
sometimes in order to cut down exactly m trees we will need
more shots than if we need to cut >= m trees.

Example:
TxxxTxxxTxxxTxxxT
xxTxxxxxxxxxxxxxx
xxTxxxxxxxxxxxxxx
xxTxxxxxxxxxxxxxx

Suppose all the letters above are in the nodes of an integer grid
in the plane. T means a tree. X means empty node in the integer grid.

So we have 8 trees in total. It's obvious that by 2 shots
we can cut 8 trees. But it seems to me we can not cut
down exactly 7 trees by two shots, can we?
So what is the answer if in the configuration above we are
required to cut down 7 trees?!

Is it 2 or is it 3 ?

10x and Regards!

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 » Sat Apr 29, 2006 6:46 pm

No response. Read the problem statement. :-)
If only I had as much free time as I did in college...

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

Post by StatujaLeha » Sat Apr 29, 2006 7:18 pm

Sedefcho wrote:What is not very clear to me is the following:
OK, we have n trees and we need to cut down m. Does that mean
that if we cut down more than m trees this is also a solution or
are we required to cut down exactly m trees

I think (not 100% sure), I just have the feeling that ... Well,
sometimes in order to cut down exactly m trees we will need
more shots than if we need to cut >= m trees.

Example:
TxxxTxxxTxxxTxxxT
xxTxxxxxxxxxxxxxx
xxTxxxxxxxxxxxxxx
xxTxxxxxxxxxxxxxx

Suppose all the letters above are in the nodes of an integer grid
in the plane. T means a tree. X means empty node in the integer grid.

So we have 8 trees in total. It's obvious that by 2 shots
we can cut 8 trees. But it seems to me we can not cut
down exactly 7 trees by two shots, can we?
So what is the answer if in the configuration above we are
required to cut down 7 trees?!

Is it 2 or is it 3 ?

10x and Regards!
TxAxTxxxTxxxTxxxT
xxTxxxxxxxxxxxxxx
xxTxxxxxxxxxxxxxx
xxTxxxxxxxxxxxxxx
xxBxxxxxxxxxxxxxx

First shoot from B to north, after that shoot from A to east. It gives exactly 7 trees.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Sun Apr 30, 2006 12:14 am

OK, I see. The problem statement clearly says "at least 7 trees".
Was it saying the same before ?
Than I should have been pretty distracted while reading ;)
Anyway, thanks.

And yes, StatujaLeha you are right. I was wrong about the example.
When constructing it I assumed the for some reason that the ray
goes in both directions, I don't know why I made this strange
assumption.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio » Sun Apr 30, 2006 6:41 pm

Sedefcho wrote:
When constructing it I assumed the for some reason that the ray
goes in both directions, I don't know why I made this strange
assumption.
You can assume that the ray goes in both directions. Because you can stay in any position when you shoot the ray. In this manner you can encounter an easy solution.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Sun Apr 30, 2006 11:55 pm

Yes, I already figured that out.

This actually comes from the fact that we want to cut down
"at least M trees" and not "exactly M trees".

So when we cut trees by shooting along some line it is always a
better strategy to cut down all the trees lying on that line
(by going far far away, behind the last tree, on that line and
shooting from there).

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

WrongAnswer

Post by tan_Yui » Mon May 01, 2006 2:41 pm

Hello, everyone.
I tried to solve this problem, but I got WrongAnswer.
Are there any critical inputs?
If you have any data, please show us solvers.

And I have a question. Is the following input (posted by StatujaLeha) valid after all?
1
16
12
540 958
901 979
540 958
901 979
758 725
664 899
758 725
664 899
848 602
636 114
848 602
636 114
284 491
829 764
284 491
829 764
Thank you.

Post Reply

Return to “Volume 110 (11000-11099)”