SRM 700, D2, 500-Pointer (XMarksTheSpot)

James S. Plank

Tue Oct 25 15:18:18 EDT 2016

Problem Statement.
A main() with the examples compiled in.
A skeleton that compiles with main.cpp.
tests.sh MD5 hash: 36e353260fcb0845779d14f51d51b39c
answers.txt MD5 hash: 064f7bcfd605c7b173b8e4df95572c11
Problem Given in Topcoder: October, 2016
Competitors who opened the problem: 281
Competitors who submitted a solution: 91
Number of correct solutions: 56
Accuracy (percentage correct vs those who opened): 19.9%
Average Correct Time: 34 minutes, 53 seconds.
Program to create a random board: gen_random_board.cpp

In case Topcoder's servers are down

Here is a summary of the problem:

You are given a vector of strings called board.
Each string in board is the same size, and is composed of the characters '.', 'O' or '?'.
board has at most 50 rows.
Each element of board has at most 50 characters.
There are at most 19 '?' characters.
There is at least one 'O' character.
To evaluate the board, you will be able to set each question mark either to 'O' or '.'.
For a given setting of the question marks, define the following variables:
- c is the index of the leftmost column containing an 'O'.
- C is the index of the rightmost column containing an 'O'.
- r is the index of the smallest row containing an 'O'.
- R is the index of the biggest row containing an 'O'.
- score is (C-c+1) * (R-r+1).
Return the sum of the scores for each possible setting of the question marks.

Let's go over Example 0, where board is:

"?."
".O"

If the question mark is set to '.', then:

c = 1
C = 1
r = 1
R = 1
score = 1

If the question mark is set to 'O', then:

c = 0
C = 1
r = 0
R = 1
score = 4

So the answer is 5.

The examples

Example	Board	Answer
0	"?." ".O"	5
0	"???" "?O?" "???"	1952
0	"...?." "?...." ".O..." "..?.." "....?"	221
0	"OOOOOOOOOOOOOOOOOOOOO"	21
0	"?????????OO??????????"	9963008
0	"OOO" "O?O" "OOO" "..."	18

Testing yourself

I have a shell script tests.sh , that you can use to test your program. When you run tests.sh, your answer should be identical to answers.txt.

Hints

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 2¹⁹ 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:

For each question mark, store its row number in a vector called QR.
For each question mark, store its column number in a vector called QC.
Go through the board, and store the minimum and maximum row numbers of the monuments.
Go through the board, and store the minimum and maximum column numbers of the monuments.
Set the return value to zero.
Do a power set enumeration, enumerating all subsets of question marks. Within the enumeration:
- See whether a question mark which is part of the subset changes the minimum or maximum monument row or column, and if so, make that change. You'll do that by checking QR and QC.
- Calculate the size of the rectangle defined by the minimum/maximum row and column numbers, and add this to the return value.
Return the return value.

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

QR = { 0, 1, 3, 4 }
QC = { 3, 0, 2, 4 }
Minrow = 2
Maxrow = 2
Mincol = 1
Maxcol = 1

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