11289 - Friend or Foe?

moravsky · Post by **moravsky** » Mon Oct 08, 2007 7:46 am

This problem has been on my mind for quite a while now. I have no idea how to solve it. I found a solution posted at http://plg.uwaterloo.ca/~acm00/070923/data/E.c, but I still don't have a slightest clue why it works. Anybody with an explanation, a hint or alternative solution is very welcome.

Darko · Post by **Darko** » Mon Oct 08, 2007 7:59 am

I was going to post a link to misof's TC post - but it was a response to your question.

I think he gave a nice explanation of a solution.

It is not an easy problem, you might want to try an easier 2D version first (they just ask if you can do it):
http://acmicpc-live-archive.uva.es/nuev ... php?p=3581

moravsky · Post by **moravsky** » Mon Oct 08, 2007 8:55 am

2Darko
misof solution runs in N^3*logN, so it's unlikely to pass in time when implemented in Java. Gradient descent on the other hand looks very nice for this one.

2sclo
what is the function that we're trying to minimize here? The diffenerence between 2 sums of scalar products?

sclo · Post by **sclo** » Mon Oct 08, 2007 9:26 am

linear discriminant analysis is also a method that works for this type of problem. we would project all the points onto a 1 dimensional line and the separating plane would be the preimage of the separating point on the line.

Darko · Post by **Darko** » Mon Oct 08, 2007 10:43 am

I've been trying to figure out what that solution does, but, unless I am missing something, it looks random. So I tried a random solution and it got accepted (I assign random numbers to a,b,c,d until it splits the points).

I guess it is not a bad idea to try during a contest

sclo · Post by **sclo** » Mon Oct 08, 2007 10:55 am

the method looks like gradient descent, but I don't know what function it is trying to minimize.

Darko · Post by **Darko** » Mon Oct 08, 2007 11:09 am

You are right, it doesn't look that random...

It looks like those two loops are pulling and turning the plane towards one set or the other and it should end up between them (I guess that is the idea). I have no idea why that works either.

gvcormac · Post by **gvcormac** » Mon Oct 08, 2007 6:48 pm

sclo wrote:the method looks like gradient descent, but I don't know what function it is trying to minimize.

The algorithm is the perceptron algorithm. I believe it can be cast as gradient descent.

sclo · Post by **sclo** » Mon Oct 08, 2007 8:08 pm

gvcormac wrote:
sclo wrote:the method looks like gradient descent, but I don't know what function it is trying to minimize.
The algorithm is the perceptron algorithm. I believe it can be cast as gradient descent.

Just as I thought.