# 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/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::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 functionfn find_mex(arr:&Vec<usize>) ->usize{// If missing element is less than largest elementfor 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 3return arr.len();}fn solve() {// ======================= Code Here =========================let _n = take_int();let mut arr = take_vector();// Sort the vector and find the mexarr.sort();let mex = find_mex(&arr) as i128;println!("{}", mex);let mut choice = take_int();// Print the input, till we reach -1while 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**