In light of recent events, I think it may be helpful to add a second measurement to problems.

The main issue

Some problems are very "hit or miss" and others are more "standard". Is there a way to quantify this?

The problemsetter's dream

is a problem rated $$$r$$$ such that everyone with rating $$$\ge r$$$ solves it and nobody with rating $$$\lt r$$$ solves it.

Obviously, this could never happen in real life. But we can generalize this idea of a difficulty curve — on the x axis, you'll have the rating, and on the y axis, you'll have the proportion/probability of people at that rating to solve the problem. At $$$r$$$, the value would be 50%.

Here's an example of what a difficulty curve of a 1600-rated problem might look like:

This is the curve of an ideal problem under the Elo model: $$$P(x) = sigmoid(\frac{r-x}{173.7178})$$$ for a problem of rating $$$r$$$ and a person of rating $$$x$$$.

Defining the index

Suppose a person is rated $$$x$$$ and the problem is rated $$$r$$$. This person's contribution to the index would be:

If $$$r \gt x$$$, $$$C = \frac{y-0.5}{E-0.5}$$$, where $$$y$$$ is the 0-1 result and $$$E$$$ is the expected probability calculated using the sigmoid function. If $$$y = E$$$, then the contribution is 1, and if $$$y = 0.5$$$, then the contribution is 0.

If $$$r \lt x$$$, $$$C = \frac{0.5-y}{0.5-E}$$$.

The index of the problem would then be the average of all the contributions. Potentially, we could weight results from low or high rated people slightly heavier, or use a different flavor of average, like mean square or mean exponential.

This would only take O(participants * problems) to calculate for each contest, which is like maybe 10 million cycles worth of CPU time per contest, way less than the amount of work it takes to judge a single submission. Maybe we can even calculate it ourselves with the API, I'm not sure.

The index can be interpreted as:

• Higher than 1: unicorn problem that discriminates even better than what should theoretically be possible under the Elo model
• 1: a perfect problem that discriminates low and high rated people well
• 0 to 1: where most problems are
• 0: a problem that is just a coin flip for everyone and their rating is irrelevant
• Negative: a problem that somehow is easier to solve the lower rated you are

(then, when the index is close to 0, you can cope when you get it wrong by saying it was very hit or miss)

Second idea / yap session

A 1600 rated problem may feel like 1700 to some and 1500 to others. We can model this by treating a problem's difficulty as a sample from a (we're just going to say it's normally distributed to make things easier) distribution. For example, a problem with mean difficulty 1600 and difficulty-standard-deviation 100 would appear as a 1700+ to 1/6 of people, 1500- to 1/6 of people, and between 1500-1700 to most.

Solving for the mean and standard deviation can probably done with maximum likelihood estimation. I did some of this for my Minecraft UHC plugin rating system a while back and it's also part of the Glicko paper, the likelihood with standard deviations involved is much more complicated but can be estimated by $$$g = \sqrt{173.7178^2 + \frac{\pi}{8} \sigma_R^2}$$$, where $$$\sigma_R^2$$$ is the variance in the ratings*, then chance of winning $$$sigmoid(x/g)$$$.

*In the Glicko system, the players' ratings also have variance. Over here, that's not explicit but we can probably just set some kind of hyperparameter "everyone's rating maybe has +/- 150 of uncertainty".

**If you're curious (you probably aren't), the reason why I keep saying $$$173.7178$$$ is because it's $$$\frac{400}{\ln 10}$$$, it converts the "400 points higher = 10 times higher chance of winning" to "173.7178 points higher = $$$e$$$ times higher chance of winning".

Someone smarter than me can take the derivatives and figure out if this is solvable easily :)