cp_library/math/conv/minplus_conv_fn.py

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

Depends on

• cp_library/alg/dp/monotone_minima_fn.py
• cp_library/ds/elist_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.__header__
from cp_library.alg.dp.monotone_minima_fn import monotone_minima
import cp_library.math.__header__
import cp_library.math.conv.__header__

def minplus_conv_arb_cnvx(arb: list[int], cnvx: list[int]) -> list[int]:
    N, M = len(cnvx), len(arb)
    def cmp(i, j, k):
        return i >= k and (i-j >= N or (cnvx[i-j] + arb[j] >= cnvx[i-k] + arb[k]))
    cols = monotone_minima(N+M-1, M, cmp)
    return [arb[j] + cnvx[i-j] for i, j in enumerate(cols)]

def minplus_conv_cnvx(A: list[int], B: list[int]) -> list[int]:
    if not (N := len(A)) | (M := len(B)): return []
    C = [0] * (K:=N+M-1)
    C[0], I, J = A[i := 0] + B[j := 0], N-1, M-1
    for k in range(1, K):
        if j == J or (i != I and A[i+1] + B[j] < A[i] + B[j+1]): i += 1
        else: j += 1
        C[k] = A[i] + B[j]
    return C

def minplus_iconv(A: list[int], B: list[int]):
    N, M = len(A), len(B)
    for i in range(N-1,-1,-1):
        A[i] = min(B[j] + A[i-j] for j in range(min(M,i+1)))   

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             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
    

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
    x₀ ────────●─●────────●───●────────●───────●────────► X₀
                ╳          ╲ ╱          ╲     ╱          
    x₄ ────────●─●────────●─╳─●────────●─╲───╱─●────────► X₁
                           ╳ ╳          ╲ ╲ ╱ ╱          
    x₂ ────────●─●────────●─╳─●────────●─╲─╳─╱─●────────► X₂
                ╳          ╱ ╲          ╲ ╳ ╳ ╱          
    x₆ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₃
                                        ╳ ╳ ╳ ╳         
    x₁ ────────●─●────────●───●────────●─╳─╳─╳─●────────► X₄
                ╳          ╲ ╱          ╱ ╳ ╳ ╲          
    x₅ ────────●─●────────●─╳─●────────●─╱─╳─╲─●────────► X₅
                           ╳ ╳          ╱ ╱ ╲ ╲          
    x₃ ────────●─●────────●─╳─●────────●─╱───╲─●────────► X₆
                ╳          ╱ ╲          ╱     ╲          
    x₇ ────────●─●────────●───●────────●───────●────────► X₇
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
                      Math - Convolution                     
'''

def minplus_conv_arb_cnvx(arb: list[int], cnvx: list[int]) -> list[int]:
    N, M = len(cnvx), len(arb)
    def cmp(i, j, k):
        return i >= k and (i-j >= N or (cnvx[i-j] + arb[j] >= cnvx[i-k] + arb[k]))
    cols = monotone_minima(N+M-1, M, cmp)
    return [arb[j] + cnvx[i-j] for i, j in enumerate(cols)]

def minplus_conv_cnvx(A: list[int], B: list[int]) -> list[int]:
    if not (N := len(A)) | (M := len(B)): return []
    C = [0] * (K:=N+M-1)
    C[0], I, J = A[i := 0] + B[j := 0], N-1, M-1
    for k in range(1, K):
        if j == J or (i != I and A[i+1] + B[j] < A[i] + B[j+1]): i += 1
        else: j += 1
        C[k] = A[i] + B[j]
    return C

def minplus_iconv(A: list[int], B: list[int]):
    N, M = len(A), len(B)
    for i in range(N-1,-1,-1):
        A[i] = min(B[j] + A[i-j] for j in range(min(M,i+1)))   

Back to top page