CF 105292A - Akari

Rating: -
Tags: -
Solve time: 58s
Verified: yes

Solution

Problem Understanding

We are given a rectangular Akari board consisting of empty cells . and walls #.

A light bulb can be placed only on an empty cell. Its light travels horizontally and vertically until it reaches a wall or the edge of the board. Two bulbs are not allowed to illuminate each other, which means that there cannot be two bulbs in the same uninterrupted row segment or the same uninterrupted column segment.

The task is not to optimize anything. We only need to output any valid placement of bulbs and mark those cells with L.

The grid can be as large as 2000 × 2000, which means there may be up to four million cells. Any algorithm that repeatedly scans rows and columns from each bulb position would be far too slow. We need something essentially linear in the number of cells.

A common source of mistakes is thinking about individual cells instead of visibility segments.

Consider:

...

A single bulb in the leftmost cell illuminates the entire row. Placing more bulbs in that row would immediately violate the rules because the bulbs would see each other.

Another easy mistake is forgetting that walls split visibility.

.#.

The left and right cells belong to different row segments. Bulbs may exist on both sides because the wall blocks the light.

A third subtle case is an isolated cell:

#
.
#

The cell forms both a row segment and a column segment of length one. A valid solution may place a bulb there, and any segment-based representation must handle such singleton segments correctly.

Approaches

The brute-force viewpoint is to repeatedly choose bulb positions and then verify whether every cell is illuminated and whether any pair of bulbs can see each other. Even checking a single candidate solution can require scanning long stretches of rows and columns. With up to four million cells, exploring placements directly is completely infeasible.

The key observation is that visibility is determined only by row segments and column segments.

A row segment is a maximal consecutive block of . cells within a row. Walls break segments. A column segment is defined similarly.

Every empty cell belongs to exactly one row segment and exactly one column segment.

Now think of a bipartite graph.

One side contains all row segments.

The other side contains all column segments.

For every empty cell, add an edge between its row segment and its column segment.

Placing a bulb in a cell means selecting the corresponding edge.

The rule that no two bulbs illuminate each other becomes very simple: a row segment can contain at most one bulb and a column segment can contain at most one bulb. In graph terms, the chosen edges must form a matching.

What about illumination?

If a row segment contains a bulb, then every cell in that row segment is illuminated. The same is true for a column segment.

A cell is illuminated if at least one of its two segment endpoints is incident to a chosen matching edge.

This suggests a classic graph fact: the endpoints of any maximal matching form a vertex cover. Every edge has at least one endpoint matched.

So if we construct any maximal matching in the segment graph, every cell's edge has at least one matched endpoint. That means every cell is illuminated by either its row segment's bulb or its column segment's bulb.

Even better, a greedy matching is already maximal. We can scan all cells and place a bulb whenever both corresponding segments are still unused.

The graph is enormous if built explicitly, but the grid structure lets us process edges directly while scanning the board.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	Exponential / impractical	Large	Too slow
Greedy Maximal Matching on Segment Graph	O(NM)	O(NM)	Accepted

Algorithm Walkthrough

Compute the row-segment id of every empty cell.

Scan each row from left to right. Whenever a new block of consecutive . cells begins, assign it a new row-segment id and give that id to every cell in the block. 2. Compute the column-segment id of every empty cell.

Scan each column from top to bottom. Whenever a new block of consecutive . cells begins, assign it a new column-segment id and give that id to every cell in the block. 3. Maintain two boolean arrays.

One array records whether a row segment is already matched.

The other records whether a column segment is already matched. 4. Scan all cells of the grid.

For each empty cell, look at its row-segment id and column-segment id.

If neither segment has been matched yet, place a bulb in this cell and mark both segments as matched.

This is exactly the standard greedy construction of a maximal matching. 5. Output the board.

Every selected cell becomes L. Walls remain #. All other empty cells remain ..

Why it works

The chosen bulb positions correspond to edges of a matching because each row segment and each column segment is used at most once.

The greedy process produces a maximal matching. After it finishes, no edge exists whose two endpoints are both unmatched, otherwise that edge could be added.

Take any empty cell. Its corresponding graph edge connects its row segment and column segment.

Since the matching is maximal, at least one endpoint of that edge is matched. That matched endpoint contains a bulb somewhere in the same segment.

If the matched endpoint is the row segment, the bulb illuminates the entire row segment containing the cell.

If the matched endpoint is the column segment, the bulb illuminates the entire column segment containing the cell.

So every empty cell is illuminated.

Because the selected edges form a matching, no row segment contains two bulbs and no column segment contains two bulbs. Hence no two bulbs can illuminate each other.

The construction is always valid.

