AIO 2021 Q6: Laser Cutter

Contest Source: AIO 2021

Observe that the top right corner and bottom left corner of an optimum square must always lie on the upper and lower boundaries respectively. If this were not the case, we would always be able to extend of the corners to form a bigger square. Also note that since it is a square, the two corners on the boundary must also lie on the same diagonal. This gives rise to a surprisingly simple solution!

We keep two positions \(a\) and \(b\), which correspond to the points on the top and bottom boundaries respectively. We loop a counter \(i\) from \(0\) to \(2N\) and at each iteration, we move the points \(a\) and \(b\) along their respective boundaries. Notice that by incrementing \(a\) and \(b\) at the same time, they will always be in the same diagonal, regardless of what their instructions are. We can now find the size of the square based on the coordinates of \(a\) and \(b\) and output the maximum square size. This is \(O(N)\), since it requires one loop through the top and bottom boundaries.

But in fact, we can do even better than this! Notice that the side length of the square only increases when \(a\) moves to the right and \(b\) moves down. Similarly, it decreases when \(a\) moves to down and \(b\) moves right. Finally, if \(a\) and \(b\) move in the same direction, then the side length of the square remains the same. This means that we don’t even need to keep track of the two points \(a\) and \(b\), just the directions that they move in! This gives us an extremely clean solution for this problem, shown below.

C++ Solution

#include <bits/stdc++.h>
using namespace std;

int main () {
    freopen("laserin.txt", "r", stdin);
    freopen("laserout.txt", "w", stdout);

    int N;
    cin >> N;
    string a, b;
    cin >> a >> b;

    int curr_length = 0;
    int best = 0;
    for (int i = 0; i < 2*N; i++) {
        if (a[i] == 'D' && b[i] == 'R') curr_length++;
        if (a[i] == 'R' && b[i] == 'D') curr_length--;
        best = max(best, curr_length);
    }
    printf("%d\n", best);

}