Plurm's blog

By Plurm, history, 14 months ago, In English

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!

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I haven't really participated in many contests or solved many problems, but I want to offer my two cents.

I started competitive programming because it was fun and interesting. Generally any principle or theorem in math/cs involves some intuitive observation. The most interesting aspect of math to me is how people came up with the intuition for some theorems, and how I could have done it myself. In every single contest, the clock ticks down. I felt the rush of adrenaline pumping my brain with numerous perspectives and ideas to tackle a certain problem. When I see the green status bar for my answer being accepted, I get super excited and pumped. Precisely the reason why I am happy after seeing the green status for my answer being accepted is due to the ingenuity and effort required to come up with a solution. This “intuition” is what makes mathematics and computer science interesting.

My main cp experience stems from my preparation for USACO rather than Codeforces, but lately I have encountered a lot of problems from both USACO and Codeforces that requires a very specific observation. Nowadays practicing CP feels like a chore and not fun. I think it feels like a chore mainly because I spend some time trying to find this one observation that would make the problem solvable or the "insight-based problems. I personally don't have an issue against these "insight-based" problems, but many times I cannot find it, even if I read a bit of the editorial for a hint. Finally, I read the entire editorial and it just kind of spits it out there. There were times before where I was like "Oh so that's how you do it, I will keep that in mind from now on", or "That is pretty cool and interesting". Maybe its because I can understand how I could have came up with the solution. Its similar to your idea of how you build up specific ideas from your initial observations. You might start with O(n^3) then gradually get it to O(n). But nowadays its more like "Oh so this is some random math bs". I can understand it but I cannot come up with it myself, only some genius could find this seemingly random solution. Even if I did come up with it, it sometimes feels like I got it because I am lucky. I can't exactly articulate how I was able to find it. Maybe I am just ranting about editorials not presenting much intuition, or maybe I'm doing problems too hard for my rating, both of which can totally be the case. However, in general it feels like you need some really unintuitive obscure observation to solve some problem, and that feels really uninteresting. I'm more interested in how you come up with that observation and how it can be applied, but problems expect you to come up with this observation and don't do a great job of revealing it if you can't come up with it.

tl;dr i guess what makes a problem good is that the problem is intuitive and you can come up with building blocks to solve it, rather than some random observation that is not very intuitive and seems obscure

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, I fully agree with this. Moreover, for me, I really dislike the problems that require those specific non-intuitive random observations.

    And yes, my (initial) reason for doing competitive programming is the same as yours. But now it's kind of a gym, a weekly exercise session to preserve my muscles from being gradually destroyed.

    I once believed that for all observations, if I practiced hard enough, I'd be able to come up by myself. It turns out that some of them are not the case, I tried but didn't achieve it. This makes me feel stupid and bored here. Well maybe I didn't try hard enough, or I'm intrinsically stupid. Either way, I'm not having fun nowadays :(

»
14 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Lol, I've been saying this. Codeforces problems these days are just notice some small observation or you struggle through out the contest. Someone without any algorithmic skill, and a good math background can make it to top levels these days. I really miss the old days where you actually learn useful techniques from problems, and not observations you may never use again.