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

Re: taking too long..

Post by StatujaLeha » Mon Mar 13, 2006 3:45 pm

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
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

I don't understand how can it happen.

Post by StatujaLeha » Mon Mar 13, 2006 11:04 pm

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
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Tue Mar 14, 2006 5:51 am

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
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

Post by StatujaLeha » Tue Mar 14, 2006 7:05 am

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

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Tue Mar 14, 2006 10:25 am

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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Tue Mar 14, 2006 11:24 am

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.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

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

Post by StatujaLeha » Tue Mar 14, 2006 2:00 pm

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?

domino
New poster
Posts: 19
Joined: Thu Dec 25, 2003 6:01 pm

Post by domino » Tue Mar 14, 2006 2:37 pm

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.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Tue Mar 14, 2006 6:39 pm

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).
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

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

Post by StatujaLeha » Tue Mar 14, 2006 7:29 pm

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.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Wed Mar 15, 2006 3:43 pm

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.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Re: taking too long..

Post by .. » Wed Mar 15, 2006 4:43 pm

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.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Post by Ivan » Wed Mar 15, 2006 8:20 pm

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?

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

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

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Post by Ivan » Wed Mar 15, 2006 9:26 pm

Thanks Abednego!
Got it!

Post Reply

Return to “Volume 110 (11000-11099)”