AtCoder ABC337 Contest

Overview

That was fun. I managed to solve the first 4 problems rather quickly, got stuck on the last problem ‘E’. Best AtCoder score so far!

Task C - “Lining Up 2”

Official Description

N persons are queuing. We are given a mapping between each person and the index of the person behind them. We want then to display the queue in the order in which people are waiting.

I just stored in a HashMap the inverse relation, i.e. who is in front instead of who is behind. Then I can just browse the list in the opposite order and display accordingly.

let mut behind: HashMap<usize, usize> = HashMap::new();
    let mut  start_index: usize = 0;
    for i in 0..n {
        let who_is_in_front = a[i];
        if who_is_in_front == -1 {
            start_index = i+1;
        } else {
            behind.insert(who_is_in_front as usize, i+1);
        }
    }

    let mut current_index = start_index;
    for _i in 0..n{
        print!("{} ", current_index);
        current_index = *behind.get(&current_index).unwrap_or(&0);
    }
    println!();

Task D - Cheating Gomoku Narabe

Official Description

Summary

We have a grid filled either with x, o or blanks .. The question is, what is the minimum amount of o we need to add in blank spaces to have K o aligned?

Solution

It would too complicated or costly to search for all the possibilities. Noticing that we don’t need to remember where the K-aligned o is located, we can just browse all the rows and then all the columns and figure out the corresponding minimum operations.

The core idea is to use a sliding window algorithm. If one row’s width is W and W>K, we will look at the “leftmost” K cells, and count what the numbers of o, x and blanks inside this window.

• If there is a x inside, we cannot have K aligned
• If there is no x inside, we just need to change all the blanks into o, so the number of operations is equal to the number of blanks. Then we “slide” the window of one index to the right, and we edit the count of corresponding tiles. We add to the respective counts according to the nature of the tile that we “gained” on the right, and we decrease the corresponding count of the tile we “lost” on the left.

We do the same thing for all rows and all columns, we will have then an algorithm in O(H*W) because each grid tile will be looked at just once.

The code is the following:

fn main() {
    input! {
       h: usize,
       w: usize,
       k: usize,
       s: [Chars; h],
    };

    // Looking at rows first
    let mut min_cost = 1000000000;
    let mut found = false;
    // k might be bigger than the width, in such case we just need to skip this part
    if k <= w {
        for i in 0..h{
            let mut numX = 0;
            let mut numO = 0;
            let mut numB = 0;

            for j in 0..k {
                if s[i][j] == 'x' {
                    numX += 1;
                } else if s[i][j] == 'o' {
                    numO += 1;
                } else {
                    numB += 1;
                }
            }
            if numX == 0 {
                let current_cost = numB;
                min_cost = min_cost.min(current_cost);
                found = true;
            }
            for j in 0..(w-k) {
                // We will add the char at j+k and remove the one at j
                if s[i][j] == 'x' {
                    numX -= 1;
                } else if s[i][j] == 'o' {
                    numO -= 1;
                } else {
                    numB -= 1;
                }
                if s[i][j+k] == 'x' {
                    numX += 1;
                } else if s[i][j+k] == 'o' {
                    numO += 1;
                } else {
                    numB += 1;
                }
                if numX == 0 {
                    let current_cost = numB;
                    min_cost = min_cost.min(current_cost);
                    found = true;
                }
            }
        }

    }

    if k <= h {
        for j in 0..w {
            let mut numX = 0;
            let mut numO = 0;
            let mut numB = 0;

            for i in 0..k {
                if s[i][j] == 'x' {
                    numX += 1;
                } else if s[i][j] == 'o' {
                    numO += 1;
                } else {
                    numB += 1;
                }
            }
            if numX == 0 {
                let current_cost = numB;
                min_cost = min_cost.min(current_cost);
                found = true;
            }
            for i in 0..(h-k) {
                // We will add the char at i+k and remove the one at i
                if s[i][j] == 'x' {
                    numX -= 1;
                } else if s[i][j] == 'o' {
                    numO -= 1;
                } else {
                    numB -= 1;
                }
                if s[i+k][j] == 'x' {
                    numX += 1;
                } else if s[i+k][j] == 'o' {
                    numO += 1;
                } else {
                    numB += 1;
                }
                if numX == 0 {
                    let current_cost = numB;
                    min_cost = min_cost.min(current_cost);
                    found = true;
                }
            }
        }
    }

    if !found {
        println!("-1");
        return;
    }
    println!("{}", min_cost);

}