I was solving Problem B of Andrew Stankevich Contest 45.And I got endless TLE on test 2.It took me about an hour to debug but find nothing wrong. So my last hope is to change the cin/cout with scanf/printf in the IO, since this problem need to read and write about 10⁵ doubles. And it got AC. 11925037 11925015. Check it out! WTF is this?

I have read some post on CF discussing the difference about speed of cin/cout and scanf/printf. But how ever in general cases they talk about read integers. But it seems even if I add ios :: sync_with_stdio(0); in my code, cin/cout is much slower than scanf/printf. Why is this? Anyone knows? Thx in advance.

BTW, how can I share my code in gym so everybody can see it? (since gym has the rule U must got accepted first then U can read the others' code. However I remember once I saw a coder share his code in gym, but I don't need to got AC in advance.)

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.

I'd like to share an interesting thing with you all — I find a problem which has less testcases in practice room than in an official contest. This problem is Substitutes in Number (I don't know if there are other problems like this or not.)

Take a look at this submission : LINK.It has 39 testcases.

However in an official contest, this problems has 50 testcases. Take a look at any accepted submissions in the contest, you can find out. Here's a sample LINK.

So I am curious why there are 11 testcases missing.

Did admin know that?

Interesting, isn't it? :D

Since there's no related post about this, I'd like to post this to remind you all:

Topcoder SRM 634 will be taken place in 40 minutes.(Since now CST 08:20) LINK.

Don't miss the Round.

We can discuss the problems here after the round.