SRM 700, D2, 500-Pointer (XMarksTheSpot)

James S. Plank

Tue Oct 25 15:18:18 EDT 2016
This one looks, feels, and smells like a power set enumeration. Because the number of question marks is at most 19, your power set enumeration will be at most 219 iterations, which is roughly 500,000. That fits easily into topcoder's time constraints.

Of course, what you do during each iteration has to be relatively fast, too.

Here's the outline of the solution:

Let's use Example 2 to illustrate. In this example, you have:

Your question marks are represented by the numbers 0, 1, 2 and 3 (for {0,3}, {1,0}, {3,2} and {4,4} ). Your power set enumeration will work as follows:

Subset Subset in hex The board Min row Max row Min col Max col Rectangle Size Final Sum
{ } 0x0
.....
.....
.O...
.....
.....
2 2 1 1 1 1
{ 0 } 0x1
...X.
.....
.O...
.....
.....
0 2 1 3 9 10
{ 1 } 0x2
.....
X....
.O...
.....
.....
1 2 0 1 4 14
{ 0 1 } 0x3
...X.
X....
.O...
.....
.....
0 2 0 3 12 26
{ 2 } 0x4
.....
.....
.O...
..X..
.....
2 3 1 2 4 30
{ 0 2 } 0x5
...X.
.....
.O...
..X..
.....
0 3 1 3 12 42
{ 1 2 } 0x6
.....
X....
.O...
..X..
.....
1 3 0 2 9 51
{ 0 1 2 } 0x7
...X.
X....
.O...
..X..
.....
0 3 0 3 16 67
{ 3 } 0x8
.....
.....
.O...
.....
....X
2 4 1 4 12 79
{ 0 3 } 0x9
...X.
.....
.O...
.....
....X
0 4 1 4 20 99
{ 1 3 } 0xa
.....
X....
.O...
.....
....X
1 4 0 4 20 119
{ 0 1 3 } 0xb
...X.
X....
.O...
.....
....X
0 4 0 4 25 144
{ 2 3 } 0xc
.....
.....
.O...
..X..
....X
2 4 1 4 12 156
{ 0 2 3 } 0xd
...X.
.....
.O...
..X..
....X
0 4 1 4 20 176
{ 1 2 3 } 0xe
.....
X....
.O...
..X..
....X
1 4 0 4 20 196
{ 0 1 2 3 } 0xf
...X.
X....
.O...
..X..
....X
0 4 0 4 25 221

My Solution (commented, and it prints out the html of the table above).