CONPOIN - Editorial

@shubham201
that is what… this is exactly the point which flashed in my mind. It is impossible for them to give m=10 for n=5. Was there some problem with the test cases ? :confused:
This question sucks .

Editorials are supposed to provide an opportunity for us to learn. Not point to a third party link! Wake up guys!

Uploaded the paper (PDF) here: https://www.scribd.com/doc/269955060/A-simple-recognition-of-maximal-planar-graphs

Edit: To clarify why the second point is a big contradiction to what the problem actually asks for:

“whether it’s possible to choose N points in any way(this was in bold)”. Whether it’s possible means that we should analyze whether there is at least one way of doing it, then “any way” messes up the logic. If you really meant looking for a maximal planarity testing, you should have said:

“Whether, for any placement of the N points and M segments such as no two intersect, adding the M+1-th segment would break this property”. This is much clearer and follows the rule of logic.

My interpretation of the statement “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” is that if there is at least one way of choosing points such that it does not conform to the conditions then answer is NO. The highlighted phrases are important. If you choose the points in ANY WAY, and they ALWAYS conform to the conditions, then answer is YES which is what the statement says basically.
IMHO the statement is not ambiguous.

If you choose points in ANY WAY, and they ALWAYS fit the conditions stated (regardless of what points you chose), then answer is 1. (read my comment on @Amlesh’s second answer).

“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.”

Answer is 0 in this case. In your example, the graph cannot ALWAYS be drawn by choosing the points such that it’s a maximal planar graph

Case n=5, m=10 the answer is 0 while you are printing 1.

Again, you are stressing the wrong words.

“If you choose points in ANY WAY, and they ALWAYS fit the conditions stated (regardless of what points you chose)”

IT DOES NOT SAY IF YOU CHOOSE. IT SAYS IS IT POSSIBLE TO CHOOSE.

If you want to consider ALL POSSIBLE SETS OF POINTS, then you CANNOT use the phrase “IS IT POSSIBLE TO CHOOSE”! You must say “among all possible sets of points”.

Both IS IT POSSIBLE and TO CHOSE make your argument wrong. IS IT POSSIBLE ALWAYS means is there at least one case which is true, NOT is there at least one case which is false.

Please read this carefully.