10768 - Planarity

[misof]

...
An example on where's the difference: Let N=9. Make a K_5 on vertices 1,2,3,4,5. Delete the edge 4-5. Add edges 4-6, 5-6. Make a K_4 on vertices 6,7,8,9. This graph cannot be reduced and thus it is NOT homeomorphic to any graph containing K_5 or K_{3,3}. But its subgraph (induced by vertices 1,2,3,4,5,6) IS homeomorphic to K_5 and THEREFORE this graph is NOT planar. (The problem statement says that it is.)

Does anybody know whether the test data was changed?

It's homeomorphic to itself, that contains the subgraph K_5, so the problem statement says it's not planar.

No, you're wrong. I agree that my graph is homeomorphic to itself - but it doesn't contain K_5 as a subgraph! (Note that the graph doesn't contain the edge 4-5.)

As the correct version of Kuratowski's theorem states, my graph isn't planar, because it contains K_5 as a minor -- in other words, it contains a subgraph homeomorphic to K_5.

[Mohammad Mahmudur Rahman]

I have got WA with your code submitting in both C & C++ but no CE. Most probably u r submitting by e-mail. If it is, then try using -
http://acm.uva.es/problemset/submit.php

[medv]

Thank you!

I submitted through email and it cut lines of program

[Niaz]

It is better to submit problems using submit-o-matic and also not by pasting but by uploading the code. In case of pasting, some times I got CE and finally I found (from the reply mail) that some of the lines (specially from the bottom or big lines from the right side) have been broken/deleted automatically at the time of uploading raw text. That's why FILE uploading is a good practice for submitting your code.

[lord_burgos]

in my program , send condition

Code: Select all

 if(k33(0,0)) return 0;
 if(k5(0,0)) return 0;

I got ac,
but send the same code , changing condition to

Code: Select all

  number_nodos = 0;
  for(x = 1; x <= n; x++){ b = 0;
    for(y = 1; y <= n; y++) if(g[x][y]){ graph[x] |= ((int)1<<y); b = 1;}
    if(b == 1) number_nodos++;
  }


 if(number_nodos == 6 && k33(0,0)) return 0;  /*only search when number_nodos is 6 ???????????? */

 for(x = 1; x <= n; x++) graph[x] |= ((int)1<<x);


 if(number_nodos == 5 && k5(0,0)) return 0; /*only search when number_nodos is 5 ???????????? */

and I goto ac, too
why?

k5 is subset of k20 , or not? and k20 is nonreducible, or not?
-------------------------------------------
Shanghai mi primer mundial