Rota Boards - A Proposed New Problem
Back to General discussions forum
Initial algorithms will need to be modified to deal efficiently with the larger sets of test data.
Initial algorithms will need to be modified to deal efficiently with the larger sets of test data. - this holds for almost any programming problem, so doesn't explain why this task is special.
The usual modifications to algorithms are certainly relevant here but they are not sufficient on their own. A significant change is required but it will spoil the problem if I go into further details.
Tried to solve this problem and found out that I need to generate 2 ^ 104 - 2 combinations. Definitely a significant change is required compared to naive solution...
I initially started googling for CSFP but upon getting irrelevant results suspected this may stand for "Clive S Fraser's Problems", right?
Besides from paying due respect to Clive as the most active author of us all nowadays, I think, we can introduce difficulty marks, perhaps in form of tags :)
Yes, that was a little homage to CSFPython. And my own, very subjective view of the problem difficulty.
Mathias, this reminded me of the idea expressed long ago that users may assign tags to problems. I never could come up with solution to make tags "democratically governered" by all users, but your initiative just gave me thought this could be enabled for a small group.
Unless I did some grave mistake you should be able to see little Tags link in the top of the any problem page. This
will take you where tags could be assigned to the problem (and also new tags created when needed).
I added tags csfp-8 and csfp-2-5 couple days ago to the latest Clive's problems by the way. Feel free to add more
and assign them according to your "very subjective view of problem difficulty" and other properties (as I guess your
subjective view is quite exceeding mine).
If the feature is working and not borken (e.g. you suddenly find you can't login or can't solve problems etc) - I think we switch it on for some other colleagues (e.g. Clive himself and Vladimir Z) - perhaps this may be better for categorizing the problems.
Hi, thanks for this update. I'll might add some tags to more recent problems. I think difficulty tags can be problematic as that is quite subjective. Maybe a slightly more generic approach would be possible: - Users with a certain rank can "vote", e.g. priest upwards (to ensure they have seen a good mix of problems). - They can choose from difficulty 1 (very easy) to 5 (super hard), or maybe in the range 1 to 10. - The page displays the average.
I think difficulty tags can be problematic as that is quite subjective.
Subjective, for sure. But is it really "problematic"? People may regard them as a friendly guidance from the experienced colleague(s) or ignore altogether :)
And tags always could be adjusted/removed later... They are supplementary (though useful) - not breaking anything etc.
Users with a certain rank can "vote"... They can choose from difficulty 1 (very easy) to 5 (super hard)...
This probably will be similarly subjective as difficulty itself is quite a personal thing - what is 2-3 for you
probably is 5 to me and 25 for someone else :)
But as a separate feature surely we can try adding this, perhaps showing not average but histogram of votes :o
I have found the discussion of problem difficulty levels very interesting. It is certainly going to be problematic to devise any system that gives a reliable indication of difficulty. Some of the suggestions which have been made could provide an additional item of interest for users, allowing them to see how others regarded the difficulty of a particular problem. However, if the main aim is to have some more accurate indication of difficulty then I would argue that this information is already present. The number of solvers for a problem is clearly a measure of the difficulty. Clearly it takes some time for a problem to accumulate solvers but it doesn't take very long to see where a new problem is beginning to settle.
I suspect that the interest in a difficulty level is most relevant for the hard problems. These are never going to attract a large number of solutions like many of the early Code Abbey problems. For the hard problems the sort on number of solvers provides the information required, although some attention needs to be given to very recent problems. One aspect of this sort that should probably be changed is the order in which problems are displayed when they have exactly the same number of solvers. If two problems have the same number of solvers then it seems reasonable to say that the older problem is the harder of the two. This should be reflected in the sort by number of solvers routine, by reversing the order of a group of problems having the same number of solutions.
I think the sort by number of solvers routine is particularly effective when the number of solvers is small; say 10 or fewer. Some users will be attracted towards these difficult problems, to give themselves an additional challenge. The problems are then very easily selected from the sort by number of solvers routine.
Clive, thank you - it seems I share the feeling that "number of solvers" is a measure of difficulty - even though intuitively.
I'm not quite sure but probably what you describe is at least partly implemented. There is a sorting mode Trending
above the task list (I hope it is default). I tried to recollect how the order is defined and found
this code. It uses language standard sorting
function with comparison callback. Inside the callback, as I see, we create two "weights" for tasks A and B,
and they are defined as
weight = (total_tasks + 1 - this_task_id) / (this_task_solvers + 1)
So this weight (difficulty) increases with the task "growing older" and decreases with the number of solvers.
I see now for example problems 240 and 236 have 8 solutions and the latter is "latter" in the list just becaus
its id is smaller, according to this formula. The same with 251, 248 (9 solutions) and 226, 224 (11
solutions).
Please direct me if I missed some point.
As a sidenote I'm not quite happy with the formula. Perhaps it should better use the age (e.g. days) of problem's existence. Though problems historically do not have creation date stored, we can recreate this retroactively, e.g. by the date of the earliest solution. Another point - I'm not sure linearity here is a good idea. Perhaps numebr of solvers should be logarithmic or square root. So any suggestions from colleagues who are more strong in math and statistics :)
Rodion,
The Trending sort is clearly intended to encourage users to try the more recent problems, while still being a rough measure of difficulty. I think it does its intended job well. However, I still think that the number of solvers sort is a better measure of difficulty. I agree that the trending sort does order problems with the same number of solutions correctly. It would be fairly simple to do this for the number of solvers sort as well. I would be inclined to leave the trending sort as it is. There is no perfect way of addressing this issue, although the modification to the number of solvers sort would be good.
However, I still think that the number of solvers sort is a better measure of difficulty
Here I feel a bit confused :) I thought that you describe something what "trending" order does, but seemingly I was wrong. You mean the older "Sort by number of solvers" itself and suggest only modify it to resolve "ties", right?
I now switched to it and really see there are many "groups" with equal numbers. Aha!
Here I switched to see where this sorting is, and found it is so old that was built-in in dedicated sql "view"
... select * from tasks order by solved desc, id asc
If I understand right, all we need is to change the last asc to desc, right? I tried this change now - looks like
this sort mode has now "groups reversed".
Thanks for your patience with my slowpoke-ness :)
Thanks for making the change. I think that the sort by number of solvers now makes more sense. Both this sort and the trending sort are useful for slightly different purposes.