Uolevin kalansaalis

warning: function `get_price_of_optimal_cut_naive` is never used
   --> input/code.rs:136:4
    |
136 | fn get_price_of_optimal_cut_naive(price_map: PriceMap) -> i32 {
    |    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
    = note: `#[warn(dead_code)]` on by default

warning: function `get_triangle_price_naive` is never used
   --> input/code.rs:155:4
    |
155 | fn get_triangle_price_naive(price_map: &PriceMap, corner_x: usize, corner_y: usize, triangle_size: usize, flipped: bool) -> Option<i32> {
    |    ^^^^^^^^^^^^^^^^^^^^^^^^

warning: associated function `get_safe` is never used
  --> input/code.rs:29:12
   |
29 |     pub fn get_safe(&self, x: usize, y: usize) -> Option<i32> {
   |            ^^^^^^^^

warning: 3 warnings emitted

use std::io::stdin;
use std::cmp::min;

#[derive(Debug, Clone)]
struct PriceMap {
    width: usize,
    height: usize,
    map: Vec<Vec<i32>>,
}
impl PriceMap {
    pub fn new(width: usize, height: usize) -> Self {
        Self {
            width,
            height,
            map: vec![vec![0; width]; height]//array of rows to increase cache hit rate
        }
    }

    #[inline(always)]
    pub fn get(&self, x: usize, y: usize) -> i32 {
        self.map[y][x]
    }

    #[inline(always)]
    pub fn set(&mut self, x: usize, y: usize, price: i32) {
        self.map[y][x] = price;
    }

    pub fn get_safe(&self, x: usize, y: usize) -> Option<i32> {
        if x >= self.width || y >= self.height {
            return None;
        }

        Some(self.map[y][x])
    }

    // pub fn empty_map_with_same_size(&self) -> Self {
    //     Self::new(self.width, self.height)
    // }

    pub fn min_point_price(&self) -> i32 {
        *self.map
            .iter()
            .map(|row| row.iter())
            .flatten()
            .min()
            .unwrap()
    }

    pub fn flip(&mut self) {
        let max_y = self.height - 1;
        for y in 0..(self.height / 2) {
            for x in 0..self.width {
                let a = self.get(x, y);
                let b = self.get(x, max_y - y);
                self.set(x, y, b);
                self.set(x, max_y - y, a);
            }
        }
    }
}

//only checks downwards pointing triangles
fn get_price_of_optimal_downwards_cut(price_map: &PriceMap, top_left_sticking_out: bool) -> i32 {
    let mut triangle_price_map = price_map.clone();
    let mut line_price_map = price_map.clone();
    let mut best_price = price_map.min_point_price();

    let max_triangle_size = min(price_map.width, price_map.height);
    let parity_term = if top_left_sticking_out { 0 } else { 1 };

    for triangle_size in 2..=max_triangle_size {
        let max_x = price_map.width - triangle_size;
        let max_y = price_map.height - triangle_size;

        for y in 0..=max_y {
            let triangle_x_offset = (y + parity_term) % 2;

            for x in 0..=max_x {
                let point_price = price_map.get(x, y);
                let line_price = line_price_map.get(x + 1, y);
                let triangle_price = triangle_price_map.get(x + triangle_x_offset, y + 1);

                let new_line_price = line_price + point_price;
                let new_triangle_price = triangle_price + new_line_price;

                line_price_map.set(x, y, new_line_price);
                triangle_price_map.set(x, y, new_triangle_price);
                best_price = min(best_price, new_triangle_price);
            }
        }
    }

    best_price
}

fn get_price_of_optimal_cut(mut price_map: PriceMap) -> i32 {
    let mut optimal_cut_price = get_price_of_optimal_downwards_cut(&price_map, true);
    price_map.flip();
    optimal_cut_price = min(optimal_cut_price, get_price_of_optimal_downwards_cut(&price_map, price_map.height % 2 == 1));
    optimal_cut_price
}

fn main() {
    let mut input = stdin().lines();

    let line = input.next().unwrap().unwrap();
    let mut split = line.split_whitespace();
    let height: usize = split.next().unwrap().parse().unwrap();
    let width: usize = split.next().unwrap().parse().unwrap();
    let amount_of_fish: usize = split.next().unwrap().parse().unwrap();

    let mut price_map = PriceMap::new(width, height);
    let mut total_price: i32 = 0;
    for line_result in input.take(amount_of_fish) {
        let line = line_result.unwrap();
        let mut split = line.split_whitespace();
        let y: usize = split.next().unwrap().parse::<usize>().unwrap() - 1;
        let x: usize = split.next().unwrap().parse::<usize>().unwrap() - 1;
        let fish_type = split.next().unwrap();

        let price: i32 = match fish_type {
            "H" => 1,
            "K" => -10,
            _ => panic!("unknown fish type")
        };

        price_map.set(x, y, price);
        total_price += price;
    }

    let best_price = total_price - get_price_of_optimal_cut(price_map);
    println!("{best_price}");
}

fn get_price_of_optimal_cut_naive(price_map: PriceMap) -> i32 {
    let mut best_price = i32::MAX;

    for flipped in [false, true] {
        for triangle_size in 1..=min(price_map.width, price_map.height) {
            for corner_x in 0..price_map.width {
                for corner_y in 0..price_map.height {
                    match get_triangle_price_naive(&price_map, corner_x, corner_y, triangle_size, flipped) {
                        Some(price) => best_price = min(best_price, price),
                        None => {}
                    }
                }
            }
        }
    }

    best_price
}

fn get_triangle_price_naive(price_map: &PriceMap, corner_x: usize, corner_y: usize, triangle_size: usize, flipped: bool) -> Option<i32> {
    let mut total_price = 0;
    for internal_y in 0..triangle_size {
        for internal_x in 0..=(triangle_size-1 - internal_y) {
            let y = if flipped { corner_y.wrapping_sub(internal_y) } else { corner_y + internal_y };
            let x_offset = ((corner_y + internal_y) / 2) - (corner_y / 2);
            let x = corner_x + x_offset + internal_x;

            match price_map.get_safe(x, y) {
                Some(price) => total_price += price,
                None => return None
            };
        }
    }

    Some(total_price)
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::prelude::*;
    use rand::seq::SliceRandom;       

    #[test]
    fn naive_and_efficient_agree() {
        const SEED: u64 = 13258927485903104053;
        let mut rng = StdRng::seed_from_u64(SEED);

        for i in 0..1000 {
            let price_map = get_random_price_map(&mut rng);

            let expected = get_price_of_optimal_cut_naive(price_map.clone());
            let actual = get_price_of_optimal_cut(price_map.clone());
            assert_eq!(expected, actual, "Subtest {i} failed.");
        }
    }

    fn get_random_price_map(rng: &mut StdRng) -> PriceMap {
        let width = rng.gen_range(1..=10);
        let height = rng.gen_range(1..=10);

        let mut price_map = PriceMap::new(width, height);
        for x in 0..width {
            for y in 0..height {
                let price: i32 = *[-10, 0, 1].choose(rng).unwrap();
                price_map.set(x, y, price);
            }
        }

        price_map
    }
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 1, 2

Verdict: ACCEPTED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 1, 2

Verdict: ACCEPTED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 1, 2

Verdict: ACCEPTED

Test 12

Group: 1, 2

Verdict: ACCEPTED

Test 13

Group: 1, 2

Verdict: ACCEPTED

Test 14

Group: 1, 2

Verdict: ACCEPTED

Test 15

Group: 1, 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: ACCEPTED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: ACCEPTED

Test 22

Group: 2

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: ACCEPTED

Test 24

Group: 2

Verdict: ACCEPTED