Topcoder SRM 639, D1, 500-Pointer “BoardFolding”
James S. Plank
EECS Department University of Tennessee
CS494/594 Class August 26, 2019
●
You are given a rectangular grid with R rows and C columns.
● ●
Each entry of the grid is either 0 (white) or 1 (grey).
The problem
You may “fold” the grid along the seam between rows or columns as long as the smaller portion goes on top of the larger portion, and the two portions match exactly.
Fold along this seam
Fold along this seam
Fold along this seam
Fold along this seam
●
If the two portions are of equal size, then either portion may go on top of the other.
●
Another way to visualize folding is to simply delete the part of the rectangle that goes on top.
The problem (continued)
This grid may be folded in half in either way.
The problem (continued)
Suppose we label the result of zero or more folds by:
– x: Column number of the resulting left column, in the original grid.
– y: Row number of the top row in the original grid. – w: Width of the resulting grid
– h: Height of the resulting grid
– Label it [x,y,w,h]
[0,0,4,4]
[0,0,4,2]
[0,2,4,2]
Given a starting grid, how many unique labelings can result from
Example 2 [0,0,4,4]
[0,0,4,2]
[0,0,2,2]
zero or more folds?
The problem (continued)
Answer = 9
[2,0,4,2]
[0,2,2,2]
[0,0,2,4]
[2,2,2,2]
[0,2,2,4]
[2,0,2,2]
● ● ●
Class name: BoardFolding Method: howMany() Parameters:
● ●
Return Value: int
Constraints: R and C are between 0 and 250.
R
int
Number of rows Number of columns
The grid (in compressed format)
C Grid
int
vector
Prototype and Constraints
– (which is roughly 28)
Thought Number 1 – Enumeration?
x & w:
y & h:
How many potential [x,y,w,h] are there?
● C columns with width 1
● (C-1) columns with width 2 ● (C-2) columns with width 3
● R rows with height 1
● (R-1) rows with height 2 ● (R-2) rows with height 3
MN
Σi ≈ (28*28) = 216 Σi ≈ (28*28) = 216
i =1
i =1
In total:
(x & w) * (y & h) = 232
That’s too slow!
●
The horizontal and vertical folds are independent!
Thought Number 2
You can make horizontal folds here, regardless of when you make
● Count the horizontal folds ● Count the vertical folds
● Multiply the results
the vertical folds.
You can make vertical folds here, regardless of when you make the
horizontal folds.
Thought Number 2 – Enumeration?
When Horizontal and Vertical folds are Independent
x & w:
y & h:
● C columns with width 1
● (C-1) columns with width 2 ● (C-2) columns with width 3
● R rows with height 1
● (R-1) rows with height 2 ● (R-2) rows with height 3
MN
Σi ≈ (28*28) = 216 Σi ≈ (28*28) = 216
i =1
i =1
In total:
(x & w) + (y & r) = 217
Thats better!
● ●
How do we count the [x,w] combinations? How do we count the [y,h] combinations?
No 0
Yes 1
rv = { 1, 0, 1, 0, 1, 0, 1, 0, 0 }
No 0
Yes 1
No 0
Yes 1
No 0 No 0
Details
vector
Return vector has (R+1) zero or one entries rv[i]=1 iff row i can be a starting row.
●
–
Yes 1
●
You can use starting_places() to identify the potential ending rows too (reverse the Grid and then reverse the return value):
No 0 No 0 Yes 1 No 0 Yes 1 No 0 Yes 1 No 0 Yes 1
rv = { 0, 0, 1, 0, 1, 0, 1, 0, 1 }
Details
vector
●
Now, count all combinations of starting and ending rows that have positive height:
SE
Details
S: { 1, 0, 1, 0, 1, 0, 1, 0, 0 }
E: { 0, 0, 1, 0, 1, 0, 1, 0, 1}
●
Now, count all combinations of starting and ending rows that have positive height:
SE
Details
S: { 1, 0, 1, 0, 1, 0, 1, 0, 0 }
E: { 0, 0, 1, 0, 1, 0, 1, 0, 1}
●
Now, count all combinations of starting and ending rows that have positive height:
SE
Details
S: { 1, 0, 1, 0, 1, 0, 1, 0, 0 }
E: { 0, 0, 1, 0, 1, 0, 1, 0, 1}
●
Now, count all combinations of starting and ending rows that have positive height:
SE
Details
S: { 1, 0, 1, 0, 1, 0, 1, 0, 0 }
E: { 0, 0, 1, 0, 1, 0, 1, 0, 1}
●
Now, count all combinations of starting and ending rows that have positive height:
SE
Details
S: { 1, 0, 1, 0, 1, 0, 1, 0, 0 }
E: { 0, 0, 1, 0, 1, 0, 1, 0, 1}
And So On.
●
Now, count all combinations of starting and ending rows that have positive height:
SE
Details
S: { 1, 0, 1, 0, 1, 0, 1, 0, 0 }
E: { 0, 0, 1, 0, 1, 0, 1, 0, 1}
In this example, there are ten combinations.
●
Do the same for starting and ending columns:
S
S
6 combinations
E
Details
S: { 1, 0, 1, 0, 0, 0, 0, 0 }
E: { 0, 0, 0, 0, 0, 1, 1, 1 }
●
You can use the same starting_places() procedure for rows, columns, starting and ending places (just transpose and/or reverse the grid).
●
●
Finally multiply the number of [x,w]combinations by the number of [h, r] combinations.
Details
vector
●
Given an index j, how can we determine that j isa starting row index?
Running Time
vector
– There must be a rectangle of height w such that:
– Row j-w is a starting row index.
– The rectangle of height w above j is the mirror image of the rectangle of height w below j.
j =2
w =2
S
● ● ●
My initial realization of this was O(n3). Iterate i from 0 to n.
If i is a starting row, then for each j > i:
O(n)
Running Time
vector
– See if the rectangle from i to j matches the rectangle from j to j+(j-i).
– If so, then j is a starting row as well.
i =0 j =2
S
w =2
It was fast enough for Topcoder.
● ● ●
One way to make it O(n2):
Iterate j from 0 to n.
Calculate the maximum w for each j and store it.
O(n2)
●
Now repeat the previous algorithm.
O(n2) w =2
j =2
Running Time
vector
S
● ●
Another way to make it O(n2):
Iterate j from 0 to n.
Iterate w from 1 to j.
If the rectangles of width w above and below j match, and j-w is a starting row, then j is a starting row.
● ●
j =2
w =2
Running Time
vector
S
O(n)
O(1)
●
You call starting_places() four times. – O(n2).
●
Setting up the Grid for starting_places(): – O(n2).
Running Time Summary
Calculating the combinations: That’s O(n2) overall.
●
– O(n2).
● ●
So, with n = 256, this should be fast enough, and indeed it is.
●
Yes – you can remove the string comparison by turning each string into an integer:
Can you make it faster?
012
0 1
0 1 1 0 0 1 1 0
0110222
● ●
MacBook Pro 2.4 GHz Difficult Grid.
Experiment
●
A pretty tough one:
How did the Topcoders Do?
– – – – – –
476 (of 534) Topcoders opened the problem. 130 (27%) submitted a solution.
83 (64%) of the submissions were correct. That’s 17.2% of those who opened the problem. Best time was 12:23
Average correct time was 39:07.
Topcoder SRM 639, D1, 500-Pointer “BoardFolding”
James S. Plank
EECS Department University of Tennessee
CS494/594 Class August 26, 2016