Recently (not so recently) I was the problem setter of one SRM. When I was developing the problems I had the idea of creating the following problem:
Given N points on a cartesian plane, two players plays the following game in alternate rounds:
The player of each round must choose two points and draw a segment of line between them as long as this segment of line doesn't intersect with any segment created before.
The player who can not draw a segment of line anymore loses the game.
Given that both players plays optimally, who is the winner?
This problem is almost the same as the Div2Hard from SRM624 ( http://community.topcoder.com/stat?c=problem_statement&pm=13204&rd=15857 ), but now we don't have the restriction that the points must be part of a convex polygon. I've asked lots of amazing coders (including target coders) but no one found a solution yet or proved that this problem is unsolvable in polynomial time.
The best solution I could come up with is the most naive one (O(2^N)). My question here is if it's possible to solve this problem with a better solution or even prove that it's indeed unsolvable.
yes you can, using the Grundy numbers .
The convex polygon one can be solved with Grundy Numbers indeed, but I'm afraid it's not possible to do the same when I have random points on a cartesian plane.
No solutions? =/
If target coders couldn't come up with a efficient solution then do you really expect the other coders to help you? XD
This game is a special case of Node-Kayles game, so it can be solved in O(1.6052^edges).
Sad to see exponential expression :(( that means it is an NP Hard problem?
Node-Kayles is PSPACE-complete, but I'm not sure if it's equivalent to the problem in question