Skip to content

Weekly Contest 393

C - Kth Smallest Amount With Single Denomination Combination

ans = f(k)表示结果, 根据题意, f(k)具有单调性. 因此, 可用二分法.

  • 左边界, l = k
  • 右边界, r = min(coins) * k
  • 二分判断, 对于金额mid, 用cnt表示当前集合中的硬币按题意组成的不同金额(<mid)的数量, cnt >= k表示f[k] <= mid, cnt < k表示f[k] >= mid + 1
rust
/// runs in O(n*2^nlog(k * min(coins)))/O(1)
pub fn find_kth_smallest(coins: Vec<i32>, k: i32) -> i64 {
    let check = |m: i64| -> bool {
        let mut cnt = 0i64;
        for mask in (1..(1usize << coins.len())) {
            let mut lcm_res = 1i64;
            for j in (0..coins.len()) {
                if mask >> j & 1 == 1 {
                    lcm_res = lcm(lcm_res, coins[j] as i64);
                    if lcm_res > m {
                        break;
                    }
                }
            }

            cnt += m / lcm_res * if mask.count_ones() % 2 == 1 { 1 } else { -1 };
        }

        cnt >= k as i64
    };

    let mut l = k as i64;
    let mut r = *coins.iter().min().unwrap() as i64 * k as i64;

    while l < r {
        let mid = (l + r) >> 1;
        if check(mid) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }

    r
}

fn lcm<T>(mut a: T, mut b: T) -> T
where
    T: Eq
        + Ord
        + Default
        + Copy
        + std::ops::Rem<Output = T>
        + std::ops::Mul<Output = T>
        + std::ops::Div<Output = T>,
{
    a * b / gcd(a, b)
}

fn gcd<T>(mut a: T, mut b: T) -> T
where
    T: Eq + Default + Copy + std::ops::Rem<Output = T>,
{
    while b != T::default() {
        (a, b) = (b, a % b)
    }
    a
}

D - Minimum Sum of Values by Dividing Array

抽象描述: 把一个数组nums拆分成m个子数组, 使得每个子数组的AND和等于andValues[i]. 用vals[i]表示第i个子数组最后一个元素的值, 求某种拆分法使得sum{vals}最小.

定义dfs(i, j, and)表示, 把nums[0..i)分成j段, 最后一段已有元素的AND和为and.

rust
use std::collections::HashMap;
const INF: i32 = i32::MAX >> 2;

/// runs in O(nmlogU)/O(nmlogU), in which U = max(nums)
fn minimum_value_sum(nums: Vec<i32>, and_values: Vec<i32>) -> i32 {
    let mut memo = HashMap::new();
    let ans = dfs(0, 0, -1, &mut memo, &nums, &and_values);

    if ans < INF {
        ans
    } else {
        -1
    }
}

fn dfs(
    i: usize,
    j: usize,
    and: i32,
    memo: &mut HashMap<(usize, usize, i32), i32>,
    nums: &Vec<i32>,
    and_values: &Vec<i32>,
) -> i32 {
    let n = nums.len();
    let m = and_values.len();

    // prune
    if m - j > n - i {
        return INF;
    }

    // reach end
    if j == m {
        return if i == n { 0 } else { INF };
    }

    // memo optimization
    if memo.contains_key(&(i, j, and)) {
        return *memo.get(&(i, j, and)).unwrap();
    }

    let and = and & nums[i];

    // and is monotone descrasing
    if and < and_values[j] {
        return INF;
    }

    let mut res = dfs(i + 1, j, and, memo, nums, and_values); // not divide

    // divide
    if and == and_values[j] {
        res = res.min(dfs(i + 1, j + 1, -1, memo, nums, and_values) + nums[i]);
    }

    memo.insert((i, j, and), res);

    res
}

Last updated at: