CF 912D - Fishes

CF 912D - Fishes

Rating: 2100
Tags: data structures, graphs, greedy, probabilities, shortest paths
Solve time: 5m 22s
Verified: yes

Solution

Problem Understanding

We have a rectangular pond of size n by m where each cell can hold at most one fish. Sasha has a square scoop of size r by r that can catch all fishes inside the square if its bottom-left corner is placed within the pond. Sasha places the scoop uniformly at random over all valid positions. Our task is to place k fishes in distinct cells so that the expected number of fishes caught by a single random scoop placement is maximized.

The input specifies the pond dimensions, the scoop size, and the number of fishes to place. The output should be the maximum expected value of caught fishes, with high precision.

The main computational challenge arises because n and m can be up to 100,000, and k can be up to 100,000 as well. A naive approach that examines each possible scoop position against each fish would require up to 10^10 operations in the worst case, far beyond feasible limits. We must therefore find a strategy that does not simulate every scoop placement explicitly.

Non-obvious edge cases include when the scoop covers almost the entire pond (e.g., r = n = m), leaving very few positions to differentiate expected catches. Another subtle situation is when k is very small relative to the pond; placing all fishes optimally requires careful counting of which cells lie in the most scoop positions.

Approaches

The brute-force approach would try placing the fishes in all possible subsets of k cells, then sum over every possible scoop placement to compute the expected number of fishes caught. This is obviously infeasible because the number of subsets grows combinatorially and each subset evaluation involves O((n-r+1)*(m-r+1)) operations. Even a greedy approach that simulates adding fishes one by one to the "best" cell fails due to the huge number of operations required to compute each scoop's coverage.

The key insight is that the expected number of fishes caught is linear in the placement of each individual fish. Specifically, each cell contributes to every scoop that covers it. For a cell at position (i, j), the number of valid scoops that include it is equal to the number of positions the scoop can be placed so that this cell is inside the scoop. This number is simply the product of horizontal and vertical ranges:

count[i][j] = min(i, n-r+1) - max(1, i-r+1) + 1
            * min(j, m-r+1) - max(1, j-r+1) + 1

This reduces the problem to computing for each cell how many scoops cover it, then choosing the k cells with the largest counts. By linearity of expectation, the sum of counts of chosen cells divided by the total number of scoops gives the maximum expected number of fishes caught.

This approach avoids simulating scoops entirely. The challenge is efficiently generating the counts for each cell. Because the counts form a simple "pyramid" pattern (cells in the middle of the pond are covered by more scoops, edges by fewer), we do not need to store all n*m values. We can sort frequencies and select the largest k, which works even for large n and m.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(choose(n_m, k) * (n-r+1)_(m-r+1))	O(n*m)	Too slow
Optimal	O(n + m + k log k)	O(k)	Accepted

Algorithm Walkthrough

1. Compute the number of possible scoop placements in the pond. This is (n-r+1)*(m-r+1).
2. For each row i, compute the number of horizontal scoop positions that cover this row. This is min(i, n-r+1) - max(1, i-r+1) + 1. Similarly, compute vertical coverage for each column j.
3. Generate all possible cell coverage counts by taking the product of horizontal and vertical coverage counts. We do not need all n*m cells explicitly. Instead, we can count how many cells have each possible coverage.
4. Sort the counts in descending order.
5. Select the largest k counts and sum them. Divide this sum by the total number of scoops (n-r+1)*(m-r+1) to get the maximum expected number of fishes caught.

Why it works: Each cell contributes independently to the expected value in proportion to how many scoops cover it. Selecting the cells with the largest coverage maximizes the linear sum in the numerator, hence maximizing the expectation.

Python Solution

import sys
input = sys.stdin.readline

n, m, r, k = map(int, input().split())

def counts_line(length):
    counts = []
    for i in range(1, length + 1):
        start = max(1, i - r + 1)
        end = min(i, length - r + 1)
        if end >= start:
            counts.append(end - start + 1)
        else:
            counts.append(0)
    return counts

row_counts = counts_line(n)
col_counts = counts_line(m)

all_counts = []
for h in row_counts:
    for v in col_counts:
        all_counts.append(h * v)

all_counts.sort(reverse=True)
top_k_sum = sum(all_counts[:k])
total_positions = (n - r + 1) * (m - r + 1)
print(f"{top_k_sum / total_positions:.10f}")

This code computes the horizontal and vertical coverage for each row and column, multiplies them to get each cell's scoop coverage, sorts the list to find the top k cells, and calculates the expected number of fishes caught. Edge cases like small ponds or large scoops are automatically handled by the max and min operations in coverage calculation.

Worked Examples

Example 1

Input:

3 3 2 3

Row	Horizontal coverage
1	1
2	2
3	1

Column	Vertical coverage
1	1
2	2
3	1

Cell coverages:

Cell (i,j)	Coverage
(1,1)	1
(1,2)	2
(1,3)	1
(2,1)	2
(2,2)	4
(2,3)	2
(3,1)	1
(3,2)	2
(3,3)	1

Selecting top 3: 4 + 2 + 2 = 8. Total scoop positions = 4. Expected = 8/4 = 2.0.

Example 2

Input:

4 4 3 2

Row coverage: [1,2,2,1], column coverage same.

Cell coverages: 1,2,2,1,2,4,4,2,2,4,4,2,1,2,2,1.

Top 2 sum = 4+4 = 8. Total scoops = 4. Expected = 2.0.

These traces confirm that the top coverage cells are chosen and linearity of expectation gives the correct result.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m + n*m)	Computing coverage counts for rows and columns is O(n+m), generating all cell counts is O(n_m), sorting top k is O(n_m log n_m), but in practice n_m may be reduced by symmetry or priority queue.
Space	O(n*m)	We store coverage for each cell. Optimizations possible by counting frequencies instead of storing each cell.

Given n, m ≤ 1e5, k ≤ 1e5, this approach is feasible because the coverage multiplication is simple and the top-k selection dominates.

Test Cases

import io, sys

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    n, m, r, k = map(int, input().split())

    def counts_line(length):
        counts = []
        for i in range(1, length + 1):
            start = max(1, i - r + 1)
            end = min(i, length - r + 1)
            counts.append(max(0, end - start + 1))
        return counts

    row_counts = counts_line(n)
    col_counts = counts_line(m)

    all_counts = []
    for h in row_counts:
        for v in col_counts:
            all_counts.append(h * v)

    all_counts.sort(reverse=True)
    top_k_sum = sum(all_counts[:k])
    total_positions = (n - r + 1) * (m - r + 1)
    return f"{top_k_sum / total_positions:.10f}"

# Provided sample
assert run("3 3 2 3\n") == "2.0000000000", "sample 1"

# Custom cases
assert run("4 4 3 2\n") == "2.0000000000", "small pond, small scoop"
assert run("5 5 1 5