CSES - Datatähti 2024 alku - Results
Submission details
Task:Uolevin kalansaalis
Sender:Roopekt
Submission time:2023-11-12 14:07:24 +0200
Language:Rust
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED37
#2ACCEPTED63
Test results
testverdicttimegroup
#1ACCEPTED0.00 s1, 2details
#2ACCEPTED0.00 s1, 2details
#3ACCEPTED0.00 s1, 2details
#4ACCEPTED0.00 s1, 2details
#5ACCEPTED0.00 s1, 2details
#6ACCEPTED0.00 s1, 2details
#7ACCEPTED0.00 s1, 2details
#8ACCEPTED0.00 s1, 2details
#9ACCEPTED0.00 s1, 2details
#10ACCEPTED0.00 s1, 2details
#11ACCEPTED0.00 s1, 2details
#12ACCEPTED0.00 s1, 2details
#13ACCEPTED0.00 s1, 2details
#14ACCEPTED0.00 s1, 2details
#15ACCEPTED0.00 s1, 2details
#16ACCEPTED0.45 s2details
#17ACCEPTED0.45 s2details
#18ACCEPTED0.47 s2details
#19ACCEPTED0.44 s2details
#20ACCEPTED0.45 s2details
#21ACCEPTED0.44 s2details
#22ACCEPTED0.44 s2details
#23ACCEPTED0.44 s2details
#24ACCEPTED0.45 s2details

Compiler report

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

Code

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 details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
5 6 13
1 1 K
5 1 K
2 2 H
4 2 H
...

correct output
-16

user output
-16

Test 2

Group: 1, 2

Verdict: ACCEPTED

input
5 6 7
1 5 K
4 6 K
2 4 H
2 5 H
...

correct output
0

user output
0

Test 3

Group: 1, 2

Verdict: ACCEPTED

input
5 6 7
5 5 K
2 6 K
2 4 H
2 5 H
...

correct output
0

user output
0

Test 4

Group: 1, 2

Verdict: ACCEPTED

input
10 10 51
3 3 H
6 3 H
9 5 H
5 10 H
...

correct output
50

user output
50

Test 5

Group: 1, 2

Verdict: ACCEPTED

input
10 10 52
3 5 H
3 1 H
9 6 H
2 8 H
...

correct output
40

user output
40

Test 6

Group: 1, 2

Verdict: ACCEPTED

input
10 10 60
6 10 H
2 8 H
5 8 H
8 10 H
...

correct output
-15

user output
-15

Test 7

Group: 1, 2

Verdict: ACCEPTED

input
10 10 60
4 7 H
7 4 H
4 10 H
3 6 H
...

correct output
60

user output
60

Test 8

Group: 1, 2

Verdict: ACCEPTED

input
10 10 40
9 9 H
5 10 H
5 6 H
4 9 H
...

correct output
2

user output
2

Test 9

Group: 1, 2

Verdict: ACCEPTED

input
1 1 0

correct output
0

user output
0

Test 10

Group: 1, 2

Verdict: ACCEPTED

input
1 1 1
1 1 K

correct output
0

user output
0

Test 11

Group: 1, 2

Verdict: ACCEPTED

input
1 1 1
1 1 H

correct output
0

user output
0

Test 12

Group: 1, 2

Verdict: ACCEPTED

input
10 5 32
10 3 H
4 4 H
3 3 H
5 4 H
...

correct output
20

user output
20

Test 13

Group: 1, 2

Verdict: ACCEPTED

input
5 10 32
5 9 H
2 4 H
2 9 H
2 5 H
...

correct output
28

user output
28

Test 14

Group: 1, 2

Verdict: ACCEPTED

input
10 10 100
2 9 H
5 4 H
5 9 K
6 1 K
...

correct output
-439

user output
-439

Test 15

Group: 1, 2

Verdict: ACCEPTED

input
10 10 100
8 9 H
5 10 H
5 4 H
3 9 H
...

correct output
88

user output
88

Test 16

Group: 2

Verdict: ACCEPTED

input
500 500 125000
125 261 K
84 78 K
11 200 K
481 246 K
...

correct output
-624270

user output
-624270

Test 17

Group: 2

Verdict: ACCEPTED

input
500 500 125100
16 61 H
37 62 H
459 125 H
318 476 H
...

correct output
124020

user output
124020

Test 18

Group: 2

Verdict: ACCEPTED

input
500 500 249999
22 214 H
356 145 H
341 29 H
393 262 H
...

correct output
249999

user output
249999

Test 19

Group: 2

Verdict: ACCEPTED

input
500 500 32000
30 81 H
315 34 H
78 112 H
367 166 H
...

correct output
10126

user output
10126

Test 20

Group: 2

Verdict: ACCEPTED

input
500 500 126745
164 390 H
126 331 H
164 126 H
55 92 H
...

correct output
-104692

user output
-104692

Test 21

Group: 2

Verdict: ACCEPTED

input
500 500 71200
106 191 H
314 189 H
482 485 H
344 401 H
...

correct output
-335853

user output
-335853

Test 22

Group: 2

Verdict: ACCEPTED

input
500 500 67772
421 277 H
428 470 H
169 142 H
256 345 H
...

correct output
-208567

user output
-208567

Test 23

Group: 2

Verdict: ACCEPTED

input
500 500 27434
366 481 H
38 22 H
126 107 H
135 169 H
...

correct output
-57100

user output
-57100

Test 24

Group: 2

Verdict: ACCEPTED

input
500 500 93982
183 13 H
463 230 H
264 351 H
399 290 H
...

correct output
-52800

user output
-52800