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:
- 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.
- 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).
- 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"?
I also want to point out many math concepts you see that are simple to describe and code (think pigeonhole, gcd, basic combo formulas, etc.), are only able to be used in beginner problems because experienced setters have seen them so many times they think it's accessible.
Yet, such ideas are not inherently any more beginner friendly to someone just starting cp than many algorithms you see in an intro CS class (except maybe being a few less lines to code). We just slowly sway the community to only adjust to seeing some types of ideas more than others, and then say these ideas are easier because more have seen. Why do we want to keep people contained to only seeing boring ideas that don't actually have much programming?
In a probably much less held viewpoint, I think the best problem for beginning of round (div2 A/B) is to be focused on trickier implementation, as that is a pre-req to all problems. Doesn't mean it has to be super long or super brain dead, but it should be a small bit of challenge to translate into code.
I think beginner problems are never going to be interesting to better participants, but implementation is the thing that can be considered most accessible and good for preparing for harder problems in a "programming" contest.
While I agree with many of the points from this blog, I disagree with your claim that these "hidden ideas" are not more beginner friendly. The reason for this is that with these "hidden ideas", understanding them at a high level is enough to start using them.
For example, in Missing Subsequence Sum, the key idea was that any number can be decomposed into powers of 2. If you understand this, then you can immediately apply it to solving the problem.
However, for something you would learn in a intro algorithm class, understanding the idea is not always enough to be able to produce the corresponding code and use it in problem-solving. For example, something like Dijkstra, the high level idea is pretty simple, but coding it using a priority queue and pairs is not very easy (for someone new to programming).
Pretty sure half of the people who read the problem saw the powers of 2 thing, but how to apply it wasn't immediately obvious.
Sorry, I think I might have misstated my point. I wasn't trying to say that knowing about powers of 2 would immediately lead to a solution to the problem (it would be a very boring problem if that were the case).
I meant that if you come up with a solution based on this idea, it is very easy to implement it in your code, which I don't think is the case for my other example of Dijkstra.
pigeonhole : you have got to be kidding me, this is not a real principle
gcd : beginner mathematics taught at middle school level i think? also sorta rare on d2A/B (not saying it doesnt occur)
basic combo : what part of combi appears at <= d2C??? Addition and Multiplication principle? (I am ashamed of even knowing their names) Okay, there was a recent d2C on combinatorics but to be fair it had the "easier" dp solution (to me combi was much easier, but i can see why that can be easier to experts) , and it definitely is an exception not the rule. I would hate it too if something like Vandermonde Identity came up in a d2C
formulas : idk what to say about this
It is indeed much more accessible. I have described certain cf problems to a lot of people (yes including non-math enthusiastic people).
Take a look at last contest. I feel positive I can describe the solutions to d2A, d2B, d1A to the average person, and he would understand it. There is no prerequisite to understand them except for basic logical reasoning. You want there to be a prerequisite, thus i disagree. You think there are already prerequisites, can you name a few among the 3 beginner problems?
Putting algorithms as the first tasks will only drive inquisitive but non cs people away from CF. I got interested in CP purely because of how much I enjoyed the tasks (I technically shouldn't have started it but once I did, I simply got addicted). I want to help people like me. I DONT want to help people who have taken intro to algorithms and think thats what should be present in such contests. No, its a test of your problem solving abilities not how well you did your coursework.
It's a "programming" contest (or at least, that's what it used to be). I don't understand why using problems that require basic programming algorithms will drive away someone interested in solving PROGRAMMING puzzles.
Also, from your last statement it seems you're claiming problems that require algorithms usually don't involve alot of problem solving, and it's just reproducing what you already know, which I think is false.
I think you totally miss my point. It is fairly easy to describe most algorithms to people with not much background besides high school education. I think easiness to describe is something like a matter of unique steps it takes to write out, and as clear example something like kruskal's algorithm has very few unique steps of logic, even something like segment tree I'd easily explain to some people who knew minimal math and no algorithm theory when in high school.
However, that does not mean such ideas are easy to come up with yourself right away. I think someone is just as likely to come up with a basic reduction to kruskal's as they are to the idea in the div2 B described below (where you have to come up with dependency on moves, what moves might end up always being dependent, guessing the maximal rectangle is the bottleneck, and showing with invariant). Some will figure out the setup the first time themselves in contest, but majority will not unless they already seen the setup before (even if they don't remember it). However, for an advanced participant both have seen such setups so many times they are equally easy to recognize.
I think basic "programming" is a pre-req to a programming contest. The rest of the topics are what we choose to emphasize. I wish we emphasized topics that required more code and just generally expanded the topics we care about, forcing people to have to think of new things more often (both beginner and advanced).
I used to play good amount of CTFs, I learn there that extrapolation to a known topic but you don't know is a skill in itself, and I think this is what cp should be all about except in what can be written in a single c++ file (and closer to theoretical side). But people on cf think your not allowed to have problems with such skills except a very particular category, pretend it is not a category, and limit themselves to only be able to show and solve problems by repeating ideas of such category.
Problems that, as far as I'm aware, are "actually ad-hoc":
I agree that the "ad-hoc" label is very frequently misused, but that does not mean that such problems don't exist at all.
4fecta Orz
Was the goodbye 2023 problem D ad hoc?
https://codeforces.com/contest/1916/problem/D
Also please show me problems that use the same "hidden techniques" as this one: https://codeforces.com/contest/1966/problem/B
so 1966B is adhoc. atleast that's I think you wanna say. it isn't in my opinion
1966B: the hidden technique is considering invariants: what are properties that the operations can never change? E.g. if an edge of the matrix is same-color, then no operation can ever change the color of any cell on that edge. There are many problems like that.
I can certainly say that the process of solving that problem was almost formulaic for me. "Answer is obviously yes if some corners have opposite colors" -> "What happens if none are" -> "What can never change" -> "Ok, solved".
I see, thanks. I have done a few problems using that technique now that you mention it. Before you did all that, did you think that it was fft?
I would say more specifically why it's formulaic, is that it is "discover invariant through checking if trivializing finish move is needed" combined with "In moves with subgrids, try using move of maximal subgrids possible" (subset of generic trying maximal move possible).
There are many invariant problems and what you need to figure that out can be much more unique in others.
kinda weird solve process (i find it much more intuitive to do when can i make corners have opposite colours, and then get the case when i can't) but I digress.
You make it seem like every problem is formulaic, that is true they are but ONLY AFTER you've solved them. You know there are a series of logical deductions that you can use to solve any solvable problem, finding that series is the problem right?
What you did is actually make several small observations and logical steps to reach to the answer (maybe your brain doesn't recognize them as such because its a d2B). You got the correct logical step immediately again because its a d2B. If you tried a harder problem, you would go down wrong solve paths till you came across the correct one, eventually (well hopefully). Trying solve paths and finding the correct one is the essence of problem solving, is it not? Certainly the solve path itself is formulaic, but you need to observe to actually get the solve path.
His solve process is exact same as mine. Yes there is observations (just the ones he described by arrows), but the observation is my first guess because I solve 50 problems with same boring steps.
Perhaps it is actual step by step puzzle for someone bad (or rigorous?), but for me it is guess stupidest idea that fits similar setups most often then it works (like most times).
This is pretty common for me even on harder problems, except yes sometime my first guess of setup isn't right and I need to combine 2 or 3. Doesn't make it not boring and formulaic, I'm still iterating through common setups I've seen, no different than iterating through what algorithm to use.
(And then the problem I don't solve in contest is usually because I hoped too much it would be more interesting setup, but after contest I give up hope at some point and realize it is also stupid one i've seen).
I've solved many div2 A's and B's but it still took me a while to make the correct observations for this problem. I think that it might not seem like a puzzle to you because you solve harder puzzles all the time. Maybe since you have solved so many hard puzzles, it is difficult for you to see that the easier puzzles are still puzzles.
Like on an IQ test designed for the mentally retarded, the puzzles there would seem super easy and not even puzzle-like. But they are still puzzles, just really easy puzzles. They still measure reasoning ability. Just my take on it.
I would not call D ad-hoc. It is type of trick "brute force small case that works and hope it's extendable by repeating same pattern" which is very common. I think more specifically you even see this idea particularly applied to building up pattern of digits.
I think the reason that particularly feels trollish is the statement gives hopes to more interesting generic insights in number theory, but instead it reduces to such boring reused idea.
I think that the problem would've been much better if the 1 6 9 solution didn't exist. Then the only solution would be to brute force squares until you get 99 of them with the same multiset. Then just keep adding zeros to them to make it work for the bigger values of n. I think that that solution is much cooler than the 1 6 9 solution and cf writers should try to include more problems that involve that sorta practical thinking. It is also very easy to prove so there is no hoping involved. Would you consider that solution generic?
how do you do the said brute force to run in time?
also, no it would have made the problem worse (even though its already quite bad)
Just generate the numbers beforehand and store them in a list or something.
Kinda like Staszek's solution here
I solved the problem in contest using the brute force method and I think the brute force solution is dumb af
Nah bro u smart as hell. I kicked myself when I saw that solution cuz it is so simple but so clever too.
.
yes
I would say there are some ad-hoc problems indeed (lazy to list but not negligible) but I mostly agree to your claims. Sometimes people can't do induction and say how genius this ad-hoc problem blah blah, I've seen this shit too many times. If they can't do induction they should prly go study DP first.
On point 2 I'm not sure, I think those "adhoc" problems are fine, but then why ds problems are not fine if they do? Probably because in ds problem those techniques are important and you should actually care, whereas "adhoc" problem they are kinda shit and nobody have to care. A weird sort of underdogma, but I can see why someone would want to shape contest that way... kind of?
(disclaimer: this is not related to today's contest and in fact I didn't read anything except F today)
Yes, a lot of tricks will turn problems easier, and that will allow you to get more time for harder problems, but if you can't simply know every trick that will be om every problem. Strong contestants will know a lot of tricks but theyll figure out the ones they don't know. It is super common for two people to solve a problem while one of them says that it was an application of an idea for another problem and the other one just came up with that idea on the spot.
The difference isnt that the low level participants are "bad at logic", they're bad at the logic that regularly appears in programming competitions. As you do more problems you learn which things to look out for and become accostumed to making arguments that result in fast algorithms. I don't think that is "learning hidden prerequisites", thats getting better.
I think of knowledge as various sets and subsets of ideas in specificity. I believe all ideas in cp can be figured out oneself with a small set of generic guidelines that when combined builds up the more specific. So yes, people figure out these and figure out repeating ideas themselves.
However, I still think problems are often going towards one style that fall under a subset of specific kinds of tricks, which just makes it boring they end the same way (regardless if that makes it easier to solve), and think it's dumb people then praise some unique nature of insights. And then I think some others actually seen the specific idea 20 times but can't pinpoint a name so they believe they come up with it from fundamentals, yet it's still ingrained in their mind from practice.
It's hard to come up with a problem that is 100% original, ofc there will be things that will repeat between problems. The point of adhoc is that it is reasonable to come up with what you need in contest if you have enough skill, not that seeing a similar problem beforehand won't help.
For example, I don't see how this problem fits your philosophy for example: https://codeforces.com/problemset/problem/1817/D . I've shown it to an IPhO silver who barely did cp and he eventually solved it. You can't tell me it's because he seen a lot of those before, lol.
From personal experience, the people who are better adhoc arent the ones that know all the "hidden tricks", those tend to be people who are good at stuff like ds and try to apply the same logic to adhoc (which can work to some extent). They test something inherintly different and different people have different levels of affinity to it.
fr they're just IQ tests