Welcome 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 (BNL)

• Mohamed Elkhatri (medk)

We wish you a higher rating !

Stay tuned, and follow us on Facebook

Welcome 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 (BNL)

• Aymane Lotfi

Stay tuned, and follow us on Facebook

Let \(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)\).

Welcome 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 (osm97)

• Nabil Sahifa (nabil_shf)

• And myself (moncef)

Stay tuned, and follow us on Facebook]