LCC '22 Contest 4 S5 - Nita's Summer Splash

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Java 3.5s
Python 3.5s
Memory limit: 256M

Author:
Problem type

Nita and Bruce are making a splash at the beach! With so many waves, Nita wants to make sure that the beach is safe for everyone to swim in.

Currently, the beach is a H by W grid with the water level in each cell being either 0 or 1. Whenever a cell of the grid is splashed, the water level at that cell changes to 1 if it was 0 or to 0 if it was 1.

Nita wants to calm the entire area of the beach to level 0, but she can only perform two types of operations:

  1. Rupture: Nita splashes all the cells in an entire row or column.
  2. Bear Paws: Bruce splashes any 2 by 2 subgrid of the beach.

Help Nita and Bruce to convert the water level of every cell of the beach to 0!

Input Specification

First line: H and W (the height and width of the beach respectively).

An H \times W grid of 0s and 1s follows, describing the initial state of the beach.

Output Specification

There are two parts for the output:

Part 1: If it is solvable, print Y. Otherwise, print N. (Producing a correct answer for Part 1 in any subtask earns you 75% of the marks for that subtask).

Part 2: If it is solvable, print an integer K stating the number of operations in your proposed solution.

On the next K lines, list the operations you used to solve the puzzle. More specifically,

  • R x splashes all cells in row x
  • C x splashes all cells in column x
  • G x y splashes the 2 \times 2 grid with the top left corner at row x column y.

If multiple valid solutions exist, any one of them will be accepted. K does not need to be minimal but should not exceed 10^6.

Constraints

In all test cases, 2 \le H, W \le 1000

Subtask 1 [20%]

2 \le H, W \le 3

Subtask 4 [80%]

No additional constraints.


Remember: for all subtasks, you will be awarded 75% of the available points for producing a correct answer for Part 1 of the output specification, regardless of your output for Part 2.

Sample Input 1

3 3
1 0 1
1 1 0
0 0 1

Sample Output 1

Y
4
C 1
C 3
R 3
G 2 2
Explanation for Sample Case 1

Nita splashes column 1, leaving

0 0 1
0 1 0
1 0 1

Then splash column 3, leaving

0 0 0
0 1 1
1 0 0

Then splash row 3, leaving

0 0 0
0 1 1
0 1 1

Finally, splash the 2 \times 2 subgrid with a top-left corner at (2, 2), leaving

0 0 0
0 0 0
0 0 0

Note: if you had simply outputted Y without listing the operations, you would have earned 75% of the points.


Comments

There are no comments at the moment.