Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

On the direction of competitive programming

Правка en3, от Plurm, 2022-12-18 04:34:55

Well, let's suppose this is not a rant but yes. Lately, I was feeling stupid. It feels like I'm becoming more and more stupid due to my performance in contests.

I should try not to blame the contests but rather myself. However, I feel like there are reasons that I'm bad at this. I'm going to explain my views through this piece of text. Personally, as one of the TAs (of national IOI training), I always try to design problems such that they provoke these questions:

  1. What are the observations for this problem?
  2. Is this solution correct?
  3. Can we improve the solution further? (for efficiency in time/memory, for generalizations, etc.)

Now that my role as a contestant for the IOI is done, and I'm wandering around Codeforces, I feel rather dull about this. I argue that for now, many of the Codeforces problems focus on judging whether you can come up with a solution for the problem or not. They are "insight"-based problems. On the other hand, when I train (myself and others) for the IOI, the process is different. I try to find a simple but ineffective solution to a problem first, then try to ask (myself and others) whether it is possible to improve the solution, and then we try to think about observations and come up with improvements.

Let us look at an example from my personal perspective of competitive programming. An example I teach about competitive programming (or in general, algorithms) is the problem of maximum subarray sum. Given an array $$$A$$$ of $$$N$$$ integers (between $$$-10^9$$$ and $$$10^9$$$), what is the maximum possible sum of a subarray? Formally, find $$$\max_{i=1}^N \max_{j=i}^N \sum_{k=i}^j A_k$$$. I start by asking the audience about their initial ideas. Assuming that they are at least familiar with basic programming, they would at least come up with an $$$O(N^3)$$$ algorithm: for each possible subarray, find the sum of the subarray, and then find the maximum over these sums. After that, I try to ask for improvements. If no one comes up with any, I talk about prefix sum (quicksum) and the idea around it. This gives an $$$O(N^2)$$$ algorithm immediately. Then I try to ask further, and if no one comes up, I'd hint "divide and conquer". Then if they still don't get it, I explain the divide and conquer algorithm, which is in $$$O(N \log N)$$$. Then I (still) ask for improvements on $$$O(N \log N)$$$. Normally no one (without any training or education in algorithms) comes up with any improvements. I explain Kadane's $$$O(N)$$$ algorithm, forming a basic idea of "dynamic programming".

(Well yes, to be honest, I may be overconfident about my pedagogic strategy because I think this is a better way of teaching than giving rather boring algorithmic stuff and putting them into the audience's mind. So here it is open for criticism, comments, or suggestions for me to improve)

The point I want to state is that in algorithms (especially in competitive programming), in my opinion, the most important thing is the idea of asking "Can we go further?" and "How can we go further?". Without these questions, I'd be bored by the education of algorithms. Without these, research in computer science wouldn't go further. Without these, there's no point in studying algorithms in the first place. Why bother finding an efficient algorithm when we can use an inefficient algorithm knowing that it terminates in finite time?

Coming back to competitive programming nowadays (since I'm too old for IOI, and I don't have time for ICPC either but might try later), I do it mostly on Codeforces. The "insight"-based problems ask whether I know the solution, and if I know it then I get the points. Otherwise, I don't get any. For me, they just check whether my intuition aligns with the original idea of the problem, which, of course, they bored me out.

I don't really understand the idea behind this "competitive programming" thing nowadays. Why should I even bother answering questions that do not even improve myself? It feels like answering a trick question. I don't get the point of why people are doing competitive programming in this format (in Codeforces) nowadays.

I might be pessimistic, but I conjecture a hypothesis as follows. Lately, as technological growth emerged, everyone seeks to find good collaborators (good in terms of efficiency/intelligence, not in a moral sense) to help with problem-solving and related areas. So people try to come up with a way to test the "cleverness" of programmers. This accidentally matches the nature of competitive programming itself, so the two things get merged together. Competitive programming then evolves, from a sport/hobby for programmers to solve problems and improve themselves, to a test of the intrinsic cleverness of programmers.

This is observed by me, in problems from programming competitions held by companies, as most of them are almost greedy/constructive/insight based, in contrast to my personal direction that problems are based on curiosity to improve things.

Thing is, in my direction, intrinsic cleverness is still an important aspect, but for problems in general, one should be able to always improve oneself indefinitely without being pulled away by their "stupidness". Competitive programming shouldn't require one to be a genius in order to come up with something. Though cleverness is a requirement in some sense, the main focus should rather be based on one's curiosity, diligence, determination, and grit.

Well, in this "nowadays" direction (presuming my hypothesis), it may be good for some people. But for me, if this is true then I'm thinking of quitting competitive programming. I don't want to do competitive programming in order to know that I'm stupid or clever. (Because I already know that I'm stupid so it doesn't give me anything) And if doing computer science or competitive programming requires me to be non-stupid, then I'm more comfortable quitting those and rather focus on some stupid things (but with more curiosity) instead.

To this end, I would want you to ask yourself "What is a good competitive programming problem?" or "What makes a competitive programming problem good?", from your perspective (answers in comments appreciated). I'm also open to criticism and comments on every aspect of my idea (especially whether my hypothesis is false). And here I also have a bonus question because I want to know others' opinions in general: "Why do you do competitive programming?". Thanks for hearing me out and I wish you Merry Christmas and Happy New Year!

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Plurm 2022-12-18 04:34:55 0 (published)
en2 Английский Plurm 2022-12-18 04:34:31 24 Tiny change: 'estions:\n1. What ' -> 'estions:\n\n1. What '
en1 Английский Plurm 2022-12-18 04:30:02 6520 Initial revision (saved to drafts)