The problem statement isn’t “misleading”, it’s entirely incorrect however you interpret it.
@ushsh, both the pre-edit and post-edit versions of the problem are wrong. The edit just rewrote the sentence while for the most part maintaining its meaning.
Easy example: for n=4, m=5, the graph can ALWAYS be drawn by choosing (it said you could choose points from the euclidean plane) the 4 points to be the vertices of a square and the 5 edges to be its outer edges and one diagonal, in which case you can never draw the 6th edge, making the answer 1 in this case. Every graph with (4,5) is isomorphic to the graph described in this embedding.
… He marked N pairwise different points on the plane and then connected M pairs of these points by straight-line segments. None of these segments intersect(maybe except at the initial N points). Then Leha tried to draw the M+1-th segment but surprisingly it turned out that it was impossible to connect any pair of points by straight-line segment which wouldn’t intersect with any of the previous segments.
The questions is: whether it’s possible to choose N points on the Euclidean plane such that they will fit the situation described above.
Yes, it’s possible to choose points as described above. You said “is it possible to choose”. This means you are allowed to choose any planar embedding, even one that would prevent you from adding another edge.
The question is: whether it’s possible to choose N points on the Euclidean plane in any way such that they will always fit the situation described above.
Yes, it is possible to choose points “in any way” (as described above) such that they will “always” fit the situation. “Any way” means “any one way out of all possible ways”. By saying “always”, the author obviously meant to say (as we realized after some WAs), output 1 if
(i) there exists at least one choice of points with a corresponding planar embedding, and
(ii) considering all graphs (>= 0 of them) resulting from an edge addition to the input graph, none of them has a choice of points corresponding to a planar embedding.
That is, is the graph maximal planar. Totally different question.
Making some words in a sentence bold does not change their meaning. Linguistic accuracy is the foundation of making problem statements, as all of mathematics and computer science depend on formal notation and on rigour in language.
I understand that the problem was probably translated from another language, but that definitely does not justify its being incorrect after testing. I know this is a pretty long rant, but I wasted a lot of time on this problem (as I did with the author’s previous problem LPARTY a few months ago, which also had a terrible choice of words and story).
I do hope I am correct and would appreciate it if someone could explain how I am wrong in case I am.