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 > 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 < 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)
↵
### 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 > 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 < 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)
