Mock CCC '20 S2 - Flipper Redux

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M

Author:
Problem types

Recently, Plasmatic got into flipper puzzles! A flipper puzzle is an grid with black and white squares. At any point, Plasmatic can flip all the squares in a single row or column, changing the respective squares from black to white and white to black. Furthermore, a flipper puzzle is considered solved when all the squares are black.

However, when Plasmatic began working on his flipper puzzle the other day, he found that no matter how he flipped the rows and columns he couldn't solve it. After raging on the puzzle for a few hours he came to the conclusion that the puzzle had been tampered with and threw it in the trash.

Now, seeing this as a perfect opportunity to have some fun, ChrisT took Plasmatic's puzzle and began solving it. This time though, ChrisT chose to write a program to help him accomplish his task. But due to his subpar programming skills, he wasn't able to finish the program. Can you help him?

Input Specification

The first line of input contains the integer .

The next lines each contain space separated integers, with the integer on line denoting the value of , the number on the row on the final configuration.

Output Specification

If the puzzle is unsolvable, print -1.

Otherwise, first output an integer , the number of moves needed to solve the puzzle. Next, output more lines, denoting the operations needed to solve the puzzle. If there are multiple answers, output any of them.

Note that doesn't have to be minimal, it just has to be .

Each operation must be one of the following:

• R x_i: Flip all squares in row
• C x_i: Flip all squares in column

Note that the rows count from top to bottom and columns count from left to right.

Constraints

In your output, .

For 1 out of 15 available marks, .

For an additional 3 out of 15 additional marks, .

Sample Input 1

3
1 0 0
1 0 0
0 1 1

Sample Output 1

2
R 3
C 1

Note that the rows count from top to bottom and columns count from left to right.

Sample Input 2

3
0 0 0
1 0 0
0 0 0

Sample Output 2

-1

• commented on Feb. 28, 2021, 3:04 p.m.

can someone take a look at my submission? I failed batch 4.

submission: https://dmoj.ca/src/3459073

• commented on Feb. 28, 2021, 4:55 p.m.

The problem statement says that but your 2d array is by .

• commented on Feb. 28, 2021, 6:33 p.m.

Nice catch! I should probably pay more attention.

• commented on Feb. 26, 2021, 12:17 a.m.

This comment is hidden due to too much negative feedback. Show it anyway.

• commented on Feb. 26, 2021, 8:44 a.m. edit 5

means you output operations, and . I'm not sure if you are using some translator service to view the problems, or just have a poor understanding of the English language, but please refrain from cluttering up the comments section with content irrelevant to the actual problem.

• commented on Feb. 26, 2021, 3:21 a.m. edited

As I said below, please read the problem AND input constraints entirely and carefully. 🤡

• commented on Feb. 25, 2021, 2:50 a.m.

This comment is hidden due to too much negative feedback. Show it anyway.

• commented on Feb. 25, 2021, 9:37 p.m.

By observing the Output Specification, we see that Plasmatic specifically wrote:

Note that M doesn't have to be minimal, it just has to be ≤4000.

in your case , with some trivial substitution or the clever proof by kevinyang below we get that . Therefore the solutions by the people you mentioned are valid.

In addition, I think it is very important to read the entire problem and think if the comment your posting is helpful for others, or will it just look like a meme.

• commented on Feb. 11, 2022, 10:26 a.m.

boo

• commented on Feb. 25, 2021, 9:13 p.m.

Hello ybao2000,

You're right! Both these cases can be solved in one operation. However, as stated in the output specification, your solution does not need to minimize the number of operations used. Solutions outputting 7 operations on these cases should score full points.

For future reference, you can display sample cases in the following format

4
1 1 1 1
0 0 0 0
0 0 0 0
0 0 0 0

by starting with a line of three backticks `, followed by your sample, followed by another line of three backticks.

• commented on Feb. 25, 2021, 9:09 p.m. edit 2

Note that M doesn't have to be minimal, it just has to be ≤4000.

Now, I will attempt to prove that is valid.
To show , I can either choose to show either or .
In this proof, I will show

My very smart friend AQT showed me that and I will use this to prove .
can be used to show that . Now, we have this inequality .
We can use induction to show that for any positive integer . Let be and let be .
If we substitute these values back into , we obtain .
Since operations fit the bounds of this problem, the solutions you claim that have operations are now proven to be valid based on the constraints on the problem.
I hope this clears up any confusion you have.

• commented on Feb. 25, 2021, 9:38 p.m.

orz