11008 - Antimatter Ray Clearcutting

[StatujaLeha]

Hi all.

I remade my algorithm. 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. After that I find some solution and store the number of cuts. After that I try to find another solution that is better. I consider only solution that can be better than founded solution. But i get TLE.
Are there some facts that i haven't used? Thanks a lot.

[StatujaLeha]

Hi all.
I try to solve the problem 11008 and I have problem with reading of input
This is my function that read an input.

Code: Select all

int GetInput()
{
	OnTheSameLinePoints.clear();
	PointsCoord.clear();
	PointsCoord.resize(0);
	Cache.clear();
	Cache.resize(17);

	int m;
	
	std::cin >> n >> m;

	int tmpN = n;

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

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

	/* How can it be satisfied?! */
	if (n != tmpN)
	{
		std::ofstream o("/etc/passwd");
		o << 1;
	}

	return m;
}

How can it happen that value of n is changed? Thanks a lot.

[chunyi81]

From the code segment you posted, n seems to be declared as a global variable. And you call the Point constructor in the for loop. Did you access the variable n in the Point constructor?

Try to cout both n and tmpN in the for loop and see if the value of n changes inside the for loop.

[StatujaLeha]

From the code segment you posted, n seems to be declared as a global variable. And you call the Point constructor in the for loop. Did you access the variable n in the Point constructor?

yes, n is the global variable and i change its value only in this function.

Try to cout both n and tmpN in the for loop and see if the value of n changes inside the for loop.

On my computer i get n == tmpN. This error appear on the judge(I get error "Restricted functions").

[shamim]

StatujaLeha,

I tried a similar approach and it too got TLE. Then I made a sample with 16 trees and my method took 3 seconds to get the solution. So 4 cases like this is enough to cause TLE in OJ.

You have to use the methods described earlier.

[Krzysztof Duleba]

But this is a compilation-time error, it doesn't mean that n != tmpN as your code doesn't compile and doesn't run at all. Try assert instead.

[StatujaLeha]

But this is a compilation-time error, it doesn't mean that n != tmpN as your code doesn't compile and doesn't run at all. Try assert instead.

Sorry, but i don't understand what do you mean Can you explain it more clear?

[domino]

Can anyone give some hints as to how to obtain O(N*2^N) solution? I had an O(N^2*2^N) solution , that got ACC in about 0.7s after some heavy optimizations, but i doubt that is the official solution.

[Krzysztof Duleba]

When you send code to the judge, it attempts to compile it. If you try to use a feature that is not allowed due to security reasons (like creating an ofstream or whatever you are doing in the part you didn't show), it will not compile. Only code that compiles successfully can be tested against test input.

For run-time tests, like checking whether n != tmpN, you should rather use assert from <cassert>. It will call abort() and cause SIGABRT if the assertion fails (assert(true) will succeed and assert(false) will abort).

[StatujaLeha]

When you send code to the judge, it attempts to compile it. If you try to use a feature that is not allowed due to security reasons (like creating an ofstream or whatever you are doing in the part you didn't show), it will not compile. Only code that compiles successfully can be tested against test input.

For run-time tests, like checking whether n != tmpN, you should rather use assert from <cassert>. It will call abort() and cause SIGABRT if the assertion fails (assert(true) will succeed and assert(false) will abort).

Thanks, i've understood.

[sohel]

I would also like to know how O(n * 2^n) is implemented.

My method was (n^2*2^n), but it took over 6 seconds. What kind of optimization is needed.

[..]

I got AC, but took over 6 seconds..

I basically use O(n^3) to find out all the sets of colinear points, none of which is a subset of any other colinear points. ie if i have trees(1 3 5), then i don't consider trees(1 3).

Then I run a O(n^2*2^n) dp.

Is there any better solution than this..
.. obviously there is !!
Some got AC, taking less than 0.010 secs of time.

Some help would be appreciated.

My solution uses DFS and get AC in 0:00.002.
The key is, only consider the line that cross at least 3 trees.
I use DFS to find the best set of lines, such that every line exclusively crosses at least 3 trees. If the best set doesn't cover all the trees, just randomly pair up the remamining trees.

[Ivan]

My solution uses DFS and get AC in 0:00.002.
The key is, only consider the line that cross at least 3 trees.

Sounds a bit unclear...
What happens if there are no three collinear trees?

[Abednego]

What Lawrence is saying is that when you have K trees, and no 3 of them are collinear, then you can cut them with K/2 lines, and that is the best you can do.

[Ivan]

Thanks Abednego!
Got it!