### News

## Arena rated round #7

posted on March 27, 2020, 2:21 p.m. 5Welcome to MOI Arena

```
print "Hello, Arena!"
```

We will be organizing the **Arena round #7** on **Friday, March 27th 2020** from **20:00 to 22:30** in Morocco time.

Problems are tenderly prepared and tested by :

Hamza Mouhcine (

)Mohamed Elkhatri (

)

We wish you a higher rating !

Stay tuned, and follow us on Facebook

## Arena round #5 and 2020 second round

posted on Jan. 16, 2020, 11:16 p.m. 0Welcome to MOI Arena

```
print "Hello, Arena!"
```

We will be organizing the **Arena round #5** on **Saturday, January 18th 2020** from **20:00 to 22:00** in Morocco time.

Problems are tenderly prepared and tested by :

Hamza Mouhcine (

)Aymane Lotfi

Stay tuned, and follow us on Facebook

## Tutorial of problem expectation

posted on Jan. 3, 2020, 10:58 p.m. 1Let \(Li\) the expected loss before choosing the next distinct number, given that \(i\) distinct numbers were chosen already. The answer would be \(An = \sum_{i=0}^{n-1}1-Li=n-\sum_{i=0}^{n-1}Li\)

For some \(i\) let's calculate \(Li\) :

In order to be able to perform a \(j^{th}\) pick while still having \(i\) distinct numbers chosen, all previous \(j-1\) picks should've resulted in a loss (one of the \(i\) already chosen numbers is picked again), meaning that the probability that the \(j^{th}\) pick results in a loss is \(P_j=(\frac{i}{n})^{j}\).

The expected amount to be lost in the \(j^{th}\) attempt is \((\frac{i}{n})^{j}\).

\(L_i\) is the sum of expected losses over all possible \(j^{th}\) attempts, thus \(L_i=\sum_{j=1}^{\infty} (\frac{i}{n})^{j}\).

Since that is just the sum of terms of a geometric series we can rewrite \(Li\) as : \(Li = \frac{i}{n}*\frac{1-(\frac{i}{n})^\infty}{1-\frac{i}{n}} = \frac{i}{n-i}\).

We get \(An=n-\sum_{i=0}^{n-1}\frac{i}{n-i}\).

Calculating the sum takes \(O(n)\) time, but we clearly have to answer each query in \(O(1)\) if we look at the constraints, so we should calculate all \(Ak\) and store them beforehand. To do that we find a recursive formula as follows:

\(A_{n+1} - A_{n} = 1 + \sum_{i=0}^{n-1}\frac{i}{n-i} - \sum_{i=1}^{n}\frac{i}{n-(i-1)} = 1 + \sum_{i=0}^{n-1}\frac{i}{n-i} - \sum_{i=0}^{n-1}\frac{i+1}{n-i} = 1 - \sum_{i=0}^{n-1}\frac{1}{n-i} = 1 - \sum_{i=1}^{n}\frac{1}{i}\).

We finally get : \(A_{n+1} = A_n+1 - \sum_{i=1}^{n}\frac{1}{i}\).

Since we know that \(A_1=1\) we can calculate all \(A_k\) in \(O(n)\) time and answer queries in \(O(1)\).

## Arena round #4 and 2020 first round

posted on Dec. 27, 2019, 10:04 p.m. 0Welcome to MOI Arena

```
print "Hello, Arena!"
```

We will be organizing the first rated round of **2020** on **Friday, January 3rd 2020** from **20:00 to 22:00** in Morocco time.

Problems are tenderly prepared and tested by :

Omar Salim Moussa (

)Nabil Sahifa (

)And myself (

)

Stay tuned, and follow us on Facebook]