Ad-Hoc is Not Real

Правка en1, от SuperJ6, 2024-04-28 00:01:48

This is something I think for a long time now, and some comments today make me explicitly share it.

The phrase "ad-hoc" is vaguely attributed to any problem that does not incorporate a "standard technique", where it's hard to put it in some big category on a problem bank.

However, in competitive programming there are many "standard techniques" that you will not find in a textbook. Some of them are still sometimes stated as "standard", but many are often attributed as "pure logic", yet it is a logic that can only be placed in beginner problems because it appears so often.

Let's take today's 1965B - Missing Subsequence Sum. This is a type of problem I think many beginners will call "ad-hoc", and even some advanced participants will claim as "just logic/trying stuff". Yet, such problem as this boils into two parts: create all of lower sum, create all of higher sum same way, how do you create all of such sum? Any advanced participant has actually come across many problems like this (i wanted to put many but too lazy to find) that are applying essentially same idea, but I do not think they're ideas that you immediately come to with no experience in cs domain. However, it's hard to put a name and a bit more flexible in presentation, so we often just pretend such problems do not fall in a category, even though they clearly do.

If you've done enough problems and think hard enough, you can classify almost every problem as using the same sort of sequence/combination of steps as a dozen others. And then low level participants get this false information that they are just plain not as good at logic, while there are also many hidden prerequisite ideas that make a problem easier.

I wonder, why are "hidden ideas" ok to be reused over and over as long as it's hard to pinpoint a name to them, but any idea that is well named is usually too hard for beginners and too standard for advanced?

What's the point?

I wish there are three things people would do:

  1. It would be great if problems were better classified, and more of these ideas that are standard to experienced participants yet never explicitly written as a technique were named in a huge list with examples.
  2. I wish coordinators would stop gearing problems towards ones that are 1 or 2 shot killed with "hidden ideas". This is just as boring as solving many variations with minimal different thinking of the same data structure or shortest path. Either get rid of all problems that are using same combination of ideas as previous, or allow combinations of known ideas as easier problems but increase the domain knowledge past what can be described to elementary school student (just because it can described in simple terms doesn't mean it's any easier to come up with, it just means it's boring with an illusion of more accessible).
  3. Stop blindly praising problems that don't use higher level domain knowledge but are not an exact replica for being "pure logic of ad-hoc". Almost no problems in contest actually has much new thinking, it is just different rehashes of ideas that are more exclusive to better participants because you won't find them in a textbook.

How does this affect your practice?

Same as I put in my practice blog, don't believe some ideas are impossible pre-reqs you must have read while others are just pure logic you always come up with from scratch. All these ideas are the same, just focus on what is similar and different between problems in practice and what are similar hints toward a mindset across problems you solve.

My Challenges

Can you list some of these "hidden techniques" that you see most often?

Also, can you post a problem that is actually "ad-hoc", ie that others cannot find 20 similar problems before it with the same "hidden ideas"?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский SuperJ6 2024-04-28 00:01:48 3942 Initial revision (published)