11393 - Tri-Isomorphism

All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina

11393 - Tri-Isomorphism

Post by sonyckson » Mon Jan 14, 2008 4:13 am

Well, i just wanna ask something, i did the "correct" solution ( at least the idea ) during the contest, but i thought the answer for input 1 was "YES" because you can have 3 empty lists of edges for each subgraph and ( as i see ) everything will be ok with the definitions given at the problem statement.... i got 2 WA during the contest, and another WA in another problem because of something similar, perhaps the same, i dont know what is it yet.... what im missunderstanding??? why the correct answer for input 1 is "NO"?? Thanks, Eric.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Mon Jan 14, 2008 5:26 am

I did the exact same thing.

-----
Rio

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Jan 14, 2008 10:53 am

I'm pretty sure that any graphs with no edges are isomorphic to itself.

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Post by fh » Wed Jan 30, 2008 4:09 am

Can anyone explain the meaning of "three pairwise-isomorphic subgraphs"? and the two sample cases? I completely don't understand them.
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Wed Jan 30, 2008 12:11 pm

fh,

let three subgraph G1, G2 and G3
if G1 and G2 are isomorphic, and G2 and G3 are isomorphic and G3 and G1 are isomorphic
then this three are pairwise isomorphic subgraphs.

I think examples will be clear to you now.

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Post by fh » Wed Jan 30, 2008 2:59 pm

Thx, emotional blind, just got it AC.
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Re: 11393 - Tri-Isomorphism

Post by yiuyuho » Mon Apr 07, 2008 5:59 am

sonyckson wrote:Well, i just wanna ask something, i did the "correct" solution ( at least the idea ) during the contest, but i thought the answer for input 1 was "YES" because you can have 3 empty lists of edges for each subgraph and ( as i see ) everything will be ok with the definitions given at the problem statement.... i got 2 WA during the contest, and another WA in another problem because of something similar, perhaps the same, i dont know what is it yet.... what im missunderstanding??? why the correct answer for input 1 is "NO"?? Thanks, Eric.
OK, so...why is the correct output for n=1 is NO? Is that a mistake?

Post Reply

Return to “Volume 113 (11300-11399)”