enumeration/
lib.rs

1//! # Enumeration
2
3/// 2749m Minimum Operations to Make Integer Zero
4struct Sol2749 {}
5
6impl Sol2749 {
7    pub fn make_the_integer_zero(num1: i32, num2: i32) -> i32 {
8        let mut x: i64 = 1;
9        loop {
10            let target = num1 as i64 - x * num2 as i64;
11
12            if target < x {
13                return -1;
14            }
15            if x >= target.count_ones() as i64 {
16                return x as _;
17            }
18
19            x += 1;
20        }
21    }
22}
23
24/// 3025m Find the Number of Ways to Place People I
25struct Sol3025 {}
26
27impl Sol3025 {
28    pub fn number_of_pairs(points: Vec<Vec<i32>>) -> i32 {
29        (0..points.len())
30            .flat_map(|i| (0..points.len()).map(move |j| (i, j)))
31            .filter(|(i, j)| i != j)
32            .filter(|&(i, j)| points[i][0] <= points[j][0] && points[i][1] >= points[j][1])
33            .fold(0, |pairs, (i, j)| {
34                if points
35                    .iter()
36                    .enumerate()
37                    .filter(|&(k, _)| k != i && k != j)
38                    .map(|(_, point)| (point[0], point[1]))
39                    .inspect(|p| println!("-> {i} {j} {p:?}"))
40                    .any(|(x, y)| {
41                        (x >= points[i][0] && x <= points[j][0])
42                            && (y <= points[i][1] && y >= points[j][1])
43                    })
44                {
45                    pairs
46                } else {
47                    pairs + 1
48                }
49            })
50    }
51}
52
53/// 3027h Find the Number of Ways to Place People II
54struct Sol3027 {}
55
56impl Sol3027 {
57    pub fn number_of_pairs(mut points: Vec<Vec<i32>>) -> i32 {
58        points.sort_by(|p, q| p[0].cmp(&q[0]).then(q[1].cmp(&p[1])));
59        println!("-> {points:?}");
60
61        points
62            .iter()
63            .enumerate()
64            .take(points.len() - 1)
65            .fold(0, |pairs, (i, p)| {
66                let mut x_min = p[0] - 1;
67                let mut y_min = i32::MIN;
68
69                pairs
70                    + points.iter().skip(i + 1).fold(0, |pairs, q| {
71                        if q[0] > x_min && q[1] > y_min && q[1] <= p[1] {
72                            x_min = q[0];
73                            y_min = q[1];
74
75                            pairs + 1
76                        } else {
77                            pairs
78                        }
79                    })
80            }) as _
81    }
82}
83
84/// 3197h Find the Minimum Area to Cover All Ones II
85struct Sol3197 {}
86
87impl Sol3197 {
88    /// 1 <= Rows, Cols <= 30
89    /// N_rc: [0, 1]
90    pub fn minimum_sum(grid: Vec<Vec<i32>>) -> i32 {
91        fn square_all_ones(grid: &[Vec<i32>], t: usize, b: usize, l: usize, r: usize) -> usize {
92            let (mut top, mut bottom) = (usize::MAX, 0);
93            let (mut left, mut right) = (usize::MAX, 0);
94
95            for (y, row) in grid.iter().enumerate().skip(t).take(b - t + 1) {
96                for (x, &g) in row.iter().enumerate().skip(l).take(r - l + 1) {
97                    if g == 1 {
98                        (top, bottom) = (top.min(y), bottom.max(y));
99                        (left, right) = (left.min(x), right.max(x));
100                    }
101                }
102            }
103
104            if top <= bottom && left <= right {
105                (bottom - top + 1) * (right - left + 1)
106            } else {
107                usize::MAX / 3
108            }
109        }
110
111        fn check(grid: &[Vec<i32>]) -> usize {
112            let (rows, cols) = (grid.len(), grid[0].len());
113
114            let mut v = rows * cols;
115            for r in 0..rows - 1 {
116                for c in 0..cols - 1 {
117                    v = v.min(
118                        square_all_ones(grid, 0, r, 0, cols - 1)
119                            + square_all_ones(grid, r + 1, rows - 1, 0, c)
120                            + square_all_ones(grid, r + 1, rows - 1, c + 1, cols - 1),
121                    );
122                    v = v.min(
123                        square_all_ones(grid, 0, r, 0, c)
124                            + square_all_ones(grid, 0, r, c + 1, cols - 1)
125                            + square_all_ones(grid, r + 1, rows - 1, 0, cols - 1),
126                    );
127                }
128            }
129
130            for r in 0..rows - 2 {
131                for r_m in r + 1..rows - 1 {
132                    v = v.min(
133                        square_all_ones(grid, 0, r, 0, cols - 1)
134                            + square_all_ones(grid, r + 1, r_m, 0, cols - 1)
135                            + square_all_ones(grid, r_m + 1, rows - 1, 0, cols - 1),
136                    );
137                }
138            }
139
140            v
141        }
142
143        fn rotate90ccw(grid: &[Vec<i32>]) -> Vec<Vec<i32>> {
144            let (rows, cols) = (grid.len(), grid[0].len());
145            let mut rotated = vec![vec![0; rows]; cols];
146
147            for (r, row) in grid.iter().enumerate() {
148                for (c, &g) in row.iter().enumerate() {
149                    rotated[cols - c - 1][r] = g;
150                }
151            }
152
153            for row in grid {
154                println!(" {row:?}");
155            }
156            println!("--|CCW:90|-> ");
157            for row in &rotated {
158                println!(" {row:?}");
159            }
160
161            rotated
162        }
163
164        check(&grid).min(check(&rotate90ccw(&grid))) as _
165    }
166}
167
168#[cfg(test)]
169mod tests;
enumeration/lib.rs

enumeration/
lib.rs
