Page 2 of 2
Re: 10768 Planarity -- what am I doing wrong?
Posted: Sun Nov 14, 2004 1:42 pm
by misof
ReiVaX18 wrote:misof wrote:
...
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.
Posted: Sun Nov 14, 2004 6:58 pm
by 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
All OK!
Posted: Sun Nov 14, 2004 8:06 pm
by medv
Thank you!
I submitted through email and it cut lines of program
Posted: Sat Dec 18, 2004 4:09 pm
by 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.
10768 I got AC , why?
Posted: Mon Dec 20, 2004 8:55 am
by 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
