0
$\begingroup$

I was practising interesting problems from past problem solving contests when I found this one. I guess that I should find some hash functions to find the candidates and check them by hand. I tried writing down the degrees and solved the 1st part, I1 and D6, but I am stuck at 2nd and 3rd part. I also found the solution booklet but it doesn't contain the exact solutions.

What are the exact solutions for 2nd and 3rd parts?

The original problem statement:

The input file contains a coordinate grid with 10 × 10 similar-looking shapes. Among those 100 shapes there are exactly three matching pairs of shapes:

  • Two shapes are identical. (One can be obtained from the other by rotation and translation only.)
  • Two shapes are mirror images of each other. (They are not identical as defined above, but one can be obtained from the other by flipping it once and then rotation and/or translation.)
  • Two shapes are complements of each other. (Explained below.)

As you can see from the input file, the shapes are actually pictures of simple graphs on 7 vertices. “Complements” should be interpreted in that sense. Two shapes are complements of each other if one of them can be rotated and translated – without flipping – and placed on top of the other in such a way that their vertices coincide and each pair of vertices is connected by an edge in exactly one of the two graphs.

Given Input

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

You were on the right track when you said

I guess I should find some hash functions to find the candidates and check them by hand.

A simple process you could follow could be

1) Order the 21 possible edges somehow, and generate the corresponding 21-bit signature for each graph.
2) For each signature, generate all 28 possible rotations, reflections, and complements, and assign the one with the smallest numerical value to that graph.
3) Once all graphs have been assigned a signature, see which signatures have been assigned to two graphs. (This is possible in many ways: one such is to place the graphs in a data structure that can be efficiently indexed by signatures, and then look for entries with length two.) There should be three of these: One will be assigned to I1 and D6, another will be assigned to the pair in Part 2, and the third will be assigned to the pair in Part 3.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I tried something similar, but I couldn't find the pairs for Part 2 and Part 3, could you? $\endgroup$
    – Tutan Kamon
    Commented Jun 27 at 7:47
  • $\begingroup$ No, because I don't know how to have a program read an image. $\endgroup$
    – AxiomaticSystem
    Commented Jun 28 at 11:02
1
$\begingroup$

Using a method that is essentially the same as AxiomaticSystem's suggested process, we find the following pairs:

The identical shapes are

enter image description here

The mirror-image shapes are

enter image description here

The complimentary shapes are

enter image description here

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.