1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
// Problem A from the Google Code Jam finals 2017.
// https://code.google.com/codejam/contest/dashboard?c=6314486#s=p0&a=0
use pathfinding::prelude::*;
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};
use std::io::prelude::*;
use std::io::{self, Cursor};
use std::num::ParseIntError;
#[derive(Debug)]
#[allow(dead_code)]
enum Error {
Io(io::Error),
Parse(ParseIntError),
}
impl From<io::Error> for Error {
fn from(err: io::Error) -> Self {
Self::Io(err)
}
}
impl From<ParseIntError> for Error {
fn from(err: ParseIntError) -> Self {
Self::Parse(err)
}
}
fn read_ints(file: &mut dyn BufRead) -> Result<Vec<usize>, Error> {
let mut s = String::new();
file.read_line(&mut s)?;
s.pop();
s.split(' ')
.map(|w| w.parse::<usize>().map_err(Into::into))
.collect()
}
fn test<EK: EdmondsKarp<i32>>(n: usize, file: &mut dyn BufRead) -> Result<String, Error> {
let n_dices = read_ints(file)?[0];
let mut dices = Vec::new();
let mut values = HashMap::new();
for d in 0..n_dices {
let mut dice = read_ints(file)?;
for v in dice.clone() {
values.entry(v).or_insert_with(HashSet::new).insert(d);
}
dice.sort_unstable();
dices.push(dice);
}
let mut groups: Vec<Vec<usize>> = Vec::new();
let mut keys = values.keys().collect::<Vec<_>>();
keys.sort();
for &v in keys {
if groups.is_empty() || *groups.last().unwrap().last().unwrap() != v - 1 {
groups.push(vec![v]);
} else {
groups.last_mut().unwrap().push(v);
}
}
let answer = groups
.into_iter()
.map(|group| {
// Extract the dices used for this group.
let subdices = group
.iter()
.flat_map(|&v| values[&v].clone())
.collect::<BTreeSet<_>>()
.into_iter()
.enumerate()
.map(|(a, b)| (b, a))
.collect::<BTreeMap<_, _>>();
// Source is 0, sink is 1. Group members are 2 .. 2 + group.len(), dices are
// 2 + group.len() .. 2 + group.len() + dices.len()
let value_offset = 2;
let dice_offset = value_offset + group.len();
let size = dice_offset + subdices.len();
let mut ek = EK::new(size, 0, 1);
ek.omit_details();
// Set capacity 1 between each value and the dice holding this value.
let smallest_value = group[0];
for &value in &group {
for dice in &values[&value] {
ek.set_capacity(
value - smallest_value + value_offset,
subdices[dice] + dice_offset,
1,
);
}
}
// Set capacity 1 between each dice and the sink.
for i in 0..subdices.len() {
ek.set_capacity(i + dice_offset, 1, 1);
}
// Add path from the source to the first value.
ek.set_capacity(0, value_offset, 1);
let mut bi = 0;
let mut ei = 1;
let mut max = 0;
loop {
let (_, n, _) = ek.augment();
debug_assert!(n >= 0);
#[allow(clippy::cast_sign_loss)]
let n = n as usize;
if n > max {
max = n;
}
if max >= group.len() - bi {
break;
}
if n == ei - bi {
if ei == group.len() {
break;
}
// Add path from source to value group[ei]
ek.set_capacity(0, group[ei] - smallest_value + value_offset, 1);
ei += 1;
} else {
// Remove path from source to value group[bi]
ek.set_capacity(0, group[bi] - smallest_value + value_offset, 0);
bi += 1;
if bi == ei {
ei += 1;
}
}
}
max
})
.max()
.unwrap();
Ok(format!("Case #{n}: {answer}"))
}
fn codejam<EK: EdmondsKarp<i32>>() {
let mut file = Cursor::new(include_str!("A-small-practice.in"));
let ntests = read_ints(&mut file).expect("cannot read number of test cases")[0];
let mut out = String::new();
for n in 1..=ntests {
out += &test::<EK>(n, &mut file).expect("problem with test");
out += "\n";
}
let expected = include_str!("A-small-practice.out");
assert_eq!(out, expected, "answers do not match");
}
#[test]
fn codejam_dense() {
codejam::<DenseCapacity<_>>();
}
#[test]
fn codejam_sparse() {
codejam::<SparseCapacity<_>>();
}
|
