AmoebaDivOne

SRM 493 · 2010-11-01 · by K.A.D.R

SRM 493 · 2010-11-01 · by K.A.D.R · Dynamic Programming

Show categories

Class Name: AmoebaDivOne

Return Type: int

Method Name: count

Arg Types: (vector<string>)

Problem Statement

Little Romeo likes cosmic amoebas a lot. He has a colony of all kinds of amoebas. Recently he received a rectangular table as a gift from his mother. He decided to place one of his amoebas on it. The table is a grid of square 1x1 cells, and each cell is occupied by either matter or antimatter. The usual shape of a cosmic amoeba is a convex set of cells (see explanation below). Romeo can place it on the table as long as every cell of the table is either completely covered by part of the amoeba or completely uncovered, and no part of the amoeba lies outside of the table. It is a well-known fact that cosmic amoebas cannot lie on top of matter, so every cell of the table covered by the amoeba must only contain antimatter.

A set of cells is called connected if there exists a path between each two cells from the set which satisfies the following restrictions:

All cells in the path belong to this set.
Each pair of neighboring cells in the path shares a common edge.

A set is called convex if it is satisfies the following conditions:

It is connected.
If any two cells in the set lie in the same row then all cells in that row between them also belong to the set.
If any two cells in the set lie in the same column then all cells in that column between them also belong to the set.

You are given a String[] table containing only lowercase hexadecimal digits. Numbers 0-9 are represented by characters '0'-'9', and numbers 10-15 are represented by characters 'a'-'f'. Each digit in table represents a 2x2 section of the table. For each digit table[i][j], let n be its 4-digit binary representation. From this, you can determine the contents of the following cells:

row 2*i, column 2*j: n[0]
row 2*i, column 2*j+1: n[1]
row 2*i+1, column 2*j: n[2]
row 2*i+1, column 2*j+1: n[3]
where 0 represents antimatter, and 1 represents matter. For example, if table[0][0] = '5', then its 4-digit binary representation is "0101" (bits are numerated from right to left), and that section of the table looks like this:

      |  column 0  |  column 1  |
------|------------|------------|
row 0 |   matter   | antimatter |
------|------------|------------|
row 1 |   matter   | antimatter |
------|------------|------------|

Now Romeo wonders how many ways there are to place a single amoeba on the table. Return this number modulo 1000000007. Two ways are considered different if and only if there is a table cell that is covered in one but not the other.

Constraints

table will contain between 1 and 50 elements, inclusive.
Each element of table will contain between 1 and 50 characters, inclusive.
All elements of table will have the same length.
Each character in table will be a hexadecimal digit ('0'-'9', 'a'-'f').

Examples

{"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000"}
Returns: 420700828

100x100 empty grid

{"0"}
Returns: 13

Here are all 13 configurations, where X represents the amoeba: X. .X .. .. XX .. X. .X XX XX X. .X XX .. .. X. .X .. XX X. .X X. .X XX XX XX

{"84","21"}
Returns: 72

Here the table looks like this ('.' stands for cell with antimatter and '#' stands for cell with matter): .... .##. .##. ....

{"e","e"}
Returns: 2

{"00"}
Returns: 90

Submissions are judged against all 59 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class AmoebaDivOne with a public method int count(vector<string> table) · 59 test cases · 2 s / 256 MB per case