In the last two hours I have been went through a quite exciting SRM. I didn't solve any problems during the macth. (In fact, I didn't open 250 at all. But it seems to be a nice choice, isn't it? :D) All my time went to 500 problem. I found it quite interesting. And I spend a lot of time coming up with an O(N²) solution. And I'd like to share with you guys.

Here we go! At first, it didn't take me too long to figure out that the order of folding by row or by column doesn't matter. (I hope you agree with me too.) If you can at first fold some rows then fold some columns to get one scheme, you can do it by folding some columns at first then some rows. So the order doesn't matter. So it leads us to focus on the position of the last scheme. As we all know, an valid scheme can be uniquely determined by the up-left corner and down-right corner. So I was wondering which units can be the up-left corner and down-right corner of the answer.

Leave all things behind, if we know which units can be the up-left corner and down-right corner of the answer, we can calculate the answer now. For each unit which can be the up-left corner of out last scheme, we just need to sum the count of the units which can be our down-right units for this up-left unit. It can be easily calculated in O(N²) dp right? (You want to know how many ones in a sub-rectangle, Let's dp!). So in the end, all comes to determining which units can the our up-left corner and down-right corner of the answer.

We know that up-left corner and down-right corner are similar. So We just need to determine which units can be up-left corner. It turns out we need to know can all rows above row[i] can be folded down to the row[i] and all columns on the left of col[i] can be fold down to the right col[i].(That was similar problem too!) And we can see there will be many comparisons of whole rows and columns. So I'd like to hash the whole row into one number.And all we need to do is find out:

Given a sequence a₁, a₂, ..., a_n, which numbers in this sequence be the leftmost one element after the fold.

(I spend a lot of time figuring out this one!), here's my way. Using one bool array to save this result. We know can[1] = 1, and when we go from left to right, we know if a_i can be the leftmost one, a_i - 1 must be folded into a_i, and there maybe some other numbers be folder to the right of a_i, or there's only a_i - 1 be folded into a_i. For the latter one, we know can[i-1] must be 1, (Other number should be folded to a_i - 1 first.) For the former one, we just need check a_i - 2 and a_i + 1, and same thing happens to a_i - 2, if can[i-2] = 1, and a_i - 2 = a_i + 1, we can fold all left numbers into a_i - 2 and fold two numbers a_i - 2, a_i - 1 into a_i, a_i + 1, so we may need check every number on the left of a_i, which takes O(N) time. And we got what we want!

So, to sum it up, we obtain a O(N²) solution. That's what I want to share with you guys. (Maybe the hash is the key-point to cut the time down to the O(N²)). However, I think it was a good solution. Any ideas and suggestions are welcome. :D

Oh, here's my code.