Home
Blog
English 日本語

AtCoder ABC344 Contest sum-up

Mar-11-2024
AtCoder rust algorithms abc344

Overall Result

Again a similar result, with questions A, B and C answered pretty quickly and then got stuck on question E. This time I fought against the Rust borrower, which forced me to dig into this deeper. It is good to see as an incentive to learn more stuff!

Task C - A+B+C

We have three sequences: A, B and C. For a given integer Q, can we select one element of A, one of B and one of C so that their sum is equal to Q?

Generally for the first three questions the complexity is not an issue (yet), and this one is no exception. At most each sequence is 100 integer long. Therefore looking at all the possibilities is at most 100*100*100=1_000_000 possibilities. Which is a big number, but should be OK to not be too long. (At least in rust). So I will compute every possibility of A+B+C and store the results in a hash set, to be able to access those in O(1). Then I just check if the set contains the value queried. The code is: (only the algorithm is extracted here)

// n is the length of sequence A, m is for sequence B, l is for sequence C
for i in 0..n {
        for j in 0..m {
            for k in 0..l {
                // We insert the result in the hashSet
                multiples_set.insert(a[i] + b[j] + c[k]);
            }
        }
    }
    // Looking at all the queries in input
    for i in 0..q {
        if multiples_set.contains(&x[i]) {
            println!("Yes");
        } else {
            println!("No");
        }
    }

Task E - “Insert or Erase”

Description

We have a sequence of distinct numbers that we are going to modify step by step. The goal is to display the sequence after taking into account all the modifications. At each step, we can either delete one element, or insert a new element. Modifications are designed in such way that the sequence will still contain distinct elements at all times. There are two challenges in this task:

  • At each step, we are not instructed to delete an element / insert a new one by their indexes, but by their values.
  • This being a Task E, the complexity matters (maximum sequence length of 10^5 and 10^5 number of queries). The above two points means that we have to track where each element is located, as we cannot afford to look for them each time.

Where I failed

I looked briefly at the Task D and decided I would be more lucky with Task E, and I ended up wasting too much time on it. I tried to build a HashMap of indexes - the issue being that when we insert or delete one element, all the indexes of the element after this one should be modified - and modifying all those will take too much time. I tried to think about a way to keep only the differences - but then I didn’t manage to keep those numbers significant if an element was deleted and then inserted a few steps later.

The solution (implemented the following day)

Looking at the editorial, the ideal data structure was a linked list, where each element is connected to the next one and the previous one. Therefore each insertion or deletion will cost only constant time. In order to implement this in Rust, I created a structure to contain the references to the next and previous, and had to spend a lot of time to clear borrower errors. (Ouch). But the solution is pretty straightforward, and then it gave me some material to write a summary of this borrowing issue so that I can refer to it in a few months.

We will store the linked list into the following structure:

#[derive(Clone, Copy)]
struct Element {
    next: Option<usize>,
    prev: Option<usize>,
}

And we will keep a HashMap associating each value with this Element, in order to be able to process queries in constant time.

We will insert an element at the beginning which does not belong to the sequence. This will be helpful at the end to browse the linked list and display its elements in the right order.

The whole code is too long to display, but for example here is the part where we deal with the supression of an element:

    // We need to delete the element of value 'x'
    // indexes is the HashMap containing references to the linked list element
    let &element_x = indexes.get(&x).unwrap();
    let element_after_x = element_x.next;
    if let Some(prev) = element_x.prev {
        indexes.entry(prev).and_modify(|e| e.next = Some(element_after_x.unwrap()));
    }
    if let Some(next) = element_x.next {
        indexes.entry(next).and_modify(|f| f.prev = element_x.prev);
    }

I spent some time to figure out how to make the compiler compile the above code - this deserves its own individual blog post. Long story short: When a struct causes trouble with the borrower, think about deriving the Copy trait.

Here is a link with a successful solution.

Task D - String bags

Description

We have a list of set of strings, one target string. The question is if it is possible to build the target string by concatenating strings of the subset, and if yes what is the minimum amount of substrings required.

Solution

The brute force solution would be to look at all the sub-string combinations. But when we look at this we can notice that if we build the tree of solutions there is significant overlap. (e.g. if we concatenate a, then bc, it’s the same than concatenating ab and c). So this calls for dynamic programming in order to optimize and reduce the decision tree size.

The dynamic programming function will be in essence: ” If I know how to build the n first letters of the target string with strings from the first i sets and with cost c, which strings can I build for the first i+1 sets and what will be the cost?”

Code

I used a helper function is_substring_matching to check whether a substring matches the target string.

fn is_substring_matching(target: &Vec<char>, string_to_add: &String, start: usize) -> bool {
    if start + string_to_add.len() > target.len() {
        return false;
    }
    return string_to_add.chars().enumerate().fold(true, | acc, (i,c)| acc && (c == target[start+i]));
}

As an aside, what I like with trust is that we can incorporate unit tests inside the source code, for example in this way:

#[test]
fn test_substring_matching() {
    let target = vec!['a','b','c','d'];
    let string_to_add = "bc".to_string();
    assert_eq!(is_substring_matching(&target, &string_to_add, 1), true);
    assert_eq!(is_substring_matching(&target, &string_to_add, 0), false);
    assert_eq!(is_substring_matching(&target, &string_to_add, 2), false);
    assert_eq!(is_substring_matching(&target, &string_to_add, 3), false);
}

Having this kind of helpers and unit tests easily accessible enable to quickly build confidence in some parts of the code, this greatly helps debugging under time pressure.

And here is the main loop:

    // t is the target string, `pieces` contain the set of substrings we could use
    // Now we will prepare the DP table
    // The DP[i][j] will contain the min cost that we can get for the first j characters (if any) after the i-th substring "bag".
    let mut dp: Vec<Vec<Option<usize>>> = vec![vec![None;t.len()+1];n+1];
    for i in 0..n{
        // For each layer we have to add to the solutions the possibility to start from scratch with each piece
        for k in 0..pieces[i].len() {
            let string_to_add = &pieces[i][k];
            if is_substring_matching(&t, string_to_add, 0) {
                // We start from scratch, the cost is 1, so it's the best solution for now
                dp[i][string_to_add.len()] = Some(1);
            }
        }
        // If we already had solutions, we have to check the combinations with the previous layer
        if i > 0 {
            // For each layer, we look at the solutions we had in the previous layer
            for j in 0..t.len()+1 {
                if let Some(cost) = dp[i-1][j] {
                    // Each time we had a solution in the previous layer, one possibility is to not concatenate anything and propagate this solution to the next layer
                    dp[i][j] = Some(cost.min(dp[i][j].unwrap_or(MAX_COST)));
                    // And we have to see if we can combine this previous solution with the string
                    for k in 0..pieces[i].len() {
                        let string_to_add = &pieces[i][k];
                        // Now we need to see if the string to add "fits" with the target string t, at the right position
                        if is_substring_matching(&t, string_to_add, j) {
                            // If it fits, we have to see if we already have a way to get to this length. If we do, we have to take the minimum
                            dp[i][j+string_to_add.len()] = Some(dp[i][j + string_to_add.len()].unwrap_or(MAX_COST).min(cost + 1));
                        }
                    }
                }
            }
        }