You are given a shape defined by the area between two walks (a lower walk and an upper walk) from the top left corner of the coordinate grid \((0,\,0)\) to the bottom right corner of the coordinate grid \((N,\,N)\).
Each walk is given as a sequence of \(2N\) instructions that specify whether to move Down or Right one space.
These two walks to not intersect, except at the start and end.
What is the side length of the largest square that fits inside this shape?
The best way to work through this problem is to draw out some examples by hand. You will notice some patterns that can help you with your algorithm.
For any shape, the top-right corner of a largest square must be touching the upper walk and the bottom-left corner of the square must be touching the lower walk.
The square that initially appears in the diagram is clearly not the largest square, becuase since it does not touch the corners, we can expand it until it does.
This property may seem a bit obvious when written out, but it is very powerful. What we have done is greatly narrow down the search possibilities for the largest possible square.
What we can do once we discover this observation is compare each possibility of top-left and bottom-right corner along the edge of the walks. If it forms a square, then compare it with the largest side length found so far. However, this algorithm is too slow for Subtask 4 since it has to pair up every point on the upper walk with every point on the lower walk. The time complexity (for those who are interested) would be \(\mathcal O\left(N^2\right)\).
This algorithm is fast enough to pass subtasks 2 and 3, though, where \(N\) is only up to 1000.
Readers may notice that it is very inefficient to check if a shape forms a square, since only a small number of pairs of points actually form squares. This may lead you to make the next observation:
For each point on the upper walk, there is exactly one point on the lower walk which forms a square with it. This square will always be inside the shape.
If we draw a diagonal line from our point on the upper walk, we see that it crosses exactly one point on the lower walk. This means that we can once more significantly reduce the number of possibilities that we have to consider.
In fact, the \(i\)th point along the top walk can always be matched with the \(i\)th point along the lower walk to form a square.
From the above observation, all we need to do in our program is maintain the positions of the two walks as we go through the instructions, and then store the side length of the corresponding square. However, as simple as this may sound, there is an even simpler way!
Along the sequence:
D and \(B_i\) equals R, the side length of the square formed increases by 1.R and \(B_i\) equals D, the side length of the square formed decreases by 1.Our full solution can hence be written as a single for loop and two if statements, as shown in the Code section.
(Note: There are also a couple of other ways to write the for loop for this problem. See if you can find one that is shorter than the code I presented!)
infile = open("laserin.txt", "r")
outfile = open("laserout.txt", "w")
# Read in our N, A and B
N = int(infile.readline())
A = infile.readline()
B = infile.readline()
# Store our current length
cur_length = 0
ans = 0
for i in range(2*N):
if A[i] == 'D' and B[i] == 'R':
cur_length = cur_length + 1
if A[i] == 'R' and B[i] == 'D':
cur_length = cur_length - 1
ans = max(ans, cur_length)
outfile.write(str(ans) + "\n")