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

Yet Another Constructive Problem～
Автор Alex2025_qwq, история, 2 часа назад, По-английски

Hi everyone! Here’s a fun problem: Construct an n*m binary matrix such that all the 1-cells form a single 4-connected component, while maximizing the number of 4-connected components formed by the 0-cells. Two cells are considered adjacent if they share an edge. Is there an O(nm) construction with a provably tight upper bound on the number of zero-components? What is the tightest upper bound you can establish, and what are the best achievable time and space complexities for the construction?

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

»
117 минут назад, скрыть # |
← Rev. 4  
Проголосовать: нравится 0 Проголосовать: не нравится

note: remember to handle n=1 or m=1

(btw im editing so much lol)

my construction (0: . and 1: #):

.#.#
####
.#.#
####

a[i][j] = 1 if (i % 2 or j % 2) else 0

its $$$\lceil n/2 \rceil \cdot \lceil m/2 \rceil$$$ 0 components

time and space is $$$O(nm)$$$

→ Ответить
  • »
    »
    103 минуты назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится 
    . # # #
# . # .
# # # #
. # . #
    → Ответить
    • »
      »
      »
      32 минуты назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится 
      # # # # #
# . # . #
# # # # #
# . # . #
# # # # #
      → Ответить