2016-1B Problem C

Final solution

use std::collections::HashSet;
pub fn bipartite_match(m: usize, n: usize, connections: &[(usize, usize)]) -> HashSet<(usize, usize)> {
	debug_assert!(connections.iter().collect::<HashSet<_>>().len() == connections.len());

	#[derive(Clone, Copy, PartialEq, Eq, Hash, Debug)]
	enum Node {
		Left(usize),
		Right(usize)
	}

	impl Node {
		fn is_left(&self) -> bool {
			if let Node::Left(_) = self {
				true
			} else {
				false
			}
		}

		fn is_right(&self) -> bool {
			if let Node::Right(_) = self {
				true
			} else {
				false
			}
		}

		fn index(&self) -> usize {
			match self {
				Node::Left(ref n) => *n,
				Node::Right(ref n) => *n
			}
		}
	}

	let mut ltor = vec![Vec::new(); m];
	let mut rtol = vec![Vec::new(); n];
	for (ref l, ref r) in connections.iter() {
		let l = *l;
		let r = *r;
		if l >= m || r >= n {
			panic!("invalid input.");
		}

		ltor[l].push(r);
		rtol[r].push(l);
	}

	let mut current_matches: HashSet<(usize, usize)> = HashSet::new();

	fn aug_can_go(from: &Node, to: &Node, current_matches: &HashSet<(usize, usize)>) -> bool {
		if from.is_left() && to.is_right() {
			!current_matches.contains(&(from.index(), to.index()))
		} else if from.is_right() && to.is_left() {
			current_matches.contains(&(to.index(), from.index()))
		} else {
			unreachable!()
		}
	}

	loop {
		let mut l_matched: Vec<bool> = vec![false; m];
		let mut r_matched: Vec<bool> = vec![false; n];
		for (ref i, ref j) in current_matches.iter() {
			l_matched[*i] = true;
			r_matched[*j] = true;
		}
		fn dfs(
			n: Node,
			ltor: &[Vec<usize>], rtol: &[Vec<usize>],
			current_match: &HashSet<(usize, usize)>,
			r_matched: &[bool],
			visited: &mut HashSet<Node>
		) -> Option<Vec<Node>> {
			assert!(visited.insert(n));
			if n.is_right() && !r_matched[n.index()] {
				return Some(vec![n]);
			}
			let next_hops: Vec<Node> = match n {
				Node::Left(i) => ltor[i].iter().map(|j| Node::Right(*j)).collect(),
				Node::Right(i) => rtol[i].iter().map(|j| Node::Left(*j)).collect(),
			};
			for j in next_hops {
				if aug_can_go(&n, &j, current_match) && !visited.contains(&j) {
					if let Some(mut path) = dfs(j, ltor, rtol, current_match, r_matched, visited) {
						path.push(n);
						return Some(path);
					}
				}
			}
			None
		}
		let dfs_path = (0..m).into_iter()
			.filter(|i| !l_matched[*i])
			.map(|i| dfs(Node::Left(i), &ltor, &rtol, &current_matches, &r_matched, &mut HashSet::new()))
			.find(|x| x.is_some()).flatten();
		if let Some(mut path) = dfs_path {
			path.reverse();
			debug_assert!(path.len() >= 2);
			for w in path.windows(2) {
				let (i, j) = (w[0], w[1]);
				match i {
					Node::Left(i) => {
						debug_assert!(j.is_right());
						current_matches.insert((i, j.index()));
					},
					Node::Right(i) => {
						debug_assert!(j.is_left());
						assert!(current_matches.remove(&(j.index(), i)));
					}
				}
			}
		} else {
			break;
		}
	}

	current_matches
}

