17.23 has an N^2logN solution

[matthewschallenkamp]

You can solve 17.23 in N^2logN time using a trick from the ICPC World Finals problem triangles.
It will be helpful to read the problem and watch the solution video first

https://icpc.kattis.com/problems/triangles3
https://www.youtube.com/watch?v=0LqHpmzRHzk

So we apply the same trick as the triangles, except in this case we aren't looking to count the number of results but instead find the largest square that connects to a given bottom right index. As a result, we'll use a binary search tree instead of a segment tree.

First lets calculate the length of 0's in each direction from each square and store them. I'll refer to these by their direction (up, etc).

Now lets walk a diagonal from the top left to the bottom right and keep a tree that contains the top left corners that could possibly make a square with the current bottom right corner based on their lengths right and down. Each time we step on a new square we will need to do three things:

1. Do a search in our tree for the smallest coordinate greater than or equal to min(up, left) of this square. That coordinate (if it exists) forms the largest possible square with this as the bottom right endpoint. If this is the largest square so far, save it.
2. Add the current coordinates into the tree and set a marker in our array right and down min(right, down) of this square. This will tell us when we should remove these coordinates from the tree.
3. Take all the markers at these coordinates and remove them from the tree, as they will not be able to form a square with the next coordinate on this diagonal.

If we do this for each diagonal we have O(N^2) to preprocess the directional lengths, O(N^2 * log(N)) for the searches in our tree, O(N^2 * log(N)) for the inserts into our tree, and O(N^2 * log(N)) for the removals from our tree. This is O(N^2 * log(N)) time total.

[matthewschallenkamp]

Seltsamonkel,

Your algorithm will correctly find filled squares, but I suspect it will not find unfilled ones. How does your algorithm handle the case:

XXXX
XXOX
XOOX
XXXX

?

[seltsamonkel]

Hi Matthew,

Oh heck, I was understanding the question as "subsquare such that all the cell are black"! Thanks,,,,