Mock CCC '20 S2 - Flipper Redux - DMOJ: Modern Online Judge

Mock CCC '20 S2 - Flipper Redux

View as PDF

Submit solution

All submissions

Best submissions

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$ ~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$ ~N~.

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

Output Specification

If the puzzle is unsolvable, print -1.

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

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

Each operation must be one of the following:

R x_i: Flip all squares in row $x_i$ ~x_i~
C x_i: Flip all squares in column $x_i$ ~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$ ~0 \le M \le 4 \times 10^3~.

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

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

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

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

Sample Input 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

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$ ~N \leq 2000~ but your 2d array is $1000$ ~1000~ by $1000$ ~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.

I just give M = 4, N= 4, what if M=4000, N=2000? you need around 5999 operations > 4000, which actually should be 1 operation!

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

I saw lots of submitted code is wrong, but they still got full points. For example, both of the following 2 cases should have 1 operation, but some solutions have 7 operations.

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

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

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$ ~M = 7~, with some trivial substitution or the clever proof by kevinyang below we get that $0\le M = 7\le 4000$ ~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$ ~7\leq 4000~ is valid.
To show $7\leq 4000$ ~7\leq 4000~, I can either choose to show either $7<4000$ ~7<4000~ or $7 = 4000$ ~7 = 4000~.
In this proof, I will show $7<4000$ ~7<4000~

My very smart friend AQT showed me that $x < x+1$ ~x < x+1~ and I will use this to prove $7 < 4000$ ~7 < 4000~.
$x < x+1$ ~x < x+1~ can be used to show that $x < x + 1 + 1$ ~x < x + 1 + 1~. Now, we have this inequality $x < x+2$ ~x < x+2~.
We can use induction to show that $x < x+n$ ~x < x+n~ for any positive integer $n$ ~n~. Let $n$ ~n~ be $3993$ ~3993~ and let $x$ ~x~ be $7$ ~7~.
If we substitute these values back into $x < x+n$ ~x < x+n~, we obtain $7 < 4000$ ~7 < 4000~.
Since $7$ ~7~ operations fit the bounds of this problem, the solutions you claim that have $7$ ~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