APIO '11 P1 - Table Coloring - DMOJ: Modern Online Judge

APIO '11 P1 - Table Coloring

View as PDF

Submit solution

All submissions

Best submissions

Points: 25 (partial)

Time limit: 1.0s

Memory limit: 256M

Problem types

Sam and his sister Sara have a table of $n \times m$ $n \times m$ square cells. they want to color all of the cells in red or blue. Due to personal beliefs, they want every $2 \times 2$ $2 \times 2$ square of the table to have odd number of red cells (i.e. 1 or 3). For example, a valid coloring of a $3 \times 5$ $3 \times 5$ table is drawn in the figure below.

Copy

B B R B R
R B B B B
R R B R B

Unfortunately, last night, someone had colored some of the cells of the table with red and some of the others with blue! Sam and Sara are wondering whether they can color the rest of the table such that no $2 \times 2$ $2 \times 2$ square contain an even number of red cells.

Input Specification

The first line of input contains three integers, $n$ $n$ , $m$ $m$ and $k$ $k$ , respectively the number of rows and columns of the table and the number of initially-colored cells. The following $k$ $k$ lines contain a description of the colored cells. The $i$ $i$ th line of this section contains three integers $x_i$ $x_{i}$ , $y_i$ $y_{i}$ , and $c_i$ $c_{i}$ , where $x_i$ $x_{i}$ and $y_i$ $y_{i}$ are the row number of column number of the $i$ $i$ th initially-colored cell and $c_i$ $c_{i}$ shows the color of the cell. $c_i$ $c_{i}$ is equal to 1 if that cell is colored in red and it is equal to 0 if the cell is colored in blue. It is guaranteed that these $k$ $k$ cells have distinct positions.

Output Specification

In a single line, write the number of possible ways of coloring the table (say $W$ $W$ ) modulo $10^9$ $10^{9}$ (i.e. if $W$ $W$ is greater than or equal to $10^9$ $10^{9}$ , write its remainder in division by $10^9$ $10^{9}$ ).

Constraints

For each description of initially colored cells, it is guaranteed that $1 \le x_i \le n$ $1 \leq x_{i} \leq n$ and $1 \le y_i \le m$ $1 \leq y_{i} \leq m$ .
Consider $2 \le n, m \le 10^5$ $2 \leq n, m \leq 10^{5}$ and $0 \le k \le 10^5$ $0 \leq k \leq 10^{5}$ in all of the test cases.
In $20\%$ $20 %$ of tests $n, m \le 5$ $n, m \leq 5$ and $k \le 5$ $k \leq 5$ .
In $50\%$ $50 %$ of tests, $n,m \le 5\,000$ $n, m \leq 5 000$ and $k \le 25$ $k \leq 25$

Sample Input

Copy

Sample Output

Copy

Comments

0

abednego commented on Dec. 20, 2023, 4:25 p.m.

Test inputs 10, 12, 14, 16, and 18 seem wrong. And the official solution on the USACO forums seems to have off-by-one errors. Please check.

3

xiaowuc1 commented on Dec. 24, 2023, 4:14 a.m.

The test data have been validated and cross-referenced using this blog post and several other reputable online judges. If you have further concerns, please use the "report an issue" functionality.

1

htoshiro commented on Dec. 21, 2023, 11:57 a.m.

people have solved the question???