AtCoder 340

Summary

More silly mistakes where I lost time and couldn’t finish. I just finished questions A and B. Was pretty close, though!

Task C: Divide and Divide

This task was with hindsight not excessively complex. I did not understand however one detail, which prevented me from finding the result.

Basically, you start from one number n and divide by 2 until you reach 1. The twist is that when n is odd, you need to process the division of both n/2 and (n+1)/2. (The problem mentions essentially the floor and the ceiling of n/2, but that’s the same thing).

My mistake was that I did not understand that when n was even, you were processing n/2 twice.

Anyway. In essence we have a very simple recursive function, and we need to compute the following:

f(n) = n + f((n+1)/2) + f(n/2)

Now we can notice pretty quickly (especially if we work on paper first) that:

• The basic recursion takes too much time
• We end up computing always the same values

So what we need to do is memoize the result, which is a fancy word to say that we just remember it.

The code in Rust end up being:

// This will be our recursive function
// The first parameter is the cache in which we store already computed values
fn f(cache: &mut HashMap<usize,usize>, n: usize) -> usize {
    if n == 1 {
        return 0;
    }

    // If we already computed the value, we stop!
    if let Some(&v) = cache.get(&n) {
        return v;
    }

    // If not, we make the recursive call and save the value
    let a1 = f(cache, n/2);
    let a2 = f(cache, (n+1)/2);
    cache.insert(n, a1 + a2 + n);
    return a1 + a2 + n;
}

// The main function is then just calling the recursion with the proper cache
fn main() {
    input! {
       n: usize,
    };
    let mut cache: HashMap<usize,usize> = HashMap::new();
    println!("{}", f(&mut cache, n));
}

Task D: Super Takahashi Brothers

In this problem we have a video game for which we want to clear the level N. To do so we have to ways to get there:

• Each level can lead to the next one with a corresponding cost Ai
• Each level can lead to another one Xi with a corresponding cost Bi

We can model this situation with a directed and weighted graph, and the aim is to find the minimum distance between the start node and the end node. This graph has potentially some cycles, so we will use the Djikstra algorithm. The easiest way to do this is to use the library allowed by the contest.

use pathfinding::directed::dijkstra::dijkstra;

fn main() {
    input! {
       n: usize,
       levels: [(usize,usize,usize); n-1]
    }

    let result = dijkstra(
        &0,
        |x| if *x == n-1 { vec!{} } else { vec![(*x + 1, levels[*x].0), (levels[*x].2-1, levels[*x].1)] },
        |x| *x == n - 1
    );

    println!("{}", result.unwrap().1);

Note the way to use this library:

• The first parameter is the start state
• The second parameter is a anonymous function (closure in Rust) which implements the transition between states, and returns a vector of couples (neighbour,cost) with all the corresponding neighbours and the relative cost to get there.
• The last parameter will be a function which returns true when the state is the final state.

That’s very efficient, but not very interesting - so we can actually implement the algorithm by ourselves. In Rust we use the data structure called BinaryHeap to implement the priority queue. The issue is that it is a max_heap, so we need to define a Struct element and redefine the ordering to get what we need.

use std::collections::BinaryHeap;

use proconio::input;

#[derive(Eq, PartialEq, Debug, Clone, Copy)]
struct PathData {
    node: usize,
    cost: usize,
}
impl PartialOrd for PathData {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(other.cost.cmp(&self.cost))
    }
}
impl Ord for PathData {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        other.cost.cmp(&self.cost)
    }
}

fn main() {
    input! {
       n: usize,
       levels: [(usize,usize,usize); n-1]
    }

    // Setup a clean adjacency list
    let mut adjacency_list = vec![vec![];n];
    for i in 0..n - 1 {
        let (a, b, x) = levels[i];
        adjacency_list[i].push((i + 1, a));
        adjacency_list[i].push((x - 1, b));
    }

    // Implementing Dijkstra's algorithm
    let mut dist = vec![std::usize::MAX; n];
    let mut queue: BinaryHeap<PathData> = std::collections::BinaryHeap::new();
    let mut visited = vec![false; n];
    dist[0] = 0;
    queue.push(PathData { node: 0, cost: 0 });
    while queue.len() > 0 {
        let path_data = queue.pop().unwrap();
        if visited[path_data.node] {
            continue;
        }
        visited[path_data.node] = true;
        for (v, w) in adjacency_list[path_data.node].iter() {
            if dist[*v] > path_data.cost + *w && !visited[*v] {
                dist[*v] = path_data.cost + *w;
                queue.push(PathData { node: *v, cost: dist[*v] });
            }
        }
    }

    println!("{}", dist[n - 1]);
}

I will write another post about Djikstra’s algorithm in Rust, as it is pretty interesting.