Sorry! Yes, We had scheduled it long back and have some product updates afterwards! So won’t be able to move this one.

SG value of a single cell (r,c) can be computed in O(rc) time if you know all SG values (x,y) in the rectangle from (0,0) to (r,c). This is done in the traditional way: try all the rectangles with bottom right at (r,c) and for each of them compute the xor of the SG values of all cells in the rectangle other than (r,c).

(Note that the naive way to do the above is in O(r^2c^2) because you have O(rc) rectangles and you do O(rc) xor-ing for each of them. Still, it's easy to improve it to O(rc) using essentially the same DP that is used for 2D prefix sums.)

Once you realize that in this problem SG(r,c) is some unknown function f of SG1(r) and SG2(c), and that those values are always powers of two, you only need to compute f(2^i,2^j) for all i,j <= 16, and you do this by computing each of the values SG((2^i)-1, (2^j)-1) in the way I described above.

I've used to think in the same way, but then I realized that I enjoy such problems as well. Googling can be seen as just another way of coming up with new (for you) knowledge that complements making logical deductions yourself. Both are integral parts of real research work, for example.

I don't see why you put those into one bag, "problems about patterns" and "googling problems" are two very different things.

When doing research I quite often needed to discover a pattern, generalize it and prove it. In some competition types you can practice all three steps, but in practical programming contests the best you can get are the first two. (And if one occasionally encounters a problem in which the straightforward generalization is wrong, it can push them towards at least spending some time thinking about whether and why their generalization is correct. Such problems are rare but I've already seen a few.) Discovering nice patterns can be cool, and finding the right generalization is non-trivial creative work.

Regarding googling, there are multiple types of googling problems, and pattern problems are not necessarily googling problems (and vice versa). For example, I see quite a difference between 1) problems where you read the problem statement and it essentially tells you that you need to google obscure properties of planar cubic graphs, 2) problems where you just write a brute force solution and plug its output into OEIS without thinking, 3) problems where you need to do some thinking and some coding to discover what to search for in the first place, and 4) problems from category 3 where your search ends up unsuccessful, either because the problem managed to obscure a known sequence enough or because the sequence wasn't noteworthy enough so far.

Regarding this div1 1000, I still like it a lot because the target group of people 1) has the option to solve it as a problem that is about recognizing and generalizing patterns, and as I mentioned elsewhere in this thread, the fact that after the right generalization one can write a full solution that does not require googling (but does require deep understanding of SG theory) is a big plus in my book; and then 2) has the option to learn about a nice bit of theory by reading the editorial and following up with some CGT resources.

But to each its own. We are not required to like the same types of problems.