AtCoder ABC336 Contest

Overview

• Well well - After having spent a whole week on graphs as I got stuck on ABC 335 - Task E, it turns out that this week’s contest was not really about data structures, but mostly about maths!
• I answered fairly confidently the first three questions - got stuck on the fourth one.

Task A and B

• The two first questions were more of a warm-up than anything.
• My submissions: Task A and Task B

Task C - Even Digits

Objective

Let a “good integer” be an integer written only with 0, 2, 4, 6, 8, i.e. even digits. The first of such “good integer” is 0, then 2, 4, 6, 8. 10 is out because it contains a 1, so after 8 we jump straight to 20.

The question is, given an integer N, to find the Nth “good integer”.

Algorithm

The brute force algorithm is looking at all integers, testing if they are a “good number” and finding the Nth one. We won’t go very far because N can be pretty big. (10^12 max - that’s a lot).

So ideally we need to find a formula to compute the Nth “good integer”. Looking at the patterns, we can see that [0, 2, 4, 6, 8] is pretty similar to 0, 20, 40, 60, 80 and 0, 200, 400, 600, 800. So I noticed that writing the Nth “good number” was equivalent to writing N in base 5, where each symbol is actually [0,2,4,6,8] multiplied by the corresponding powers of 10.

So my algorithm is first to find the “digits” in the base-5 decomposition of N. Then, for each digit, to add 2*the corresponding power of 10.

The code is the following:

let mut digits_5: Vec<u8> = vec![];
    // The key is to substract 1 from n now!!!
    let mut res = n-1;
    while res != 0 {
        digits_5.push((res % 5) as u8 );
        res /= 5;
    }

    // Now we need to rebuild the number
    let mut ans: usize = 0;
    for i in 0..digits_5.len() {
        ans += 2*(digits_5[i] as usize)*((10 as usize).pow(i as u32));
    }
    println!("{}", ans );

My corresponding submission is here