# Task 255 — ONNX Build Guide

## Overview

The Python solver at `task255_solver_265.py` passes 265/265 examples.
This document provides the ONNX implementation plan.

**KEY SIMPLIFICATION**: The largest empty rectangle ALWAYS touches at least one grid boundary (verified on all 265 examples). This eliminates the need for a general histogram-based algorithm.

## Input/Output Format

- Input: `[1, 10, 30, 30]` float32 (one-hot encoded, channel 0 = background)
- Output: `[1, 10, 30, 30]` float32 (same as input, with color 3 added at cross mask)

## ONNX Operations Needed

### Step 1: Compute fg_mask [1,1,30,30]

```
# Sum channels 1-9 to get foreground indicator
fg = Slice(input, [0,1,0,0], [1,10,30,30])  # channels 1-9
fg_sum = ReduceSum(fg, axes=[1])  # [1,1,30,30]
fg_mask = Greater(fg_sum, 0.5)  # [1,1,30,30] bool → float
```

### Step 2: Find Largest Empty Rect (boundary-anchored)

For each of 4 sides, find the largest rect anchored to that side.

**Example: Anchored to TOP (rect starts at row 0)**

```python
# For each depth k (1..30):
#   cum_fg[k] = ReduceMax(fg_mask[0:k, :], axis=row)  # [30] - 1 if any fg in top k rows
#   col_ok[k] = 1 - cum_fg[k]  # [30] - 1 if col is empty in top k rows
#   # Find longest consecutive run of 1s in col_ok[k]
#   # Run length × k = area for this depth
# Take max area across all k

# In ONNX:
# Precompute cumulative max from top: cum_max[r][c] = max(fg_mask[0:r+1, c])
# This is: MaxPool along row axis with kernel [r+1, 1] and valid padding
# Or: iterative max (cum_max[0] = fg_mask[0], cum_max[r] = max(cum_max[r-1], fg_mask[r]))
# With 30 fixed rows, can be done with 29 Max operations.

# For col_ok[k]: just 1 - cum_max[k-1]

# For consecutive run detection:
# diff = col_ok[i] - col_ok[i-1] (with padding)
# run_start positions: where diff = 1
# run_end positions: where diff = -1
# Longest run = max(end - start)
# This can be done with prefix sum tricks.
```

**ONNX-friendly approach for consecutive runs:**

```python
# For a binary vector v[30] (1=eligible, 0=not):
# prefix_sum[i] = sum(v[0:i+1])
# When v[i]=0: prefix_sum resets. So: cum_v[i] = v[i] * (cum_v[i-1] + 1)
# This gives run lengths at each position.
# max_run = ReduceMax(cum_v)

# In ONNX without loops: unroll 30 steps of cum_v computation
# Or: use prefix operations on [30×30] matrices
```

**Practical ONNX implementation for longest consecutive run:**

```python
# Method: for each possible start position s (0..29), compute how many consecutive 1s
# Mask[s][c] = product(v[s:c+1]) for c >= s, 0 otherwise
# This is a [30×30] lower-triangular matrix where each row s has the consecutive product.
# Use CumProd along axis=1, masked to lower triangular.
# sum_each_row = ReduceSum(Mask, axis=1)  # gives run_length_from_s
# max_run = ReduceMax(sum_each_row)

# Memory: [30×30] = 3600 floats = 14.4KB per computation
# Total for rect finding: 4 sides × 30 depths × 14.4KB = ~1.7MB
# This is too much! Need to optimize.
```

**Optimized approach:**

```python
# Instead of computing for ALL depths independently:
# Use the cumulative approach:
# empty_depth_from_top[c] = number of consecutive empty rows from row 0 in col c
# This is just: first_fg_row[c] (or 30 if no fg in col)
# For a rect of depth k anchored to top: only cols where empty_depth >= k are usable.
# Binary mask: (empty_depth >= k) for each k.
# Longest run in that mask × k = area.

# So the computation is:
# 1. Compute empty_depth_from_top[30] (one value per col)
# 2. For each k (1..30): mask = (empty_depth >= k)
# 3. Longest consecutive 1s in mask
# 4. Area = longest × k

# The 'empty_depth' is cheap: just a CumMax + comparison.
# The 'longest consecutive' for each k: use the [30×30] approach once
# with thresholding at different k values.

# Key insight: as k increases, the mask only LOSES 1s (never gains).
# So the longest run is non-increasing with k.
# Can binary search for optimal k, or just compute all 30 values.
```

### Step 3: Erosion

```
# erode_range(start, end, grid_max):
#   if start > 0: start += 1
#   if end < grid_max: end -= 1
# In ONNX: simple comparison + shift by 1
```

### Step 4: Extensions (Phase 1-4)

Each phase involves:
1. Per-row or per-col reduction to find fg boundaries
2. Comparison to determine eligibility
3. Contiguous run detection + erosion
4. Fill mask generation

All can be done with ReduceMax/ReduceMin along axes, comparisons, and mask operations.

## Memory Budget

Target: < 3MB intermediate → score > 10.0 pts

| Component | Estimated Memory |
|-----------|-----------------|
| fg_mask + cum_max | 30×30×4 = 3.6KB |
| Rect finding (4 sides) | ~200KB total |
| Extensions (4 phases) | ~300KB total |
| Output construction | 10×30×30×4 = 36KB |
| **Total** | **~600KB → score ~12.7** |

## Implementation Strategy

1. Start with rect-finding (hardest part)
2. Test with ground-truth rect values to validate extensions
3. Combine and validate end-to-end

## Critical Constraints

- Opset ≤ 18
- Banned: LOOP, SCAN, NONZERO, UNIQUE, SCRIPT, FUNCTION, COMPRESS, Sequence*
- File size: < 1.44MB
- All shapes must be statically known
- Input/output: exactly `[1,10,30,30]`