Page 1 of 1
11289 - Friend or Foe?
Posted: Mon Oct 08, 2007 7:46 am
by moravsky
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.
Posted: Mon Oct 08, 2007 7:59 am
by Darko
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
Posted: Mon Oct 08, 2007 8:55 am
by moravsky
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?
Posted: Mon Oct 08, 2007 9:26 am
by sclo
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.
Posted: Mon Oct 08, 2007 10:43 am
by Darko
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
Posted: Mon Oct 08, 2007 10:55 am
by sclo
the method looks like gradient descent, but I don't know what function it is trying to minimize.
Posted: Mon Oct 08, 2007 11:09 am
by Darko
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.
Posted: Mon Oct 08, 2007 6:48 pm
by gvcormac
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.
Posted: Mon Oct 08, 2007 8:08 pm
by sclo
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.