Mock CCC '20 S2 - Flipper Redux

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 2.0s
Memory limit: 512M
Author:
Plasmatic
Problem types

Recently, Plasmatic got into flipper puzzles! A flipper puzzle is an N \times N 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 N.

The next N lines each contain N space separated integers, with the j^\text{th} integer on line i denoting the value of a_{i, j}, the j^\text{th} number on the i^\text{th} row on the final configuration.

Output Specification

If the puzzle is unsolvable, print -1.

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

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

Each operation must be one of the following:

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

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

Constraints

For all subtasks:

In your output, 0 \le M \le 4 \times 10^3.

1 \le i \le N \le 2 \times 10^3

0 \le a_{i, j} \le 1

For 1 out of 15 available marks, 1 \le N \le 2.

For an additional 3 out of 15 additional marks, 1 \le N \le 10.

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

Comments


  • 1
    herro  commented on Feb. 28, 2021, 8:04 p.m.

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

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


    • 2
      kevinyang  commented on Feb. 28, 2021, 9:55 p.m.

      The problem statement says that N \leq 2000 but your 2d array is 1000 by 1000.


      • 4
        herro  commented on Feb. 28, 2021, 11:33 p.m.

        Nice catch! I should probably pay more attention.


  • -9
    ybao2000  commented on Feb. 26, 2021, 5:17 a.m.

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


    • 2
      Plasmatic  commented on Feb. 26, 2021, 1:44 p.m. ← edit 5

      M=4000 means you output 4000 operations, and 4000\neq 5999. 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.


    • 6
      Dan13llljws  commented on Feb. 26, 2021, 8:21 a.m. ← edited

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


  • -14
    ybao2000  commented on Feb. 25, 2021, 7:50 a.m.

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


    • 15
      Dan13llljws  commented on Feb. 26, 2021, 2:37 a.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 M = 7, with some trivial substitution or the clever proof by kevinyang below we get that 0\le M = 7\le 4000. 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.


      • -3
        Lonerrr  commented on Feb. 11, 2022, 3:26 p.m.

        boo


    • 23
      mangoqwq  commented on Feb. 26, 2021, 2:13 a.m. ← edited

      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.


    • 45
      kevinyang  commented on Feb. 26, 2021, 2:09 a.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 7\leq 4000 is valid.
      To show 7\leq 4000, I can either choose to show either 7<4000 or 7 = 4000.
      In this proof, I will show 7<4000

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


      • 22
        thomas_li  commented on Feb. 26, 2021, 2:38 a.m.

        orz