Plurm's blog

By Plurm, history, 10 months ago, In English

Hello!!!

I'm very happy to announce that, with the permission by the Scientific Sub-Committee of TOI19@NU, an unofficial mirror for the TOI will be hosted this May/27/2023 11:05 (Moscow time) and May/28/2023 11:05 (Moscow time), accessible at The Unofficial Mirror Contest of 19th Thailand Olympiad in Informatics Day 1 and The Unofficial Mirror Contest of 19th Thailand Olympiad in Informatics Day 2, respectively.

The tasks will be given in Thai and English. The scoring rule will be the IOI-style scoring (i.e., with subtasks in each of the problems). In each of the contests, you will be given 3 tasks and 4 hours to solve them.

Note that the problems will probably be easier than the IOI, as the contest is intended as a regional selection rather than a national selection.

Finally, I would like to thank the Scientific Sub-Committee of TOI 19 for the permission to reuse the problems and test data here, and also thank MikeMirzayanov for Codeforces and Polygon. A feedback form will be provided after the end of the contests.

I hope to see you all soon and thank you for joining the mirror contest!

Update 1: To be clear: For the official contestants (and anyone who knows the tasks already), please don't participate in this contest directly. You can upsolve the problems after the contest.

Update 2: The English statements (translated) are given as default, in the normal HTML format. To access the Thai statements, one should download the attachments given in the contest (in PDF).

Update 3: It is reported that the feedback was incomplete. This will be fixed in the second day, sorry for the issue.

Also, I'd like to give an extra acknowledgement here: I thank M-W and TangentOfA for the translation of the tasks and general help on the contest organization.

Update 3': For some reasons this isn't updating, so I need to edit it again.

Full text and comments »

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

By Plurm, history, 15 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!

Full text and comments »

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

By Plurm, history, 2 years ago, In English

Codeforces is a very nice platform, but why isn't it open-source? I mean, I think it would be better for us to develop and extend the benefits if we have it open-source. What do you think?

Full text and comments »

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