Contest Results

I solved four questions - and thought that I would get the green belt. Alas, still brown. Still lots of wood to chop!

Task A - Past ABCs

Maybe I spent too much time on this one - checking stuff I should not be checking. The idea is just to check the last three characters of a 6 character strings and check whether those three digits correspond to a past ABC digits.

One convenient trick in Rust is the conversion between a char and a int occurs easily, so to get the number associated with the digits we just need to do the following:

    let d1 = (s[3] as u8 - '0' as u8) as usize ;
    let d2 = (s[4] as u8 - '0' as u8) as usize ;
    let d3 = (s[5] as u8 - '0' as u8) as usize ;

    let d = d1 * 100 + d2 * 10 + d3;
    if d == 316 || d == 0 || d > 349 {
        println!("No");
        return;
    }
    println!("Yes");

Task B - Dentist Aoki

The problem topic obfuscated a bit the actual solution (I kept thinking I had to go to the dentist soon…). Basically we have N boolean values, we read a list of queries where for each query we take the opposite boolean value. And at the end we have to count how many booleans are equal to true. Counting booleans is much easier if we model the situation by an integer worth 0 or 1 instead of a boolean. If we do this, at the end of the process we can just use a function to compute the sum of all elements in an array.

So we have:

    // We initialize the state of all teeth as '1'
    let mut teeth: Vec<usize> = vec![1; n];
    for treatment in t {
        // For each treatment we take the opposite of the teeth boolean
        teeth[treatment - 1] = 1 - teeth[treatment - 1];
    }

    println!("{}", teeth.iter().sum::<usize>());

Note that at the end, we have to use the ::<> operator to indicate Rust in which type we want to aggregate the data. (You don’t need to remember this by heart, the compiler error is easy enough to understand that you can fix the code easily)

Task C - Sort

I took way too much time on this task that I needed to… Somehow, thinking after 9PM at whether the proper index is i or i-1 just broke my brain. (I wish that AtCoder problem data were starting indexes at 0, it would remove unnecessary confusion).

Here we have a permutation of 1..N, and we have to figure out how to sort the data in an array in less than N permutation, and display the permutation list. The fact that this is a permutation is a huge help because:

We know that there won’t be any duplicate, each number between 1 and N appears once and only once.
We already know in which slot each number is going: the number ‘i’ is going at the ‘i-1’ slot. So we will proceed a bit like a selection sort algorithm:

We find the location of the element number 1.
If it is not at its final place, we swap it with whatever element was at its expected place.
And we do the same for the remaining N-1 items. If we generalize this, we can see that at the kth step,
the array indexes between 0 and k-2 is sorted and contains all the integers between 1 and k-1
We can look for the k in the remaining N-k items and swap it.

This works very well for the test examples, but if we look for indexes all the time, the complexity is N^2 which is way too slow. One way to speed this up is to use a HashMap, storing the locations of each element. We will need to update this HashMap each time we swap any elements.

The code becomes:

    // positions will contain references to positions of each element in the array
    let mut positions: HashMap<usize,usize> = HashMap::new();
    // Solutions will contain the list of permutations we have to do
    let mut solutions :Vec<(usize, usize)> = vec![];
    for i in 0..n {
        // To make it cleaner, we subtract 1 from A values to make them 0 indexed
        a[i] = a[i] - 1;
        // We record the current position of each number into the array
        positions.insert(a[i], i);
    }
    // Now position will be a hash table pointing to the position of the element 0..n
    for i in 0..n {
        if *positions.get(&i).unwrap() == i {
            continue;
        }
        let pos_i = *positions.get(&i).unwrap();
        // For better visibility, we use an intermediate variable
        // containing the index we need to swap the ith element with
        // We swap the two elements to get 'i' in the ith position.
        let new_val = a[i];
        a[pos_i] = new_val;
        a[i] = i; // (This is not strictly necessary as we will never look at it again)
        // We swap the positions in the hash table as well
        positions.insert(new_val, pos_i);
        positions.insert(i, i);
        // We record the solution
        solutions.push((i, pos_i));
    }
    // At the end we will need to revert back to the `1-indexed` world
    println!("{}", solutions.len());
    for (i, j) in solutions {
        println!("{} {}", (i+1), (j+1));
    }

Task D - New Friends

We have a graph representing relations between friends. If we edit the graph in the following way: the friend of friend becomes a friend, then how many times can this operation be done? This problem reminded me of the Six degrees of separation which we spoke about in university, which was before any social network was invented. (Internet just appeared). I remember as well spending days on the Oracle of Bacon to see if I could find an actor I knew who was more than 4 connections away from Kevin Bacon. (That was excessively difficult…)

Intutively, if I get connected to all my friend’s friends, then to all of their friends, etc, the end point will be that I will be connected with everybody. Well, almost everybody: what if someone is not connected to anyone of my network? So the idea is the following:

Partition the network in sub-networks completely distinct from each other
Count the number of nodes in each sub-network
Compute the max number of connections in each sub-network (that’s k*(k-1)/2 if k is the number of nodes in this sub-network)
Add all the numbers computed in the previous step, and substract the number of connections we had initially. That’s the number of connections we need to add, which is the answer to the problem.

In order to partition the network, we need to do a union-find algorithm, but it was late and my brain was too tired to figure this out, so I used an already made algorithm in the atcoder library. It worked pretty well - but I note I need to implement this algorithm for my own understanding. For those interested, you can find further explanation on cp-algorithms.com

fn main() {
    input! {
       n: usize,
       m: usize,
       friends: [(usize, usize); m],
    }

    let mut dsu = Dsu::new(n);
    for (a, b) in friends {
        dsu.merge(a - 1, b - 1);
    }

    let mut total_connections: usize = 0;
    dsu.groups()
        .into_iter()
        .for_each(|x| {
            if DEBUG {
                println!("{:?}", x);
            }
            total_connections += ((x.len() - 1) * x.len()) / 2;
        });

    println!("{}", total_connections - m);
}