Python Solution

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
grid = [list(input().strip()) for _ in range(n)]

row_id = [[-1] * m for _ in range(n)]
row_cnt = 0

for i in range(n):
    j = 0
    while j < m:
        if grid[i][j] == '#':
            j += 1
            continue

        rid = row_cnt
        row_cnt += 1

        k = j
        while k < m and grid[i][k] == '.':
            row_id[i][k] = rid
            k += 1

        j = k

col_id = [[-1] * m for _ in range(n)]
col_cnt = 0

for j in range(m):
    i = 0
    while i < n:
        if grid[i][j] == '#':
            i += 1
            continue

        cid = col_cnt
        col_cnt += 1

        k = i
        while k < n and grid[k][j] == '.':
            col_id[k][j] = cid
            k += 1

        i = k

row_used = [False] * row_cnt
col_used = [False] * col_cnt

ans = [row[:] for row in grid]

for i in range(n):
    for j in range(m):
        if grid[i][j] != '.':
            continue

        r = row_id[i][j]
        c = col_id[i][j]

        if not row_used[r] and not col_used[c]:
            row_used[r] = True
            col_used[c] = True
            ans[i][j] = 'L'

for row in ans:
    print("".join(row))

The first phase labels row segments. Every maximal horizontal block of empty cells receives one identifier.

The second phase does the same for column segments.

After that, each empty cell already knows the two graph vertices corresponding to its edge.

The greedy matching phase is extremely small. If both segment endpoints are currently free, we match them and place a bulb.

The output grid is initialized as a copy of the original board. Only cells selected by the matching are changed to L.

No special handling is needed for isolated cells, segments of length one, or boards containing many walls. The segment construction naturally handles all of them.

Worked Examples

Example 1

Input:

3 3
...
.#.
...

Row segments:

Cell	Row Segment
Top row	R0
Middle left	R1
Middle right	R2
Bottom row	R3

Column segments:

Cell	Column Segment
Left upper	C0
Left lower	C1
Middle top	C2
Middle bottom	C3
Right upper	C4
Right lower	C5

Greedy scan:

Cell	Row Free	Col Free	Action
(0,0)	Yes	Yes	Place bulb
(0,1)	No	Yes	Skip
(0,2)	No	Yes	Skip
(1,0)	Yes	No	Skip
(1,2)	Yes	No	Skip
(2,0)	Yes	Yes	Place bulb

Output:

L..
.#.
L..

Every empty cell shares either a row segment or a column segment with one of the bulbs.

Example 2

Input:

4 5
..#..
.###.
..#..
.#.#.

Greedy matching may choose:

Cell	Action
(0,0)	Place bulb
(0,3)	Place bulb
(1,4)	Place bulb
(2,1)	Place bulb
(3,2)	Place bulb

One valid output is:

L.#L.
.###L
.L#..
.#L#.

This demonstrates that many different valid answers can exist.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(NM)	Each cell is processed a constant number of times
Space	O(NM)	Segment ids for every cell

With N, M ≤ 2000, the grid contains at most four million cells. An O(NM) solution is exactly the right scale for this input size and comfortably fits within the limits.

Test Cases

# helper: run solution on input string, return output string
# These tests validate structure rather than a unique output,
# because many different valid solutions may exist.

import sys
import io

def run(inp: str) -> str:
    # paste solution here when testing locally
    pass

# minimum board
# 1x1 empty cell must contain a bulb somewhere
# assert validity of produced board

# single row
# input:
# 1 2
# ..
# one bulb is sufficient

# wall-separated cells
# input:
# 1 3
# .#.
# both sides may independently contain bulbs

# larger mixed case
# input:
# 4 5
# ..#..
# .###.
# ..#..
# .#.#.

Test input	Expected output	What it validates
`1 1 / .`	One bulb	Smallest possible board
`1 2 / ..`	Valid placement	Long row segment
`1 3 / .#.`	Valid placement	Wall splits visibility
Mixed 4×5 sample	Valid placement	Multiple disconnected segments

Edge Cases

Consider:

1 2
..

There is one row segment and two column segments.

The greedy matching places a bulb in the first cell. The row segment becomes matched. The second cell's edge cannot be added because the row segment is already used.

The second cell is still illuminated because it belongs to the same row segment as the bulb.

Now consider:

1 3
.#.

The two empty cells belong to different row segments and different column segments.

The greedy scan may place a bulb in both cells. This is legal because the wall blocks visibility between them.

Finally, consider:

3 1
#
.
#

The lone empty cell forms a row segment and a column segment by itself.

Both segment endpoints are initially free, so the algorithm places a bulb there. The cell illuminates itself, and the solution is valid.