lyzqm   7년 전

대회문제는 처음인데요

구하고자하는것은 간단한데 시간적으로 해결하는게 너무나도 어렵습니다.

제방식으로는 답이 없는거 같아 질문드립니다.

저는 삶의질이 높은순서( 숫자가 작은수)대로 그 값이 중앙값인지 확인하였습니다.

중앙값을 확인하는 과정에서 memoization을 사용해서 불필요한 탐색을 줄였습니다.

ex)5 5 3 3

      1  2  3   10  11

      4  5  6   12  13

      7  8   9  14   15    

     16 17 18 19 20

      21 22 23 24 25      <1이 중앙값인지 확인한다고했을때 {{1,2,3},{4,5,6},{7,8,9}}를 확인하여 5라는 값을dp에 저장함>

중앙값 확인은 quick selection을 사용했습니다..

위의 값에 대한 memoization뿐만아니라 범위에 해당하는것도 했습니다.

시간단축을 더 줄일 방법이 있을까요? 아니면 제 방법이 잘못된걸까요? 

lyzqm   7년 전

Here is a O(N log N) solution. Observe that the program's output can be verified by some algorithm which answers the question "Does any rectangle have median ≤ X?" This query can be answered in O(n2) time. A rectangle has median ≤ X if and only if it contains more values ≤ X than otherwise. Assign all cells in the grid a 'value' according to a 'threshold' function: -1 if greater than X, 0 if equal to X, 1 if less than X. Using the well-known cumulative data structure for queries on rectangular sums, try all possible rectangle locations and return "yes" if the 'values' inside any sum to ≥ 0. We simply binary search values of X to find the minimum value for which the answer is "yes".

N.B. An O(N log N) algorithm suffices for 100% score.

O(N logN) 방법이 있긴하다는데 잘 이해가 안가네요 ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.