Power Cell Bank

ᨳଓ A big thank you to the friend who shared this problem with FastPrep! ᢉ𐭩

Implement the PowerCellBank class.

The bank contains num_racks racks arranged from front to back. Rack 1 is the front rack, and rack i has capacity 2^i.

A cell is installed with a load timestamp and a rated duration. As time passes, each cell automatically moves through three temporal states: charged, depleted, and spent.

Class Interface

class PowerCellBank:
    def __init__(self, num_racks: int) -> None:
        ...

    def load_cell(
        self,
        timestamp: float,
        cell_id: str,
        rated_duration: float,
    ) -> bool:
        ...

    def discharge(
        self,
        timestamp: float,
        max_dispatch: int,
    ) -> list[str]:
        ...

Constructor

__init__(num_racks: int) -> None

Initializes an empty bank containing num_racks racks. The racks are numbered from 1 to num_racks. Rack 1 is the front rack, and rack i has capacity 2^i.

For example, with three racks, the capacities are:

• rack 1: 2
• rack 2: 4
• rack 3: 8

Loading A Cell

load_cell(
    timestamp: float,
    cell_id: str,
    rated_duration: float,
) -> bool

Installs one freshly charged cell into the bank. The cell is placed in the frontmost rack that still has free capacity.

Return:

• True if the cell was installed successfully.
• False if every rack is full.

A spent cell is treated as absent, so it does not occupy rack capacity, its slot may be reused, and its cell_id may be reused by a later load_cell call.

You may assume:

• rated_duration > 0.
• No non-spent cell currently in the bank has the same cell_id as the new cell.

A dispatched cell is also removed from the bank, so its ID may later be reused.

Temporal States

For a cell loaded at load_timestamp, define t = timestamp - load_timestamp.

The cell's state at the current operation timestamp is:

State changes happen automatically as time passes. No explicit update is required at the transition moment.

Spent cells are treated as absent everywhere:

• They are not dispatched.
• They do not occupy rack capacity.
• They are excluded from all counts.
• They are excluded from charge equalisation.
• They are excluded from bus-shift selection.
• They do not appear in output.

Throughout the specification, cell means a non-spent cell unless stated otherwise.

Charge Ordering

At a call's timestamp, define a cell's charge window as load_timestamp + rated_duration - timestamp.

This value is positive for charged cells and zero or negative for depleted cells. Cells are ordered by charge window.

• The most-charged cell is the cell with the largest charge window.
• The most-depleted cell is the cell with the smallest charge window.

When charge windows tie, choose the cell with the lexicographically smallest cell_id using ordinary ASCII comparison. For example, "a" < "b". The same tie-breaking rule applies to both most-charged and most-depleted selection.

Discharging Cells

discharge(
    timestamp: float,
    max_dispatch: int,
) -> list[str]

The operation has two stages:

1. Run one charge-equalisation cycle.
2. Dispatch up to max_dispatch cells using repeated bus-shift pulls.

The returned list contains entries in dispatch order. Each entry has the form cell_id:state, where state is "charged" if the cell is still within its rated window at the call's timestamp and "depleted" otherwise.

For example: ["c2:charged", "c7:depleted"].

Dispatching stops early when the bank is empty. You may assume 1 <= max_dispatch < 2^10.

Charge Equalisation

Charge equalisation runs once at the start of every discharge call.

A rack is below-sag when it contains at least one cell and strictly fewer than 50% of its cells are charged. Equivalently, 2 * charged_cell_count < total_cell_count.

The equalisation cycle visits racks from front to back. For each rack k that has a rear neighbour k + 1, while both of the following conditions hold:

• rack k is below-sag;
• rack k + 1 contains at least one charged cell;

perform one balance swap:

1. Choose rack k's most-depleted cell.
2. Choose rack k + 1's most-charged charged cell.
3. Swap the two cells.

Continue swapping until rack k is no longer below-sag or rack k + 1 has no charged cells remaining. Then move on to rack k + 1.

The final rack has no rear neighbour, so no equalisation begins from it.

Bus Shift

Each bus-shift pull dispatches exactly one cell through two actions.

1. Dispatch

Find the active rack, defined as the frontmost rack containing at least one cell. Dispatch the most-charged cell from that rack. When charge windows tie, dispatch the cell with the lexicographically smallest cell_id.

If no active rack exists, the bank is empty and the discharge call stops.

2. Inward Shift

The dispatched cell frees one slot in the active rack. Fill that slot by moving the most-charged cell from the next rack back into the active rack.

That movement frees one slot in the next rack, so fill it by moving the most-charged cell from the rack behind it. Continue propagating the vacancy toward the back.

The shift stops when the next rack is empty or there is no further rack.

A cell moved into a rack during the inward shift is immediately eligible for dispatch during the next pull.

FastPrep Runner Adapter

The executable FastPrep interface represents calls to the class as one operation stream without changing any bank behavior:

powerCellBank(int numRacks, String[][] operations) -> String[][]

Process operations in order and return one row for every operation:

• ["load_cell", timestamp, cell_id, rated_duration]: call load_cell and append ["true"] or ["false"].
• ["discharge", timestamp, max_dispatch]: call discharge and append its returned list. This row may be empty.

All values inside an operation row are strings. Parse timestamps and rated durations as floating-point numbers and max_dispatch as an integer.