Editorial for Colored Cubes


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.
Analiz ve Çözüm Yolu

N tane karemiz var. Küpün üst, alt, ön, arka, sağ ve sol yüzleri için kare seçebileceğimiz farklı yol sayısı \(\binom{N} {6}\) yani en fazla 177100 olabilir (\(N \le 25\) olduğu için). Böylece verilen karelerin kombinasyonlarını kullanarak tüm olası küpleri oluşturabiliriz.

Bir küpü 24 şekilde döndürebiliriz. En küçük dönüşü, en küçük üst yüzey renkli olanla tanımlayalım. Eğer böyle birden fazla döndürme yolu varsa, en küçük ön yüz rengi ardından sol yüz rengi, arka yüz rengi ve sağ yüz rengi olanı alalım. Elde edilen algoritma şu:

  • olası tüm küpleri oluştur;
  • her küp için en küçük dönüşümünü bul;
  • farklı küp dönüşümlerinin sayısını bul (mesela önce sıralayarak).

Analysis and Guide for Solution

We have \(N\) squares. The number of ways to choose squares for top, front, left, rear, right and bottom cube faces is \(\binom{N} {6}\) which is at most 177100 (since \(N \le 25\)). Thus we can construct all possible cubes using combinations of the given squares.

For each cube there are 24 ways to rotate it. Let's define the smallest rotation as the one with the smallest top face color. If there are multiple such rotations take the one with the smallest front face color, then left face color, then rear face color, then right face color. Now our algorithm is the following:

  • generate all possible cubes;
  • for each cube find its smallest rotation;
  • count the number of distinct smallest cube rotations, e.g. by sorting them first.