Skip to content

Instantly share code, notes, and snippets.

@robert-king

robert-king/hidden_pancakes.rs

Created May 8, 2022 04:26
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save robert-king/eb8ce0eee18787f833258596e0f9393f to your computer and use it in GitHub Desktop.
Save robert-king/eb8ce0eee18787f833258596e0f9393f to your computer and use it in GitHub Desktop.
Download ZIP
codejam 2021 round 2
Raw
hidden_pancakes.rs
// problem: https://codingcompetitions.withgoogle.com/codejam/round/0000000000435915/00000000007dc20c
// video: https://www.youtube.com/c/RobertKing/videos
// twitter: https://twitter.com/robertkingNZ
pub struct Combination {
fact: Vec<usize>,
inv_fact: Vec<usize>,
modulo: usize,
}
const MOD: u64 = 1_000_000_007;
impl Combination {
pub fn new(max: usize, modulo: usize) -> Self {
let mut inv = vec![0; max + 1];
let mut fact = vec![0; max + 1];
let mut inv_fact = vec![0; max + 1];
inv[1] = 1;
for i in 2..(max + 1) {
inv[i] = inv[modulo % i] * (modulo - modulo / i) % modulo;
}
fact[0] = 1;
inv_fact[0] = 1;
for i in 0..max {
fact[i + 1] = fact[i] * (i + 1) % modulo;
}
for i in 0..max {
inv_fact[i + 1] = inv_fact[i] * inv[i + 1] % modulo;
}
Self {
fact,
inv_fact,
modulo,
}
}
pub fn get(&self, x: usize, y: usize) -> usize {
assert!(x >= y);
self.fact[x] * self.inv_fact[y] % self.modulo * self.inv_fact[x - y] % self.modulo
}
pub fn h(&self, n: usize, r: usize) -> usize {
self.get(n + r - 1, r)
}
}
fn dfs(i: usize, children: &Vec<Vec<usize>>, combo: &Combination) -> (u64, u64) {
let mut p = 1;
let mut sizes = vec![];
for &c in &children[i] {
let (sz, ways) = dfs(c, children, combo);
sizes.push(sz);
p *= ways;
p %= MOD;
}
let tsz: u64 = sizes.iter().sum();
let mut z = 0;
for sz in sizes {
p *= combo.get((tsz-z) as usize, sz as usize) as u64;
p %= MOD;
z += sz;
}
(tsz + 1, p)
}
fn solve(v: Vec<usize>) -> u64 {
let n = v.len();
let mut vis = vec![0];
assert!(v[0] == 1);
let mut children = vec![vec![]; n];
for i in 1..n {
if v[i] > v[i-1] {
if v[i] != v[i-1] + 1 {
return 0;
}
vis.push(i);
} else {
let lost = v[i-1] - v[i] + 1;
assert!(vis.len() >= lost);
for _ in 0..lost-1 {
let x = vis.pop().unwrap();
children[*vis.last().unwrap()].push(x);
}
let x = vis.pop().unwrap();
children[i].push(x);
vis.push(i);
}
}
while vis.len() > 1 {
let x = vis.pop().unwrap();
children[*vis.last().unwrap()].push(x);
}
let mut big = 0;
for i in 0..n {
if v[i] == 1 {
big = i;
}
}
let combo = Combination::new(n, 1_000_000_007);
// println!("{:?} big {} {:?}", children, big, children[big]);
dfs(big, &children, &combo).1
}
fn main() {
let (r, w) = (std::io::stdin(), std::io::stdout());
let mut sc = IO::new(r.lock(), w.lock());
let t: usize = sc.read();
for case_num in 1..=t {
let n: usize = sc.read();
let v = sc.vec(n);
let ans = solve(v);
sc.write(
format!("Case #{}: {}", case_num, ans)
);
sc.write("\n");
}
}
pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);
impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
pub fn new(r: R, w: W) -> IO<R, W> {
IO(r, std::io::BufWriter::new(w))
}
pub fn write<S: ToString>(&mut self, s: S) {
use std::io::Write;
self.1.write_all(s.to_string().as_bytes()).unwrap();
}
pub fn read<T: std::str::FromStr>(&mut self) -> T {
use std::io::Read;
let buf = self
.0
.by_ref()
.bytes()
.map(|b| b.unwrap())
.skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
.take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
.collect::<Vec<_>>();
unsafe { std::str::from_utf8_unchecked(&buf) }
.parse()
.ok()
.expect("Parse error.")
}
pub fn usize0(&mut self) -> usize {
self.read::<usize>() - 1
}
pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.read()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.read::<String>().chars().collect()
}
pub fn binary_vec(&mut self) -> Vec<u8> {
self.read::<String>()
.bytes()
.map(|b| b - b'0')
.collect()
}
}
Raw
retiling.rs
// Problem: https://codingcompetitions.withgoogle.com/codejam/round/0000000000435915/00000000007dc2de
// video: https://www.youtube.com/c/RobertKing/videos
// twitter: https://twitter.com/robertkingNZ
fn main() {
let (r, w) = (std::io::stdin(), std::io::stdout());
let mut sc = IO::new(r.lock(), w.lock());
let t: usize = sc.read();
for case_num in 1..=t {
let r: usize = sc.read();
let c: usize = sc.read();
let f: i64 = sc.read();
let s: i64 = sc.read();
let char_to_bool = &|c| c == 'M';
let g1 = sc.grid(r, char_to_bool);
let g2 = sc.grid(r, char_to_bool);
let start = 0;
let end = 1;
let mut solver = primal_dual::MinimumCostFlowSolver::new(r*c*2+2);
for i in 0..r {
for j in 0..c {
let node = 2 + j + i*c;
solver.add_edge(start, node, 1, 0);
solver.add_edge(node + r*c, end, 1, 0);
}
}
// flat_map
for i in 0..r {
for j in 0..c {
for i2 in 0..r {
for j2 in 0..c {
let mut flip_cost = 0;
if g1[i][j] != g2[i][j] {
flip_cost += f;
}
if g1[i2][j2] != g2[i2][j2] {
flip_cost += f;
}
let mut cost = flip_cost;
if g1[i][j] == g2[i2][j2] && g1[i2][j2] == g2[i][j] {
let d = (i as i64 - i2 as i64).abs() + (j as i64 - j2 as i64).abs();
let swap_cost = d*s;
cost = cost.min(swap_cost)
}
let node1 = 2 + j + i*c;
let node2 = 2 + j2 + i2*c + r*c;
solver.add_edge(node1, node2, 1, cost);
}
}
}
}
let ans = solver.solve(start, end, (r*c) as i64).unwrap()/2;
sc.write(
format!("Case #{}: {}", case_num, ans)
);
sc.write("\n");
}
}
pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);
impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
pub fn new(r: R, w: W) -> IO<R, W> {
IO(r, std::io::BufWriter::new(w))
}
pub fn write<S: ToString>(&mut self, s: S) {
use std::io::Write;
self.1.write_all(s.to_string().as_bytes()).unwrap();
}
pub fn read<T: std::str::FromStr>(&mut self) -> T {
use std::io::Read;
let buf = self
.0
.by_ref()
.bytes()
.map(|b| b.unwrap())
.skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
.take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
.collect::<Vec<_>>();
unsafe { std::str::from_utf8_unchecked(&buf) }
.parse()
.ok()
.expect("Parse error.")
}
pub fn usize0(&mut self) -> usize {
self.read::<usize>() - 1
}
pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
(0..n).map(|_| self.read()).collect()
}
pub fn chars(&mut self) -> Vec<char> {
self.read::<String>().chars().collect()
}
pub fn binary_vec(&mut self) -> Vec<u8> {
self.read::<String>()
.bytes()
.map(|b| b - b'0')
.collect()
}
pub fn grid<T, F>(&mut self, r: usize, f: &F) -> Vec<Vec<T>>
where F: Fn(char) -> T {
let mut g = Vec::with_capacity(r);
for _ in 0..r {
g.push(
self.chars().into_iter().map(f).collect()
)
}
g
}
}
pub mod primal_dual {
use std::cmp;
use std::collections::BinaryHeap;
type Flow = i64;
type Cost = i64;
const INF: Cost = 1 << 60;
struct Edge {
to: usize,
capacity: Flow,
flow: Flow,
cost: Cost,
reverse_to: usize,
}
impl Edge {
fn residue(&self) -> Flow {
self.capacity - self.flow
}
}
pub struct MinimumCostFlowSolver {
graph: Vec<Vec<Edge>>,
previous_edge: Vec<(usize, usize)>,
}
impl MinimumCostFlowSolver {
pub fn new(n: usize) -> Self {
MinimumCostFlowSolver {
graph: (0..n).map(|_| Vec::new()).collect(),
previous_edge: vec![(0, 0); n],
}
}
pub fn add_edge(&mut self, from: usize, to: usize, capacity: Flow, cost: Cost) {
let reverse_from = self.graph[to].len();
let reverse_to = self.graph[from].len();
self.graph[from].push(Edge {
to,
capacity,
flow: 0,
cost,
reverse_to: reverse_from,
});
self.graph[to].push(Edge {
to: from,
capacity,
flow: capacity,
cost: -cost,
reverse_to,
});
}
/// Find the minimum cost to send `flow` through a flow network from `source` to `sink`.
pub fn solve(&mut self, source: usize, sink: usize, mut flow: Flow) -> Option<Flow> {
let n = self.graph.len();
let mut result = 0;
let mut h = vec![0; n];
let mut q: BinaryHeap<(Cost, usize)> = BinaryHeap::new();
while flow > 0 {
let mut dist = vec![INF; n];
dist[source] = 0;
q.push((0, source));
while let Some((current_dist, v)) = q.pop() {
if dist[v] < current_dist {
continue;
}
for (i, e) in self.graph[v].iter().enumerate() {
if e.residue() == 0 {
continue;
}
if dist[e.to] + h[e.to] > current_dist + h[v] + e.cost {
dist[e.to] = current_dist + h[v] + e.cost - h[e.to];
self.previous_edge[e.to] = (v, i);
q.push((dist[e.to], e.to));
}
}
}
if dist[sink] == INF {
return None;
}
for i in 0..n {
h[i] += dist[i];
}
let mut df = flow;
let mut v = sink;
while v != source {
let (prev_v, prev_e) = self.previous_edge[v];
df = cmp::min(df, self.graph[prev_v][prev_e].residue());
v = prev_v;
}
flow -= df;
result += df * h[sink];
let mut v = sink;
while v != source {
let (prev_v, prev_e) = self.previous_edge[v];
self.graph[prev_v][prev_e].flow += df;
let reversed_edge_id = self.graph[prev_v][prev_e].reverse_to;
self.graph[v][reversed_edge_id].flow -= df;
v = prev_v;
}
}
Some(result)
}
/// Find the minimum cost to send `flow` through a flow network, which contains edges of
/// negative cost, from `source` to `sink`.
pub fn neg_solve(&mut self, source: usize, sink: usize, mut flow: Flow) -> Option<Flow> {
let n = self.graph.len();
let mut result = 0;
while flow > 0 {
let mut dist = vec![INF; n];
dist[source] = 0;
loop {
let mut updated = false;
for v in 0..n {
if dist[v] == INF {
continue;
}
for (i, e) in self.graph[v].iter().enumerate() {
if e.residue() == 0 {
continue;
}
if dist[e.to] > dist[v] + e.cost {
dist[e.to] = dist[v] + e.cost;
self.previous_edge[e.to] = (v, i);
updated = true;
}
}
}
if !updated {
break;
}
}
if dist[sink] == INF {
return None;
}
let mut df = flow;
let mut v = sink;
while v != source {
let (prev_v, prev_e) = self.previous_edge[v];
df = cmp::min(df, self.graph[prev_v][prev_e].residue());
v = prev_v;
}
flow -= df;
result += df * dist[sink];
let mut v = sink;
while v != source {
let (prev_v, prev_e) = self.previous_edge[v];
self.graph[prev_v][prev_e].flow += df;
let reversed_edge_id = self.graph[prev_v][prev_e].reverse_to;
self.graph[v][reversed_edge_id].flow -= df;
v = prev_v;
}
}
Some(result)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment