cp_library/alg/dp/monotone_minima_fn.py

• View this file on GitHub
• Last update: 2025-03-30 20:17:47+09:00

Depends on

• cp_library/ds/elist_fn.py

Required by

• cp_library/math/conv/minplus_conv_fn.py

Verified with

• test/atcoder/abc/abc325_f_minplus_conv_inplace.test.py
• test/library-checker/convolution/min_plus_convolution_convex_arbitrary.test.py
• test/library-checker/convolution/min_plus_convolution_convex_convex.test.py

Code

import cp_library.alg.dp.__header__
from typing import Callable

def monotone_minima(N: int, M: int, func: Callable[[int,int,int],bool]):
    '''
    Finds row minima in a totally monotone N×M matrix using the SMAWK algorithm.
    The matrix is defined implicitly through the comparison function.
    
    A matrix is totally monotone if the minimum in row i occurs at column j,
    then the minimum in row i+1 must occur at column j' where j ≤ j'.
    
    Time: O(N log M), Space: O(N)
    
    Args:
        N: Number of rows
        M: Number of columns
        func(i,j,k): Returns True if element (i,j) < element (i,k)
    
    Returns:
        List of column indices containing the minimum value for each row
    
    Example:
        # Find minima where each element is (i-j)²
        min_indices = monotone_minima(5, 5, lambda i,j,k: (i-j)**2 < (i-k)**2)
    '''
    min_j, st = [0] * N, elist(N)
    st.append((0, N, 0, M))
    while st:
        li, ri, lj, rj = st.pop()
        if li == ri: continue
        mi, mj = li + ri >> 1, lj
        for j in range(lj + 1, rj):
            if func(mi, mj, j): mj = j
        min_j[mi] = mj
        st.append((li, mi, lj, mj+1))
        st.append((mi+1, ri, mj, rj))
    return min_j

from cp_library.ds.elist_fn import elist

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''
from typing import Callable

def monotone_minima(N: int, M: int, func: Callable[[int,int,int],bool]):
    '''
    Finds row minima in a totally monotone N×M matrix using the SMAWK algorithm.
    The matrix is defined implicitly through the comparison function.
    
    A matrix is totally monotone if the minimum in row i occurs at column j,
    then the minimum in row i+1 must occur at column j' where j ≤ j'.
    
    Time: O(N log M), Space: O(N)
    
    Args:
        N: Number of rows
        M: Number of columns
        func(i,j,k): Returns True if element (i,j) < element (i,k)
    
    Returns:
        List of column indices containing the minimum value for each row
    
    Example:
        # Find minima where each element is (i-j)²
        min_indices = monotone_minima(5, 5, lambda i,j,k: (i-j)**2 < (i-k)**2)
    '''
    min_j, st = [0] * N, elist(N)
    st.append((0, N, 0, M))
    while st:
        li, ri, lj, rj = st.pop()
        if li == ri: continue
        mi, mj = li + ri >> 1, lj
        for j in range(lj + 1, rj):
            if func(mi, mj, j): mj = j
        min_j[mi] = mj
        st.append((li, mi, lj, mj+1))
        st.append((mi+1, ri, mj, rj))
    return min_j



def elist(est_len: int) -> list: ...
try:
    from __pypy__ import newlist_hint
except:
    def newlist_hint(hint):
        return []
elist = newlist_hint
    

Back to top page