fn test() -> usize {
	let n: usize = read_ints()[0];
	use std::collections::HashMap;
	struct WordToId {
		next: usize,
		hm: HashMap<usize, String>,
		rev: HashMap<String, usize>,
	}
	impl WordToId {
		fn with_capacity(cap: usize) -> Self {
			WordToId {
				next: 0,
				hm: HashMap::with_capacity(cap),
				rev: HashMap::with_capacity(cap)
			}
		}
		fn insert(&mut self, w: String) -> usize {
			if self.rev.contains_key(&w) {
				*self.rev.get(&w).unwrap()
			} else {
				let id = self.next;
				self.next += 1;
				self.hm.insert(id, w.clone());
				self.rev.insert(w, id);
				id
			}
		}
		fn len(&self) -> usize {
			self.next
		}
	}
	let mut left = WordToId::with_capacity(n);
	let mut right = WordToId::with_capacity(n);
	let mut edges: HashSet<(usize, usize)> = HashSet::with_capacity(n);
	for _ in 0..n {
		let l = read_line();
		let parts: Vec<&str> = l.split(' ').collect();
		assert_eq!(parts.len(), 2);
		let w = (left.insert(parts[0].to_owned()), right.insert(parts[1].to_owned()));
		edges.insert(w);
	}
	let base_set = bipartite_match(left.len(), right.len(), &edges.iter().copied().collect::<Vec<_>>());
	let mut left_used: Vec<bool> = vec![false; left.len()];
	let mut right_used: Vec<bool> = vec![false; right.len()];
	for w in base_set.iter().copied() {
		left_used[w.0] = true;
		right_used[w.1] = true;
	}
	let mut nb_not_faked = base_set.len();
	for w in edges {
		if base_set.contains(&w) {
			continue;
		}
		if left_used[w.0] && right_used[w.1] {
			continue;
		}
		nb_not_faked += 1;
		left_used[w.0] = true;
		right_used[w.1] = true;
	}
	n - nb_not_faked
}

fn main() {
	let t: usize = read_ints()[0];
	for i in 1..=t {
		println!("Case #{}: {}", i, test());
	}
}

// boilerplate omitted...

Wrong solution

// package, import, etc...

func start() {
  // read T, repeat test() T times...
}

type Topic struct {
	left, right string
}

func test() {
	var N int
	mustReadLineOfInts(&N)
	topics := make([]Topic, 0)
	for i := 0; i < N; i++ {
		line := strings.Split(mustReadLine(), " ")
		assert(len(line) == 2)
		topics = append(topics, Topic{line[0], line[1]})
	}
	count := 0
	leftMap := make(map[string]int)
	rightMap := make(map[string]int)
	for i, t := range topics {
		if _, exist := leftMap[t.left]; exist {
			continue
		}
		if _, seen := rightMap[t.right]; seen {
			continue
		}
		leftMap[t.left] = i
		rightMap[t.right] = i
		debug(fmt.Sprintf("%v", t))
		count++
	}
	// The following 16 lines of code is wrong. This is because although the topic added in each loop will not be fake *at
	// that time*, it can cause previous topics to become fake. I think my mistake is that I thought of the relationship of
	// "faked from" is undirected: if the new topic can't be faked from previous topics, previous topics can't be faked
	// from the new topic. This is not true because "faked from" is a 1-to-2 relationship.
	for i, t := range topics {
		if _, exist := rightMap[t.right]; exist {
			continue
		}
		debug(fmt.Sprintf("%v", t))
		rightMap[t.right] = i
		count++
	}
	for i, t := range topics {
		if _, exist := leftMap[t.left]; exist {
			continue
		}
		debug(fmt.Sprintf("%v", t))
		leftMap[t.left] = i
		count++
	}
	fmt.Fprintf(stdout, "%d\n", N-count)
}

// boilerplate omitted...

1
3
A B
A C
C B

Expected output

Case #1: 1

Sample test cases given in question

3
3
HYDROCARBON COMBUSTION
QUAIL BEHAVIOR
QUAIL COMBUSTION
3
CODE JAM
SPACE JAM
PEARL JAM
2
INTERGALACTIC PLANETARY
PLANETARY INTERGALACTIC

Other files

5
4
A B
A C
D C
D B
9
A B
D B
A C
D C
D F
D E
A E
A F
B F
9
D E
A B
D B
A C
D C
D F
A E
A F
B F
3
H C
Q C
Q B
12
A B
D B
A C
D C
D F
D E
A E
A F
B F
F C
K G
D G