meiniak's blog

By meiniak, history, 4 years ago, In English

Problem Link . I tried to solve this problem but couldn't solve it. Try to read editorial using google translate help me nothing.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The solution here hinges on the fact that we don't care about most of the 3x3 subrectangles.

Let's pick any uncolored cell. You can see that any 3x3 subrectangle that would contain that cell would be fully contained within the 5x5 subrectangle in which that cell is the middle. This means that if no cell in the 5x5 subrectangle where the target cell is the middle is colored, then we don't care about that point.

At most $$$9$$$ subrectangles will go through a single point, so there are at most $$$9N$$$ subrectangles we have to worry about. For each point, generate the subrectangles that contain that point (you can iterate through the position in the subrectangle that our target point is in, also be careful about edges). Also, remove duplicates in some way. This process is probably $$$O(nlogn)$$$ because of sorting or something.

Now, for each subrectangle, we will count how many colored cells are in it. We can do this by keeping each point in some ordered list (perhaps a C++ set) and checking each of the 9 points in each rectangle. This is our answer.

The total number of rectangles is $$$(H - 2) * (W - 2)$$$, and if we haven't looked at a rectangle, it has 0 points inside it, so you can just subtract the number of rectangles we've looked at and add that to $$$count(0)$$$.

I got bored and wanted to prove that the constant wouldn't be too bad, so here's a submission with time = 396 ms.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanx for the explanation, I implemented the solution but my exe time is 1144ms. Please explain why ? My solution

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I would imagine constantly inserting into the set used instead of using a vector and removing duplicates would perform significantly slower because set is slow.

      Also, the use of the check function ends up looking at more points than the faster solution, because if a square would be out of bounds, the faster solution wouldn't even look at the square, but you would query the set for some of the points before deciding that it's an invalid square.