FIZZBUZZ2306 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Authors: naisheel, jalp1428, vasu_2344
Tester: tabr
Editorialist: iceknight1093

DIFFICULTY:

1750

PREREQUISITES:

Observation

PROBLEM:

There’s an N\times M grid with a single cell (x, y) initially infected.
You can choose some other cell (x', y') to vaccinate, then both the infection and vaccine spread across the grid horizontally and vertically in stages, with the infection spreading first.

If the vaccination cell is chosen optimally, what’s the maximum number of cells that can be vaccinated?

EXPLANATION:

Trying out a couple of cases on paper, you might notice that it always seems optimal to choose to place the vaccine right next to the infection.
Intuitively this seems reasonable too, since we curtail the infection as much as possible.

Indeed, this is optimal. Let’s prove it!

Proof

Suppose the vaccine is placed at cell (x', y'). Without loss of generality, let x'\geq x and y'\geq y.

Notice that the infection and vaccine both spread out in a ‘diamond’ shape with the sources as the center.
Consider the first instant of time when the two diamonds touch reach other at their borders.
Since the vaccine spreads only after the infection, note that the vaccine’s diamond cannot include both (x', y) and (x, y') — at most one of them can be included in it.

So suppose (x', y) isn’t included in the vaccine’s diamond.
Then, no cell in a column \leq y can ever be vaccinated, so the absolute best we can do is vaccinate all the cells in columns \gt y.
Note that we could’ve achieved this by placing the vaccine at (x, y+1) as well, which is adjacent to the initial infection cell.

Similarly, if (x ,y') isn’t included, no cell at row \leq x can be vaccinated ever; and the best we can do in this case is to vaccinate all rows \gt x, doable by placing the vaccine at (x+1, y).

So, placing the vaccine adjacent to the infection is always optimal.

Now that we know this, there are at most four choices to check: (x\pm 1, y) and (x, y\pm 1).
For each one, computing the number of vaccinated cells isn’t too hard:

  • (x+1, y) will vaccinate every row \gt x and nothing \leq x, for a total of (N-x)\cdot M cells.
  • (x-1, y) will vaccinate every row \lt x and nothing \geq x, for a total of (x-1)\cdot M cells.
  • (x, y+1) will vaccinate every column \gt y and nothing \leq y, for a total of (M-y)\cdot N cells.
  • (x, y-1) will vaccinate every column \lt y and nothing \geq y, for a total of (y-1)\cdot N cells.

The final answer is the maximum of these four numbers.

TIME COMPLEXITY

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, m = map(int, input().split())
    x, y = map(int, input().split())
    
    ans = n*max(m-y, y-1)
    ans = max(ans, m*max(n-x, x-1))
    print(ans)
2 Likes