Блог пользователя zeref_dragoneel

number of rectangular submatrix with all 1s
Автор zeref_dragoneel, история, 8 лет назад, По-английски

How to count the number of rectanglular submatrix with all 1s in a binary square matrix of size N in O(N^2)?

i have a solution for o(N^3)

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Nice question! Like you, i am only solving the O(N^3) algorithm with two pointer technique, and i guess O(N^2 Log N) with divide and conquer maybe..

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Test your idea with this problem from COCI. My O(N^2 Log N) idea get TLE.

→ Ответить