1

Recently, I came across a unique problem for which I couldn't find a complete solution.

I want to determine if a given rectangle is fully "compatible" (for the lack of a better word, please suggest if there is any) with all members of a given Polyomino set.

A rectangle is said to be "compatible" for a given member of a Polyomino set if it can be formed by using at least one of that given polyominoes and the rest can be any combination (with repetition) of all members of Polyomino set.

I am sure I have confused you by now, so here is the example, Consider a 4x4 rectangle with Tetrominoes. There exists at least one solution for all (I, O, Z, T, L) Tetrominoes. So it is compatible. Likewise 5x8 and 4x10 are compatible as they involve ALL tetrominoes.

For Trominoes, any rectangle with area A where A > 3 and A % 3 = 0 is compatible.

Please note that I am only interested in finding out if it is "Compatible", the actual solutions are not required.

I could find that there is no solution for all N-Ominoes where N >= 7, as they all involve at least one omino shape with a hole which is impossible to fill up without causing overlaps.

I am having trouble finding solution for 4,5 and 6-Ominoes.

I am sure someone out there would have worked this out.

Ravi M Patel
  • 113
  • this was problem D of the last google code jam, I guess they will post an analysis of the solution – Vicfred Apr 13 '15 at 07:13
  • Yes. I took part in it. They do post solution of contestants, I've seen one. But I am looking for an answer with mathematical proof. Not sure if Google provides complete solutions with analysis. – Ravi M Patel Apr 13 '15 at 07:19
  • They provided analysis of past contests' (as you can see on the page), I don't see why they wouldn't provide it this year. – Vicfred Apr 13 '15 at 07:21
  • Would you please send me a link for 2014? I looked, I couldn't find one. – Ravi M Patel Apr 13 '15 at 07:29
  • 1
    https://code.google.com/codejam/contests.html scroll down, there's analysis for every major past contest – Vicfred Apr 13 '15 at 08:39

0 Answers0