1228B — Filling the Grid — Editorial (Unofficial :: Explained)

Revision en1, by ismail, 2019-09-30 15:19:22

Problem Details:

Contest : Codeforces Round 589 (Div. 2)

Problem : 1228B - Filling the Grid

Solution : Submission

Solution Explanation:

Create a matrix a[r+2][c+2] to hold cell information (2 extra index for 1 based indexing + no need to check overflow)

Cell information:

-1 = Free (can be White or Black)

0 = Reserved (Must be empty and immutable)

1 = Occupied (Black cell)

[ To make r and c valid, reserved cell never be changed ]

Logic:

  1. Initialize all cell as free (-1). memset(a, -1, sizeof(a[0][0]) * (r + 2) * (c + 2));

  2. Take input each row (1 to h) value as "d" and do the following:

    • If d==0, then 1st cell (for 1 base indexing, cell d+1=1 is the 1st cell) must be reserved (0) otherwise cell d+1 reserved.-> cell d+1 reserved because if d+1 cell changed to black then r will be invalid.
    • if d>0 then make all (1 to d) cell occupied (1)
  3. Take input each col (1 to w) value as "d" and do the following:(same as logic 2, just extra need you to check reserved cell is occupied or not before new cell reserved or occupied)

    • Check required reserved cell is occupied or not. if occupied then it's impossible to make a grid to satisfy such r, c values, so return 0 with "0" output.
    • make cell d+1 reserved.
    • if d>0 then make all (1 to d) cell occupied (1) BUT before made occupied check it previously reserved or not. If reserved then return 0 with "0" output.
  4. Count how many free (-1) cell do you have for combinations. If free cell is zero then ans = 1(initialized) otherwise ans = 2^free_cell.

.

Solution / Code:

Happy coding

Tags #editorial, #589 (div 2), #1228b

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English ismail 2019-09-30 15:44:24 90
en2 English ismail 2019-09-30 15:24:56 20 In my code, h and w replaced by r and c respectively.
en1 English ismail 2019-09-30 15:19:22 3051 Initial revision (published)