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
Disclaimer: This is just my opinionThese are just my personal thoughts on what role a Div2A should play in a contest, based on what I've seen from my own contests and the opinions of my classmates who are newer to Codeforces. Of course, I'm only 1600-rated and haven't written a contest for the larger Codeforces userbase, so my opinion will likely differ from a seasoned GM organizer for Div2s and Div1s. Plus, higher-rated participants probably view A and B problems as less and less interesting, regardless of "quality", due to the (intended) easy difficulty. If you disagree with any of the points I make or have a second opinion, please share them down below!
Disclaimer 2: Educational Rounds are weirdMost of the points I make don't apply to Educational Round Div2As, since those are specifically tailored to teach concepts important to competitive programming.
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:
Since a Div2A is the barrier to entry for Codeforces, it follows that it shouldn't be unnecessarily high as to drive off first-time competitors.Superficially, this just means writing a simple problem, but I also believe that Div2As shouldn't test any algorithmic knowledge beyond what is learned in the standard first-year CS course. (I particularly dislike Div2As that involve XOR or any modular arithmetic beyond simple remainder definitions.)
There's a lot of discussion to be had on the benefits of so-called 'implementation slop' problems. Regardless of your stance, the one place an implementation-heavy problem should NOT be is the first problem in a problemset; its not fun for first-time participants and portrays a distorted picture of competitive programming as having an emphasis on raw programming translation, and it kills momentum for higher-rated participants who just want to get a move on.Regarding the latter point, since Div2As are solved by almost all high-rated participants in a contest (unless your name is rainboy), a Div2A should aim to be "fast" to solve for those who recognize the solution and serve as a momentum and morale booster for the rest of the contest. As silly as it sounds, I believe AC dopamine is a real factor that should be considered by problemsetters — participants undeniably feel much better about a round if they kick things off with a quick 1 minute A solve rather than a tedious "1 minute mental solution + 5 minute coding phase" solve.
A Div2A should aim to be as 'Russian' as possible.As the linked blog post eloquently describes: "Observation means that you stare at some problem for a sufficient amount of time and you are able to reduce it to some easier problem... Despite being rated 3000, the problem is solvable in 30 lines of trivial code." Of course, the above quote describes a much more difficult problem, but the underlying principle applies just as much to Div2As. A good Div2A should require an interesting observation or reduction by the participant, which reduces the problem to a trivial implementation. Note, for example, the highly-regarded 1339A - Filling Diamonds (if you haven't solved it yet — solve it now! It's a Div2A, after all, what are you waiting for?). This problem may appear to be a challenging geometric reasoning task at first — but trace some examples by hand or reason it out mentally, and the clever solution reveals itself as a simple print(input()). I think this is an example of a very good Div2A, and the fact that some people still remember an A problem from a several-year-old contest should speak to its effectiveness.
- Avoid "Brute Force" as main solutions:
Going hand-in-hand with the previous point, the key observation to a Div2A should ideally reduce the problem to something more satisfying than just a simple brute force with bounds.After all, as with the problem I mentioned at the start of this section, a brute force solution doesn't feel satisfying when it feels like a newbie could have accidentally stumbled on the solution with the simple formula of "if I don't find the answer within the first thousand numbers, it probably doesn't exist." Div2As should be easy, but they shouldn't be free and should involve a bit more thinking on the user's part than a simple "brute force for the first N cases." Of course, this doesn't mean that a brute force should be disallowed; I particularly like problems that involve observations with small constraints, such as 2155A - El fucho, giving the user a sort of "choose your own adventure" solution; try to find the observation that reduces the problem into a trivial implementation, or implement a brute force that will take longer to code but will guarantee the correct answer. (This achieves the dual purpose of avoiding a "roadblock" on a Div2A; if you can't find the observation, you don't have to be frustrated throwing yourself at a wall and instead choose to code the slower but correct brute force to move on.)
- Sample Tests Shouldn't Mislead:
This is probably the most controversial point here (refer to the dozens of 'WA on Pretest 2 is bad' blogs). Yet, just as with the above point on implementation, I don't think that a Div2A is a good place to put such problems.Nothing feels worse than a WA that you don't know how to fix — again, an arguably important skill, but a huge morale killer for participants all around. As a contest organizer, I aim to make contests that not only accurately place people based on skill, but also leaves the majority participants feeling satisfied and wanting to participate again, even if they got a bad placement. (In marketing terms — user retention is important!) A Div2A that has the potential to mislead a substantial portion of participants into implementing an incorrect solution is an excellent way to fail that goal.
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.