shejibri's blog

[help!]IZHO 2017 Bomb
By shejibri, 4 years ago, In English

How to solve IZHO 2017 Bomb? Please help! Problem link: https://oj.uz/problem/view/IZhO17_bomb

  • Vote: I like it
  • +20
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 4   Vote: I like it -13 Vote: I do not like it

Nvm this, it's wrong!

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    Thanks! I wrote what you said but is gets only 24 score. Code: https://oj.uz/submission/171777 I can not catch any bug in this code.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Your solution is wrong. Here's a counterexample

    6 6
000111
000111
001111
111100
111000
111000

    We can't fill it with 3x3 bombs.

    P.S. I don't know the full solution, but enoone and DavitMarg do. Maybe they want some contrtibution.

    → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Obviously the width is bounded by the smallest horizontal strip of 1s, let that width be w.

Let's precalculate top[i][j] = greatest x<i such that (x, j) is 0, precalculate bottom[i][j] similarly.

Create an array h of size w, all initialized to the smallest vertical strip of 1s.

For each maximal horizontal strip of 1s from (i, l) to (i, r) do the following:

For each prefix of that strip from (i, l) to (i, x), min h[x-l+1] with (y = min(bottom[i][l..x])-max(top[i][l..x])-1). It basically means that if we put a rectangle at [l, x], we can get a height of at most y.

Do a similar thing for all suffixes of that strip.

I claim that a rectangle of max(h[i]*i) is always possible, and you can see that this is true as the codes that do this get AC.

→ Reply