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