2016 Canadian Computing Olympiad

Day 2, Problem 1 - O Canada

In this problem, a grid is an N-by-N array of cells, where each cell is either red or white.

Some grids are similar to other grids. Grid A is similar to grid B if and only if A can be transformed into B by some sequence of changes. A change consists of selecting a 2-by-2 square in the grid and flipping the colour of every cell in the square. (Red cells in the square will become white; white cells in the square will become red.)

You are given G grids. Count the number of pairs of grids which are similar. (Formally, number the grids from 1 to G, then count the number of tuples (i, j) such that 1 ≤ i < j ≤ G and grid i is similar to grid j.)

Input Format

The first line of input contains N (2 ≤ N ≤ 10), the size of the grids.
The second line contains G (2 ≤ G ≤ 10 000), the number of grids.
The input then consists of N·G lines, where each line contains N characters, where each character is either R or W, indicating the colour (red or white) for that element in the grid. Moreover, after the first two lines of input, the next N lines describe the first grid, the following N lines describe the second grid, and so on.

For 12 out of the 25 marks available for this question, 2 ≤ G ≤ 10.

Output Format

Output the number of pairs of grids which are similar.

Sample Input

2
2
RW
WR
WR
RW

Sample Output

1

Explanation

There are exactly two grids, and they are similar because the first grid can be transformed into the second grid using one change (selecting the 2-by-2 square consisting of the entire grid).

All Submissions
Best Solutions

Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 64M
Added: May 14, 2016
Author: nullptr

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I believe G can be as large as 10000. The original problem statement seems to have the correct limits:
https://cemc.math.uwaterloo.ca/contests/computing/2016/stage%202/day2.pdf

Fixed.