## 11008 - Antimatter Ray Clearcutting

Moderator: Board moderators

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

### Re: taking too long..

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.

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

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
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
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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
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
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
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
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
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.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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..

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:
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
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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
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
Thanks Abednego!
Got it!