As a problemsetter, this is a question that I've been thinking about for a very long time — writing high-quality and challenging tasks for a contest's problemset is a valuable and much-discussed skill, but barely anyone ever talks about or even remembers the first two problems of a contest (barring Div1s, which this blog post largely doesn't apply to). This is a great shame in my eyes; Div2As always boast the highest solve counts in virtually every Div2 round, and are accessible to the widest audience of Codeforces users, but are almost never discussed in the comments section of the contest blog post or editorial.
Is this simply because such tasks are considered trivial in the eyes of most Codeforces users (at least, those rated above 1200) and therefore not worth discussing? Perhaps, but there are usually about two to four thousand people per contest who solve the Div2A and Div2B but fail to solve anything beyond that, meaning that for these people the A problem forms the majority of the contest experience — I think this is a substantial enough audience to warrant a discussion about what actually makes these so-called "easy" problems "good" versus "mediocre."
TLDR Div2As are barely ever talked about and I think they should be discussed more, which is what this blog post is for.
My Take
The recent 2197A - Friendly Numbers is largely what motivated me to make this post. As an unofficial participant, I spent several minutes looking at this problem wondering if there was an easy trick with manipulating the sum of digits, before disappointingly realizing that any numbers above roughly $$$x+100$$$ simply could not be friendly, leading to a rather uninvolved brute force check. Sure, this is an easy problem (reflected by the solve count), and the skill of recognizing cutoffs and answer bounds is arguably important, but it also didn't exactly feel very fun or involved to solve. Is that a bad thing? I argue that it is.
In my eyes, a Div2A should satisfy five basic principles:
- Easy:
- Implementation-Light:
- Observation-Heavy: Referring to this blog post:
- Avoid "Brute Force" as main solutions:
- Sample Tests Shouldn't Mislead:
In my opinion, Div2As that follow the majority of the above principles generally get better reception from both new and experienced competitive programmers, and thus should be the standard for the beginning problem of a contest. Of course, that's just my opinion — if you disagree with all of the points and think that Div2As should be more implementation-based, or want to see (or have seen) a high-quality bitwise Div2A in a contest someday, or think that a 1600 rated user can't possibly know what they're talking about (I won't take offense) — please let me know in the comments! I think this is a good opportunity to have a discussion on an otherwise little-discussed aspect of problemsetting.
I think it's absolutely true that the more implementation-light a Div2A is, the better, just wanted to note that IMO extreme cases of Div2A's like 1339A - Filling Diamonds, despite having a really beautiful idea, are too guessable, and that not only gives an unfair advantage to the thoughtless guessing strategy, but would also make a lot of beginners get an AC without really learning anything new. And yes, as a problemsetter, I completely agree that it's easier to come up with a good Div2D-E than a good Div2A-B.
Thanks for the feedback! That Div2A is a really neat idea (which is why I linked it), but it's definitely a trick that only works once (maybe we could see this as a Div4A?). Avoiding making problems that reward "thoughtless guessing" is something I hadn't really thought of before — definitely will keep this in mind for future problems.
i thought it was a very clever question even if it dropped me to pupil
I hadn't thought about it so deeply before, but I agree with you. Personally, the Div2As I enjoy the most are those that I can solve without messy code and that require an observation that allows you to solve them in just a few lines. In addition, getting a WA on test 2 can be kind of frustrating, so having a well-explained Div2A with good samples can really help with motivation at the first stage of the competition (at least for me as a Specialist–Expert coder).
I think this div2A was fairly Russian — noticing an "efficient brute force" is still an important observation. In terms of difficulty I do feel like it's a little on the higher side for an A though.
I also wouldn't really classify this as a brute force. Yes, you do kind of brute force it, but you are smart about it. All solutions are just smarter brute forces, DP is just brute force but you are smart with your recursion and states.
It's definitely an important observation, but at its place in a Div2A it's not a fun observation. As I mentioned, it doesn't feel satisfying to code a solution that simply checks all numbers from $$$0$$$ to $$$C$$$ or $$$x$$$ to $$$x + C$$$ where $$$C$$$ is some very small constant. (Problems where you check all numbers in a range satisfying some special condition that isn't just "continuous range of size $$$C$$$" are a bit better.) Of course, this is just subjective opinion from me, and this depends largely on how much you value "fun" as an important purpose for a Div2A.
I can kind of see what you're getting at now. When you frame it like that, it's definitely not the most fun in terms of a solution.
Then again, that might just be inherent to "easier" problems where the trick is not meant to be insanely hard to find.
Yep, that's what makes writing a good Div2A so difficult (and why I'm surprised there's barely any discussion about it.) Striking a balance between making a fun observation that a newbie can still find in a reasonable timeframe is surprisingly challenging!
Meet the Div2A
this isnt funny dude.
Interesting perspective on A problems.