Page 3 of 6

Re: taking too long..

Posted: Mon Mar 13, 2006 3:45 pm
by 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.

I don't understand how can it happen.

Posted: Mon Mar 13, 2006 11:04 pm
by 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.

Posted: Tue Mar 14, 2006 5:51 am
by 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.

Posted: Tue Mar 14, 2006 7:05 am
by StatujaLeha
chunyi81 wrote: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").

Posted: Tue Mar 14, 2006 10:25 am
by 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.

Posted: Tue Mar 14, 2006 11:24 am
by 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.

Posted: Tue Mar 14, 2006 2:00 pm
by StatujaLeha
Krzysztof Duleba wrote: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?

Posted: Tue Mar 14, 2006 2:37 pm
by 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.

Posted: Tue Mar 14, 2006 6:39 pm
by 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).

Posted: Tue Mar 14, 2006 7:29 pm
by StatujaLeha
Krzysztof Duleba wrote: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.

Posted: Wed Mar 15, 2006 3:43 pm
by 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.

Re: taking too long..

Posted: Wed Mar 15, 2006 4:43 pm
by ..
sohel wrote: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.

Posted: Wed Mar 15, 2006 8:20 pm
by 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?

Posted: Wed Mar 15, 2006 8:33 pm
by 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.

Posted: Wed Mar 15, 2006 9:26 pm
by Ivan
Thanks Abednego!
Got it!