Answers to: CONPOIN - Editorialhttps://discuss.codechef.com/questions/71547/conpoin-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/CONPOIN">Practice</a><br>
<a href="http://www.codechef.com/JUNE15/problems/CONPOIN">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/pavel1996">Pavel Sheftelevich</a><br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/white_king">Mahbubul Hasan</a> and <a href="http://www.codechef.com/users/ma5termind">Sunny Aggarwal</a><br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/balajiganapath">Balajiganapathi Senthilnathan</a><br>
<strong>Russian Translator:</strong> <a href="http://www.codechef.com/users/xcwgf666">Sergey Kulik</a><br>
<strong>Mandarian Translator:</strong> <a href="http://www.codechef.com/users/xiaodao">Minako Kojima</a></p>
<h1>DIFFICULTY:</h1>
<p>Hard</p>
<h1>PREREQUISITES:</h1>
<p>Maximal planar graph </p>
<h1>PROBLEM:</h1>
<p>You are given N points and M edges connecting them. You have to determine whether it is possible to draw those N points and M edges on a plane such that no two edges intersect except at the endpoints and it is not possible to add another edge without intersecting an existing edge.</p>
<h1>EXPLANATION:</h1>
<p>The first part is to find whether it is possible to draw the points and edges such that the edges are non intersecting. That is the definition of planar graph. </p>
<p>The second part of the condition is that if we add one more edge the graph will be non planar. Thus we have to find out whether the given graph is a <em>maximal planar graph</em> or not.</p>
<p>This can be done in linear time using the algorithm given <a href="https://www.researchgate.net/publication/220112472_A_simple_recognition_of_maximal_planar_graphs">here</a>.</p>
<h1>Time Complexity:</h1>
<p>$O(N)$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/JUNE15/setter/CONPOIN.java">Author's solution</a> <br>
<a href="http://www.codechef.com/download/Solutions/JUNE15/tester/CONPOIN.cpp">Tester's solution</a></p>enMon, 29 Jun 2015 14:44:27 +0530Answer by yleeweihttps://discuss.codechef.com/questions/71547/conpoin-editorial/72438<p>Uploaded the paper (PDF) here: <a href="https://www.scribd.com/doc/269955060/A-simple-recognition-of-maximal-planar-graphs">https://www.scribd.com/doc/269955060/A-simple-recognition-of-maximal-planar-graphs</a></p>yleeweiMon, 29 Jun 2015 14:44:27 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/72438Answer by njr07121977https://discuss.codechef.com/questions/71547/conpoin-editorial/71798<p>Editorials are supposed to provide an opportunity for us to learn. Not point to a third party link! Wake up guys!</p>njr07121977Tue, 16 Jun 2015 22:19:08 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71798Answer by shivamg_ischttps://discuss.codechef.com/questions/71547/conpoin-editorial/71748<p><a href="/users/53157/shubham201">@shubham201</a>
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 ? :/ ..
This question sucks .</p>shivamg_iscTue, 16 Jun 2015 00:46:22 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71748Answer by shubham201https://discuss.codechef.com/questions/71547/conpoin-editorial/71747<p><a href="/users/104109/checkmate1">@checkmate1</a> , Yes 5C2 is 10.But they cannot give m=10 for n=5 because for this the edges will intersect but question say the given m edges are non-intersecting. So how they can give m=10 non-intersecting edges for n=5??? So one cannot say whats the answer for m=10 and n=5.</p>shubham201Tue, 16 Jun 2015 00:32:42 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71747Answer by shubham201https://discuss.codechef.com/questions/71547/conpoin-editorial/71746<p><a href="/users/97006/shivamg_isc"><a href="/users/97006/shivamg_isc">@shivamg_isc</a></a> , agree with you.
As the problem statement says the given m edges are non-intersecting.
For n=5, and the optimal planar graph will have 9 edges (i.e. we cannot add more edge). Since they are not giving non-intersecting edges they cannot give m>=10 for n=5, so for m<9 answer should be 0 and m>=9 answer should be 1. But it gave me wrong answer. I got correct answer for 20 points when i did m==9 instead of m>=9. Why so, if they haven't given m>=10 (because for m>=10 the m edges will intersect) ???
I mean answer should not depend for m>=10 for n=5 since they are not giving non-intersecting edges.
Am i wrong anywhere in understanding anything??</p>shubham201Tue, 16 Jun 2015 00:26:20 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71746Answer by checkmate1https://discuss.codechef.com/questions/71547/conpoin-editorial/71745<p><a href="/users/97006/shivamg_isc">@shivamg_isc</a></p>
<p>Check this :-- <a href="http://www.codechef.com/viewsolution/7234731">http://www.codechef.com/viewsolution/7234731</a></p>
<p>I just changed your soln a little bit....</p>
<p>All >= signs are there as it is except for n = 5 (last case) as 5C2 is 10....</p>
<p>That was your mistake for n = 5 and m = 9 ans is 1 and for n = 5 and m = 10 ans must be 0...</p>
<p>Hope you can understand... </p>checkmate1Tue, 16 Jun 2015 00:20:39 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71745Answer by shivamg_ischttps://discuss.codechef.com/questions/71547/conpoin-editorial/71708<p>I attempted the question for 20 marks . This is my solution.</p>
<p><a href="http://www.codechef.com/viewsolution/7154533">http://www.codechef.com/viewsolution/7154533</a></p>
<p>It gave WA on the second part of the subtask meant for 20 points.
Now , have a look at this solution,
<a href="http://www.codechef.com/viewsolution/7211402">http://www.codechef.com/viewsolution/7211402</a></p>
<p>What i can't understand is that I just used a greater than sign for just namesake (in case there are more than n*(n-1)/2 segments given as the value of m). Afterall , it was specifically mentioned that no two points can be connected by more than 1 segment , and no point can be connected to itself. So, how can this solution of mine can be wrong. Pls, help where am I wrong.</p>shivamg_iscMon, 15 Jun 2015 21:43:30 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71708Answer by argoshttps://discuss.codechef.com/questions/71547/conpoin-editorial/71672<p>Could not download paper. Please write normal editorial or give working link.</p>argosMon, 15 Jun 2015 20:27:20 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71672Answer by helthazarhttps://discuss.codechef.com/questions/71547/conpoin-editorial/71671<p>Next time pay please more attention to the problem statement and clarify the updates somehow, otherwise people try to solve another problem which is much more complex.</p>helthazarMon, 15 Jun 2015 20:26:09 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71671Answer by xorfirehttps://discuss.codechef.com/questions/71547/conpoin-editorial/71654<p>I agree with <a href="/users/81740/amlesh">@Amlesh</a>. This is the fcking shittiest problem statement I have ever seen in my life. To think I spent days trying the wrong problem when I have so much more important shit to do, darn. You guys do not know how to write problem statements. The question <em>clearly</em> wanted an embedding of a planar graph on the plane such that any new edge intersects a previous segment. Now, it is like, "Hehe, just a misunderstanding, I meant a maximal planar graph. Not a big deal". I hate you all.</p>xorfireMon, 15 Jun 2015 18:58:28 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71654Answer by xellos0https://discuss.codechef.com/questions/71547/conpoin-editorial/71651<p>I used almost exactly the approach from the editorial - googled the paper and implemented the algorithm described there.</p>
<p>That's a bad thing, though. For one, getting to the paper took me about half a minute on Google and 5 minutes of waiting for the login page on Researchgate to load. What's worse, there's literally no CS about it, it's all just implementation and googling; you don't have to read the paper (apart from the 3 algorithms you're asked to implement) at all. That's not how you make contest problems.</p>
<p>Btw "The first part is to find whether it is possible to draw the points and edges such that the edges are non intersecting." - no, that isn't required in the solution. From what I understood, the described algorithm is simple exactly because it assumes the graph is maximal planar, and just reports "fail" when the assumption fails instead of trying more sophisticated ways to test if it's just planar.</p>
<p>Editorial: 0/10 nothing to read.</p>xellos0Mon, 15 Jun 2015 18:34:46 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71651Answer by vvneagleonehttps://discuss.codechef.com/questions/71547/conpoin-editorial/71640<p>The problem statement isn't "misleading", it's <b><i>entirely incorrect</i></b> however you interpret it.</p>
<p><a href="/users/6854/ushsh"><a href="/users/6854/ushsh">@ushsh</a></a>, 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.</p>
<p>Easy example: for n=4, m=5, the graph can ALWAYS be drawn by <i><b>choosing</b> (it said you could choose points from the euclidean plane)</i> 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 <b> never </b> 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.</p>
<p><b> PRE-EDIT VERSION </b></p>
<p><i> ... 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. </i></p>
<p>Yes, it's possible to choose points as described above. You said "is it possible to choose". This means you are allowed to <b> choose any planar embedding</b>, even one that would prevent you from adding another edge.</p>
<hr>
<p><b> POST-EDIT VERSION </b></p>
<p><i> The question is: whether it's possible to choose N points on the Euclidean plane <b> in any way </b>such that they will <b> always </b> fit the situation described above. </i></p>
<p><b> Yes, it is <i>possible to choose</i> points "in any way" (as described above) such that they will "always" fit the situation. </b> "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</p>
<p>(i) there exists at least one choice of points with a corresponding planar embedding, and</p>
<p>(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.</p>
<p>That is, is the graph maximal planar. Totally different question.</p>
<p>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 <b> rigour in language</b>.</p>
<p>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).</p>
<p>I do hope I am correct and would appreciate it if someone could explain how I am wrong in case I am.</p>vvneagleoneMon, 15 Jun 2015 18:10:12 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71640Answer by retrogradhttps://discuss.codechef.com/questions/71547/conpoin-editorial/71625<p>I have had my time on this problem because of the misleading and ambiguous explanation. What I initially (and for several days) undertood was whether you can plot the N points in a plane such as no two intersect and adding one more STRAIGHT line would be impossible. There was a lot of red herring in the explanation:</p>
<ol>
<li>Why do the edges have to be straight? In no way does this change anything about the problem.</li>
<li>What is with this sentence: "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." ? It has not much sense at all</li>
<li>If the condition has to hold in any circumstance, WHY emphasize on the collinearity of the points? It makes no sense. This one drove me on the wrong track.</li>
</ol>
<p>Other than that, the problem was nice, and maybe I would have learned the algorithm for this one, if I had undertood it properly sooner.</p>retrogradMon, 15 Jun 2015 17:26:55 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71625Answer by ushshhttps://discuss.codechef.com/questions/71547/conpoin-editorial/71598<p>The problem statement changed to
</p><blockquote>
The question is: whether it's possible to choose N points on the Euclidean plane <b>in any way</b> such that they will <b>always</b> fit the situation described above.
</blockquote>
at 14/06/2015, 02:00 hrs IST. But I think it was too late.<p></p>ushshMon, 15 Jun 2015 16:06:35 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71598Answer by miteshaghttps://discuss.codechef.com/questions/71547/conpoin-editorial/71594<p>I read it again just now. Now I see that your point is valid.</p>miteshagMon, 15 Jun 2015 15:55:33 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71594Answer by Amleshhttps://discuss.codechef.com/questions/71547/conpoin-editorial/71593<p><a href="/users/48715/miteshag">@miteshag</a> The question asks us to determine whether <em>there exists</em> an embedding such that we can't draw an extra edge. Yes I agree that this graph isn't maximal, but <em>there exists</em> a way to embed that graph so that there are no ways to add additional edges, namely a square with one of its diagonals. The problem statement should have mentioned that "regardless of how we place the N points on the plane such that the edges don't cross, we can't place a new edge between existing points", instead of "try to place the N points in a way such that ....". </p>
<p>Its particularly frustrating because I immediately dismissed the idea of just classifying the graph as maximally planar precisely due to the fact that I thought the graph just had have one embedding that was maximal, as the problem statement suggests :(</p>AmleshMon, 15 Jun 2015 15:55:16 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71593Answer by tapasjain01https://discuss.codechef.com/questions/71547/conpoin-editorial/71589<p>But i won't choose these points. i would go for 1=(0,0) 2=(1,0) 3=(1,1) and 4=(0,1). So thats a possible way of choosing the points and hence the answer should be "YES" according to me. </p>
<p>Because the question states "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." and YES, it is possible. </p>tapasjain01Mon, 15 Jun 2015 15:50:48 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71589Answer by Amleshhttps://discuss.codechef.com/questions/71547/conpoin-editorial/71586<p><a href="/users/69130/madiyar">@madiyar</a> the problem statement clearly states that we are to "try to place the given N points and M non-intersecting segments that are given, you will never be able to place M+1th segment". So for the input I described in my post, we can clearly embed the graph as a square with only one diagonal drawn, making it maximal. What the problem setter intended was to show that <em>regardless of how the graph is embedded</em> that it should be maximal, which isn't how the statement is currently worded.</p>AmleshMon, 15 Jun 2015 15:45:00 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71586Answer by krutarthkp800https://discuss.codechef.com/questions/71547/conpoin-editorial/71584<p>Please update the link to the Contest problem</p>krutarthkp800Mon, 15 Jun 2015 15:44:21 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71584Answer by miteshaghttps://discuss.codechef.com/questions/71547/conpoin-editorial/71583<p><a href="/users/80099/tapasjain01"><a href="/users/80099/tapasjain01">@tapasjain01</a></a> <a href="/users/81740/amlesh"><a href="/users/81740/amlesh">@Amlesh</a></a> For the case given with diagonal in a sqaure, we get to choose the points in cartesian plane.Hence, if I choose 1=(0,0) 2=(10,0) 3=(0,10) 4=(1,1). Then after making the graph, I can still add an edge, from 2 to 4. Hence answer will be 0.</p>miteshagMon, 15 Jun 2015 15:43:40 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71583Answer by madiyarhttps://discuss.codechef.com/questions/71547/conpoin-editorial/71581<p><a href="/users/81740/amlesh">@Amlesh</a>, no, you can add one more edge, just draw a triangle and point inside it connected to all vertices of triangle.
<a href="/users/80099/tapasjain01">@tapasjain01</a>, yes your algorithm should receive 20 points, because when n <= 5, only non-planar graph is K5, which is has more edges than 3*5-6/</p>madiyarMon, 15 Jun 2015 15:41:42 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71581Answer by Amleshhttps://discuss.codechef.com/questions/71547/conpoin-editorial/71561<p>IMHO the problem statement is misleading, since as its stated we aren't <em>quite</em> looking for maximal planar graphs. Consider the following input:</p>
<p>4 5</p>
<p>1 2</p>
<p>2 3</p>
<p>3 4</p>
<p>4 1</p>
<p>1 3</p>
<p>One way this can be interpreted is as a square with one of its diagonals connected. This is a planar embedding of a graph where no additional edge can be drawn, but however this graph is <strong>not maximal</strong>. </p>
<p>As stated, the problem is to determine whether there exists a maximal <em>embedding</em> of the given graph (if its planar of course), and not just determine if the graph itself is maximal. In fact I noticed a lot of the AC solutions miss the above case.</p>AmleshMon, 15 Jun 2015 15:21:35 +0530https://discuss.codechef.com/questions/71547/conpoin-editorial/71561