Christian_D's blog

Stuck on problem B. Blurred Pictures of SWERC18
By Christian_D, history, 6 years ago, In English

The problem is here. My latest attempt is here.

I've implemented a version of this algorithm. It works for the smaller tests, however in the worst case (100000x100000 matrix, nothing blurry) my implementation still takes about 13 seconds.

I've optimized it as far as I'm able to. Is there something I'm missing? Or another approach entirely? I'm stuck.

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

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

Try a binary search on the length of the square. Complexity: Nlog(N).

→ Reply
  • »
    »
    6 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I'm not sure how I could use binary search to solve the problem. Can you elaborate?

    → Reply
    • »
      »
      »
      6 years ago, hide # ^ |
      ← Rev. 3  
      Vote: I like it 0 Vote: I do not like it

      The key is "all the non-blurred pixels are connected in such a way that any horizontal or vertical line drawn between two non-blurred pixels goes only through non-blurred pixels". That means that to check if a square is inside the non-blurred part you only need to check that the four vertexes are inside. Each row i contains a segment [a_i, b_i] of non-blurred pixels. To check whether a square of length k+1 fits on the non-blurred part, denote by m_i = max(a_i, a_{i+k}). You need to check that (i, m_i) (i+k, m_i), (i, m_i+k) (i+k, m_i+k) all belong to the non-blurred parts. This can be done in O(1) time. Thus in O(N) time, you check if a square of side length (k+1) fits.

      → Reply