Блог пользователя poikniok

Автор poikniok, история, 9 лет назад, По-английски

This is a blog post about possibly creating a new category of “problems” if one were to so call them on Codeforces, with the category being very standard problems requiring one specific data structure or idea. Now before you respond as to why one would want such a useless or simplistic thing, I think there are several useful scenarios. In particular sometimes right now I find myself in a workflow where I would like to try a particular concept, for instance topological sorting, max flow, range minimum queries, union find, or any other algorithms / data structures like that. Right now on Codeforces to do so one has to find a problem that uses such an idea, however of course the problem will have other extraneous ideas / tricks thrown in which one also has to code. And then the other thing is that for some concepts, such as maximum flow and even more advanced topics there are no simple problems that use it, they are all Div1 D and E problems which is quite intimidating.

What I sort of envision is problems where the purpose is clear and simple, for people to practice implementation. For instance problem called Topological Sorting, which would ask a user to sort a graph in topological order, or return if it is not possible. Or a problem called Union Find that would give users two queries, to join two indices, and to check if two indices are connected.

In particular I guess this would be sort of an extension of the Education series, except even more distilled down to basic algorithms, as even the Educational series requires innovative thought, or at least it seems that way to me.

Another aspect of this that I think would be very useful is to check / compete on the speed of implementation. For instance one of the few flow problems that is easy enough for me to understand is 546E - Soldier and Traveling, however it also has tiny limits, so after I implement maxflow I do not have great idea of how fast my version is. Maybe there would also different versions of maxflow problem, with different constraints, and at the highest level of constraints individuals could also compete with each other on fastest implementations, and people like me could check the leaderboards to learn fast implementations of various algorithms.

Now I understand that for this to happen takes a lot of work, and in some sense it is useless to suggest that other people do something, of course it is always great if other people do things. However I do not recall recently this sort of idea being suggested recently in any blogs, and I wonder if there are other people in the Codeforces community who feel the same way that I do.

I also understand if the Codeforces administration does not want to go in this direction, as it does sort of involve a simplification of the goal of competitive programming, and there is an argument to be made that there are maybe other sites that are better for something like this and so on. However I feel that this is in some ways just an extension of the Educational series of rounds to sort of appeal to maybe newer and less experienced people like me. And also Codeforces has great ranking system and a lot of great competitors that other sites do not. And so if I were looking at implementations of a certain algorithm for a problem, and it is done by somebody who is red I know that they have a lot of experience and probably any implementation choices they make have very good reasoning behind them.

Anyway I suppose there is not much point to this blog, but would be interested to hear if any people have opinions on this, or maybe I missed it and this topic has already been discussed and thought out. Thanks ☺

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

While I really like Educational Rounds, and think it's a great work off the CodeForces team, I personally do not see that much of a difference between them and regular rated rounds, maybe C-D are easier than usual for Educational, but if someone puts up an Educational as a rated round, I don't think many will notice.

Most of "repeated" problems are usually E-F. ( Sum of Remainders for example ), which most div 2 coders ( primary aim of the rounds ? ) won't have seen before.

IMO, it would be really great if we can start seeing classical problems appear. ( Basic RMQ, Maxflow, Popular but "classic" DP optimizations,etc)

N.B. I'm not saying Educational rounds are bad, they are really great, it's an improvement IMO.