# 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/namanlpGitLab : https://gitlab.com/namanlpWebsite : https://rustp.orgYou can visit https://rustp.org/basic-programs/basic-template/for understanding the templateFeel free to copy the template, but not the solutions :DThank 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 colorslet mut indices = vec![Vec::new(); k+1];for i in 0..n {indices[arr[i]].push(i);}// Minimum set contains all the available indiceslet mut minimum = BTreeSet::new();// Insert all the indices in the beginningfor i in 0..n {minimum.insert(i);}for i in 1..k+1 {// If the color is not present in array at all, return 0if indices[i].is_empty() { print!("0 ");continue; }// Print answerprint!("{} ", 2 * (1+ minimum.last().unwrap()-minimum.first().unwrap()));// Remove the covered indicesfor 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**