Task C: Reorder Cards

Source: https://atcoder.jp/contests/abc213/tasks/abc213_c

The problem is the following:

• You set a certain number of cards on the table, creating a grid WxH
• Some cards have numbers, some are blank
• You delete all the rows with only blanks and all the columns with only blanks
• You should figure out the final coordinates of the numbered cards

Solving process

First Algorithm

At the beginning I tried to follow the process described, thinking that it would be a good use of the Enum feature of Rust. However I didn’t want to actually delete rows and columns - that would be too time consuming.

So I defined the

#[derive(Clone, Debug)]

enum Card {
	Empty, // no card (after deletion)
	Number(usize),
	Blank,
}

At each turn I will test whether there are rows / columns with only Blank cards. I will then “soft delete” them, which basically means filling the row/col with Empty cards. When there are no rows or columns to delete, I will then count the number of Blank cards to reach each numbered card, this will give me their final coordinates.

I decided to build several helper functions - this allows me to use the unit test function of Rust, so that I can quickly test if my algorithm’s basic bricks are correct.

For example:

fn is_col_deletable(table: &Vec<Vec<Card>>, j: usize) -> bool {
	let mut count_blanks = 0;
	for i in 0..table.len() {
		match table[i][j] {
			Card::Blank => {
				count_blanks = count_blanks + 1;
			}
			Card::Number(_) => {
				return false;
			}
			Card::Empty => (),
		}
	}
	// when we reach here it means there are no numbers
	return count_blanks != 0;
}

And the associated test function:

#[test]

fn test_is_deletable() {
	let table = vec![
		vec![Card::Blank, Card::Blank, Card::Empty],
		vec![Card::Empty, Card::Blank, Card::Empty],
		vec![Card::Empty, Card::Empty, Card::Empty],
		vec![Card::Number(1), Card::Blank, Card:: Empty]
	];

	assert!(is_row_deletable(&table, 0));
	assert!(is_row_deletable(&table, 1));
	assert!(!is_row_deletable(&table, 2));
	assert!(!is_row_deletable(&table, 3));
	
	assert!(!is_col_deletable(&table, 0));
	assert!(is_col_deletable(&table, 1));
	assert!(!is_col_deletable(&table, 2));
}

The main loop is then very readable and goes like:

let mut finished = false;
while !finished {
	let mut has_deleted_something = false;
	for i in 0..h {
		if is_row_deletable(&table, i) {
			delete_row(&mut table, i);
			has_deleted_something = true;
			continue;
		}
	}

	for j in 0..w {
		if is_col_deletable(&table, j) {
			delete_col(&mut table, j);
			has_deleted_something = true;
			continue;
		}
	}

	if !has_deleted_something {
		finished = true;
	}
}

// Then we need to display the coordinates
for i in 0..n {
	print_coordinates(&table, cards[i].0 - 1, cards[i].1 - 1);
}

The only issue is - the algorithm was too slow in a few of the test cases. Checking at all times if all the rows are empty or not ends up doing just too many tests and/or too many operations.

The final algorithm

Noticing that actually the configuration of the grid doesn’t change, because we delete whole columns or whole rows, so the position of the cards relative to each other doesn’t change meaningfully. In the final configuration, the only columns remaining are the columns with one or more numbers, and likewise for the rows. Finding the final column of a card is equivalent to finding how many columns before this card have a number in them.

What I will do then is:

• Create an array containing all the cards initial column indexes
• Sort the array and remove the duplicates For example, if a card was initially in the column 164, and if the column array begins in the following: [10,45,62,84,112,120,164, ... then I know that eventually the card will be at column 7, which is its index in the column array. Using the example above I will have [(10, 0), (45,1), (62, 3), ...]. In order to find the final column of a card initially in column 62, I need to browse this array until I find the 62, then the solution will be the corresponding index (3) in this case.

In order to speed up the lookup, I will store all the couples (column, index) in a hash table. Then for each card I just need to look up in the hash table the final index for this column.

I end up with:

let mut rows: Vec<usize> = Vec::new();
let mut cols: Vec<usize> = Vec::new();

for i in 0..n {
	let (x, y) = cards[i];
	rows.push(x);
	cols.push(y);
}

rows.sort();
rows.dedup();
cols.sort();
cols.dedup();

// Putting the indexes in a hash_map to speed up the retrieval

let mut row_index: HashMap<usize, usize> = HashMap::new();
let mut col_index: HashMap<usize, usize> = HashMap::new();

for i in 0..rows.len() {
	row_index.insert(rows[i], i);
}

for i in 0..cols.len() {
	col_index.insert(cols[i], i);
}

for i in 0..n {
	let (x, y) = cards[i];
	let index_x = row_index.get(&x).unwrap();
	let index_y = col_index.get(&y).unwrap();
	println!("{} {}", index_x + 1, index_y + 1);
}

The final submission is here