C. Salyg1n and the MEX Game

and solution of this problem with proof in Rust Language

Introduction

In this article, we will see my solution to the codeforces problem, 1867C. Salyg1n and the MEX Game, which came in Codeforces Round 897 (Div. 2).

This is an interactive problem!

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.

Approach

In this problem, we can see that we can each time add a number, and a number less than that will be removed in next turn, until we add minimum number.

So, we have to add the mex of the array each time, till we reach the 0.

Proof

Let us suppose to the contradiction that adding mex is not the optimal solution. This means that we can add x that can become mex, also there is an element y which is current mex.

Then, Bob can remove an element from the array, such that there are 2 elements less than x missing from the array.

As Alice can only add 1 element at a time, after which, 1 element will be removed from the array, so net change in elements less than x is at max 1.

Hence, we can say that there is always a missing element less than x, so mex will always be less than x.

But this contradicts our assumption.

Hence, we have to add mex each time.

Hence Proved.

Implementation

We first find the mex of the array. Then we output it. Now, we take the input and print it, till -1, because the element removed will be new mex.

Program

Program using above implementation is

/*
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::io::stdin;

fn take_int() -> i128 {
    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;
}

// Find Mex function

fn find_mex(arr:&Vec<usize>) ->usize{
    // If missing element is less than largest element
    for i in 0..arr.len() { if arr[i]!=i { return i;} }

    // Else, if all elements present upto n-1, return n
    // For example array is 0, 1, 2, return 3
    return arr.len();
}

fn solve() {
// ======================= Code Here =========================
    let _n = take_int();
    let mut arr = take_vector();

    // Sort the vector and find the mex
    arr.sort();
    let mex = find_mex(&arr) as i128;

    println!("{}", mex);
    let mut choice = take_int();

    // Print the input, till we reach -1
    while choice >= 0 {
        println!("{}", choice);
        choice = take_int();
    }
}

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

Conclusion

In this article, we discussed solution to Codeforces problem 1867C. Salyg1n and the MEX Game along with proof and program in Rust Language.

Thank You