C. Colorful Table

and solution of this problem with proof in Rust Language

Introduction

In this article, we will see my solution to the codeforces problem, C. Colorful Table, which came in Codeforces CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!).

Note : My Solution might not be the most optimized one, but it is certainly working.

You can go to above link to view the question statement.

Observation

Observation 1 : Clearly, if if b_i,j = a_i, then clearly b_j,i = a_i as well because min(x, y) = min(y, x). Conclusion 1 : So, all the elements will form a square, because let us say, length is greater than width. Then, there must be some element, that is present in length, but not in width, which is not possible.

So, we just have to find the edge length of the above-mentioned square to find the answer. This can be achieved

Observation 2 : So, we have to find first and last position where element is minimum. Conclusion 2 : As we have to output the sum of width and height of this rectangle ( or square ), we can simply say that edge of the square is the difference of positions where the element is first minimum and last minimum + 1.

Mathematically : Answer = 2×(1 + last index - first index where element or color is minimum)

Approach

Now, all we have to do is to find for each color, when it is minimum, both in front and back.

For this, first of all, we can store indices of each color in a vector of vector. It will take O( k+N ) time complexity and O( k+N ) space complexity.

Then, we will make an minimum set, and insert all indices at first. Also, it must be a BTreeSet, because we have to find its minimum and maximum value.

Then we will traverse the colors from 1 to k and print the difference of first and last minimum, and remove all the indices of the indices where the color has come using the matrix we made earlier.

Proof

As we are traversing number from 1 to k+1, and removing all the occurrences of the number, it can be easily proved that all the indices of numbers less than given number are already removed from the minimum set.

So, if all the numbers less than the given number are already removed from this set, it is clear that this number is minimum for these indices in the minimum set.

Hence, proved.

Program

/*
This template is made by Naman Garg <[email protected]>
GitHub : https://github.com/namanlp
GitLab : https://gitlab.com/namanlp
Website : https://rustp.org

You can visit https://rustp.org/basic-programs/basic-template/
for understanding the template

Feel free to copy the template, but not the solutions :D
Thank You
 */

#![allow(unused)]

use std::collections::BTreeSet;
use std::io::stdin;

fn take_int() -> usize {
    let mut input = String::new();
    stdin().read_line(&mut input).unwrap();
    return input.trim().parse().unwrap();
}

fn take_vector() -> Vec<usize> {
    let mut input = String::new();
    stdin().read_line(&mut input).unwrap();
    let arr: Vec<usize> = input.trim().split_whitespace().map(|x| x.parse().unwrap()).collect();
    return arr;
}

fn take_string() -> Vec<char> {
    let mut input = String::new();
    stdin().read_line(&mut input).unwrap();
    let vec: Vec<char> = input.trim().chars().collect();
    return vec;
}

fn to_string(vec: Vec<char>) -> String { return vec.iter().collect::<String>(); }

fn solve() {
// ======================= Code Here =========================
    let n_k = take_vector();
    let n = n_k[0];
    let k = n_k[1];

    let arr = take_vector();

    // Matrix for storing indices of the colors
    let mut indices = vec![Vec::new(); k+1];

    for i in 0..n {
        indices[arr[i]].push(i);
    }

    // Minimum set contains all the available indices
    let mut minimum = BTreeSet::new();

    // Insert all the indices in the beginning
    for i in 0..n {
        minimum.insert(i);
    }

    for i in 1..k+1 {
        // If the color is not present in array at all, return 0
        if indices[i].is_empty() { print!("0 ");continue; }

        // Print answer
        print!("{} ", 2 * (1+ minimum.last().unwrap()-minimum.first().unwrap()));

        // Remove the covered indices
        for j in &indices[i] {
            minimum.remove(&j);
        }
    }
    println!();
}

pub fn main() {
    let t = take_int();
    for _ in 0..t { solve(); }
}

Conclusion

In this article, we discussed solution to Codeforces problem 1870C. Colorful Table along with observations, proof and program in Rust Language.

Thank You