11008 - Antimatter Ray Clearcutting

[nonvoid]

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]

i am late to say, but well, thanks abednigo! i spotted my mistake corrected it and got AC but in > 9sec!

[nonvoid]

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]

Just want to say that I really liked this problem

I got AC in 0.033

[shanto86]

can u plz share ur idea with us?

[rajkon]

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]

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

[StatujaLeha]

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

[Sedefcho]

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!

[Abednego]

No response. Read the problem statement. :-)

[StatujaLeha]

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.

[Sedefcho]

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]

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.

[Sedefcho]

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]

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.