### HandIeNeeded's blog

By HandIeNeeded, history, 4 years ago, , 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 105 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.) By HandIeNeeded, 5 years ago, , 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(N2) 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(N2) 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 a1, a2, ..., an, 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, and when we go from left to right, we know if ai can be the leftmost one, ai - 1 must be folded into ai, and there maybe some other numbers be folder to the right of ai, or there's only ai - 1 be folded into ai. For the latter one, we know can[i-1] must be 1, (Other number should be folded to ai - 1 first.) For the former one, we just need check ai - 2 and ai + 1, and same thing happens to ai - 2, if can[i-2] = 1, and ai - 2 = ai + 1, we can fold all left numbers into ai - 2 and fold two numbers ai - 2, ai - 1 into ai, ai + 1, so we may need check every number on the left of ai, which takes O(N) time. And we got what we want!

So, to sum it up, we obtain a O(N2) 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(N2)). However, I think it was a good solution. Any ideas and suggestions are welcome. :D

Oh, here's my code. By HandIeNeeded, 5 years ago, , 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.

Interesting, isn't it? :D bug,
By HandIeNeeded, 5 years ago, ,  