C. Colorful Table

and solution of this problem with proof in Rust Language


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 1 : Clearly, if if bi,j = ai, then clearly bj,i = ai 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)


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.


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.


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
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 {
// Minimum set contains all the available indices
let mut minimum = BTreeSet::new();
// Insert all the indices in the beginning
for i in 0..n {
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] {
pub fn main() {
let t = take_int();
for _ in 0..t { solve(); }


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

Thank You