antontrygubO_o's blog

Are subtasks evil?
By antontrygubO_o, 5 years ago, In English

Everything in this blog is only my opinion, motivated by the recent round. If you disagree with it, let's discuss in the comments!

It's always hard to prepare a balanced problem set, and when the contest turns out to be unbalanced, an army of angry coders will destroy you in the comments section. But how can setters make Codeforces contests balanced?

Before, authors usually had to spend more time coming up with new problems which would close a too large gap between some $$$2$$$ problems. But now we have an easier solution! Any time there is a big difficulty gap in a contest, add subtasks to it!

View on subtasks by MikeMirzayanov:

Subtasks became really widely used in Codeforces contests recently. I looked at last $$$30$$$ contests rated for Div1 users. In turns out that:

Rounds $$$30 - 21$$$ had only $$$1$$$ subtasks in total,

Rounds $$$20 - 11$$$ had $$$3$$$ subtasks in total,

The last $$$10$$$ rounds already had $$$7$$$ subtasks in total.

Codeforces rounds in the nearest future:

But what can be bad about subtasks if they are making contests so balanced? I have several thoughts.

To begin with, subtasks shouldn't be treated as a panacea. That means, that we can't create a random set of problems with hope to make it balanced by adding several subtasks: they should be treated as a safety bag. As MikeMirzayanov says, In a perfect world, probably, subtasks are not needed

Setter has to really aim to make a balanced round, and after that, if testing shows that there is some very large gap, then maybe try to close it with a subtask. This means that subtasks should be pretty rare in general. However, we see that the number of subtasks in Codeforces contests is growing. Did setters really become worse in making the rounds balanced during the last year? I don't think so, and, to be honest, it feels like the trend now is "Oh it's not balanced, don't bother, just add subtask". The earlier the round is ready the better!

Now the actual complaints about the subtasks on Codeforces:

1. The difficulties are almost always ruined.

Let's look at several examples:

Codeforces Round #602(Div 1). Both problems A and B1 in this round have difficulty $$$500$$$. However, I believe that B1 is easier than A.

Codeforces Round #601(Div 1) Problem B1 is worth $$$500$$$ points, B2 is worth $$$750$$$ points, while the only step that B2 makes with respect to B1 is that you can iterate only through prime divisors, not through all divisors!

And an example that really a lot of people were angry about:

Codeforces Round #584(Div 1), where both E2 and G1 were worth $$$1500$$$ points, which is nonsense.

2. The strategy of solving the easy subtask before trying hard gives more points than just solving hard from scratch too often.

Again, look at Codeforces Round #584(Div 1) with G1 worth $$$1500$$$ and G2 worth $$$2250$$$. Here implementing G1 before even trying G2 is the best strategy.

The same is true about B1 and B2 in Codeforces Round #602(Div 1) (for not too high rated users), about G1 and G2 in Codeforces Round #568(Div 2), and so on.

As pointed out by teja349 here, this would have been okay if the penalty was last submission time, but the decreasing problem value Codeforces system makes the situation with subtasks really sad. Basically, this gives a motivation to solve all easy problems first and doesn't give you nor motivation either time left to work on the harder version.

3. The subtasks should have some weight as problems even on their own, but often they are dead problems.

I will explain what I mean. Consider problem B1 from Codeforces Round #602(Div 1). I am sorry, but there is just nothing good about this problem. It's clear that it was created just for balance, and it's clear that no author with some self-respect would come up with exactly this problem, it's suitable only as a subtask. But as a result, we get a Frankenstein problem.

One more Frankenstein:

E1 from Codeforces Round #577(Div 2) — I really like E2 version, but E1 just makes you code all the possible positions on the board, and I don't think that there exists a person that would find that beautiful.

4. Often, the solution for subtask doesn't have anything in common with the solution of the original problem

Again, refer to problem B1 from Codeforces Round #602(Div 1), E1 from Codeforces Round #577(Div 2).

Just to clarify: I don't think that all problems with subtasks are bad. In particular, I think that F1 and F2 from Codeforces Global Round 4 were fitting perfectly, same about E1 and E2 from Codeforces Round #588(Div 1).

However, I don't feel that subtasks have been really successful in Codeforces (yet). Setting a good subtask doesn't require much less effort than coming up with a new problem, and should be treated with the same amount of responsibility, but it seems that's not true here (yet).

What do you think?

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

»
5 years ago, # |
  Vote: I like it +51 Vote: I do not like it

Subtasks should be disallowed. Trash problems should be disallowed. Coordinators should be more responsible. Problems with binary modular exponentiation should be allowed as D2B. Testers shouldn't be lazy.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +83 Vote: I do not like it

Why is #2 a problem? Isn't it what subtasks are actually supposed to do?

imo, the problem is the opposite case. When you solve the harder version of a problem, the easier version is like a weird free score.

I agree with everything else on this blog. I wish for subtasks problems to be gone from CF contests. They belong in IOI-style contests where the amount of time you spend on a problem doesn't matter since you're given enough time to read every problem and think them through step by step, not in CF contests where time penalty matters so much.

→ Reply
»
5 years ago, # |
  Vote: I like it +75 Vote: I do not like it

If designed correctly, subtasks do more than just smooth the difficulty curve of the problemset: they provide more problems for weaker contestants to work on without forcing stronger ones to spend even more of their contest time rushing through easy problems.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    Right now, the subtasks are completely unrelated and more than 80% of the time the easier one is just heavy implementation and nothing more.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +103 Vote: I do not like it

    The problem is that even when the subtasks designed "correctly", you can never tell whether you're strong enough to solve both or not before you actually attempt the problem.

    So unless you're so good that you can solve pretty much any problems, you just have to guess whether you're strong enough or not then decide which subtasks you're gonna try. And guessing wrongly results in increased time penalty. I really don't like this coin-flippy aspect of subtasks.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The exact same concept of providing more problems for weaker contestants can be done by... providing more problems for weaker contestants.

    If this what the main point of subtasks are for (which I believe it true allowing the round to have a smoother difficulty curve), the contest setters should spend the extra time to come up with one more problem that has the needed difficulty.

    I do realize it is easier said than done to come up with a problem with such difficulty, but it could also improve a decent round with subtasks to a great round without them.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      without forcing stronger ones to spend even more of their contest time rushing through easy problems.

      this is the important part of that comment relating to subtasks specifically

      → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +104 Vote: I do not like it

I second this. From my perspective subtasks increase the amount of tedious and boring codes I am forced to write if I care about taking a good place — kinda the same issue as adding div2 problems in combined rounds. Coding bruteforces is just almost never fun. There are examples where coming up with a bruteforce is an interesting problem on its own (note the difference between interesting and hard), but in 80% it is not and becomes a tedious thing to do. Trying to balance difficulty by forcing us to code straightforward brutes — what about no?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I think you're being a little too harsh, $$$\textbf{some}$$$ subtasks have a meaning in the case of contestants who aren't able to solve the problem on large constraints due to lack of knowledge or being inexperienced in some topic but are able to get the core idea which needs some thinking. but in the case of CF a lot of the subtasks are pure shit.

    → Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I think subtasks give lower-rated participants something to do, rather than giving up on contests an hour early because the first few problems could be solved quickly and the next one is too difficult.

In particular, it's easier to try to think of the leap/trick from a simple subtask to a difficult one, than to approach an entirely new tough problem.

However, I do agree with the points made on odd points allotments.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +61 Vote: I do not like it

    "In particular, it's easier to try to think of the leap/trick from a simple subtask to a difficult one, than to approach an entirely new tough problem." — it's a part of the solving process to be able to come up with a good intermediate problem which will help us solve the original problem by smaller chunks. Nobody should give it right in front of you and moreover require you to code it as well :P.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sure, breaking down a problem is an essential part of the solving process, but a little bit of hand-holding from the setters is much appreciated, especially by less-skilled participants in Div2.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +26 Vote: I do not like it

        Subtasks usually don't help you solve a problem, though. They have reduced constraints, no queries etc., which is something you can think of on your own. They're useful if you can't solve a problem or if you want to verify the correctness of your intermediate solution by submitting.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          Exactly. It's not like IOI tasks where you can see a pattern for building a solution.

          → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it +66 Vote: I do not like it

Subtasks arent bad when a problem has 2 "a-ha"'s (as umnik adores) and you need an a-ha for the first subtask and one more for the second

→ Reply
»
5 years ago, # |
  Vote: I like it +31 Vote: I do not like it

I don't like the fact that the last round had 6 problems and two of them had subtasks. That's 8 in total, what happened with 5? I don't think that the spread of skills within div1 increased that much.

→ Reply
»
5 years ago, # |
  Vote: I like it -25 Vote: I do not like it

Ban all subtasks!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

You should've named the article "Subtasks considered harmful".

P.S. Ban all subtasks!

→ Reply
»
5 years ago, # |
  Vote: I like it +88 Vote: I do not like it

One interesting thing to notice is that for the same set of problem/subtask, today's Div1 B1/B2 (Div2 D1/D2), in div1, the solve counts for the subtask and for the overall problem were approximately the same, while in div2, they were considerably different. This suggests that maybe this subtask was appropriate for div2 but not for div1.

→ Reply
»
5 years ago, # |
  Vote: I like it +60 Vote: I do not like it

In today's Div1 D1/D2, my submission for D1 (65654056) failed pretests but the same code for D2 (65654096) passes pretests. Luckily due to this I was able to fix my bug and resubmit both. However, had I tried the strategy of writing separate solutions for D1 and D2, I would not have caught my bug for D2.

For this reason, I think (pre)tests for the hard subtask should be a superset of the (pre)tests for the easy subtask (and this fact should be mentioned in the problem). In Google Code Jam, I would always build confidence in my large solution by running it on the small data and comparing results with my small solution. In Codeforces, without a quick-and-easy confidence check, I have even less reason to attempt the easy version, especially in such a time-sensitive contest.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    Completely agree. Even more than that, there were numerous occasions when the same solution didn't pass systests for the easy subtask, but did for the harder one.

    → Reply
»
5 years ago, # |
  Vote: I like it +154 Vote: I do not like it

I want to ask the CF community about this. If you have to choose between two contests: "great problems, unbalanced result" and "bad problems, balanced result", what's your choice?

For me it's clearly the former for two reasons. I do contest to solve problems, and rating is a secondary issue. Also, the idea of "in case of tie faster one wins" just makes sense (although CF score system favors speed too much, that's a different issue).

My impression on CF community is usually on the latter side. Comments are flooded with some memes when they had unbalanced scores. However, people rarely blames bad, unoriginal problems. It's not like the community is particularly gentle, because there are rants everywhere. So while I think the subtask system is awful in CF, I think it's what community wants and deserves.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    Most of the users including me are incapable of spotting unoriginal problems simply because they haven't seen enough problems to do so.

    I'm not sure what do you mean by "bad problem". If it means casework problems or trivial idea + tones of implementation problems, I see rants about them pretty much everytime they appear on a round.

    This is a large community. There are bound to be some rants about problem difficulty from those who failed each rounds. I'm not sure this is a CF-specific thing.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      My point is not about "let's start blaming bad problems". I think blaming balances are mostly pointless, just like blaming problems that people don't like. But the community had chosen to do only one of them (likely because it's easier), and now we have this.

      But I don't check all replies in CF rounds, so if you think the community is neutral on that issue — then it's good to know.

      → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    How does "good problems, unbalanced result" even work? If there are significant difficulty gaps (I'm not talking about the last problem being very hard, that's normal), there will be either too many too easy problems or too many too hard problems, and I'm most likely not going to enjoy many problems in either situation.

    My judgement on individual problems is always just part of my judgement on the whole problemset — one great problem and 5x trash spoils that great problem. If the problemset is good, the result will be naturally at least somewhat balanced.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's an independent thing. I don't hate the problem just because it's hard. It's more like an opposite to me.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        I don't hate hard problems because they're hard either. It's just that when there are too many hard problems, there's most likely going to be something that's just hard, not interesting — annoying data structures, annoying geometry, super obscure theory, 20 easy problems squashed into one... it's not a 100% rule, but if you're preparing a nice balanced contest and it ends up very unbalanced, it's because you misjudged the content of the problems somehow, and both "nice" and "balanced" are just part of that, so it's probably not going to still end up very nice.

        → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    I also really like the fact that if #AC(n+1)/#AC(n)>=3 for some n, where #AC(n) is the number of ACs on n-th problem then there are memes about contest being unbalanced. However simple math shows that if we aim at say #AC(1)=1000, #AC(5)=3 then it is always the case for some n xD.

    I of course prefer first option as well. What I don't like however is when contest is visibly too hard even for the best competitors (for example TooDifficult contest on Petrozavodsk Summer 2018) cause hard task are clearly wasted then, but that rarely happens on cf that some task doesn't get deserved attention cause previous ones were too hard.

    However I also understand that you and I are not representative sample of whole cf community and I get disadvantages of too big gaps in difficulty, but anyway I don't think subtasks as they currently are, is a good way to patch this.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +50 Vote: I do not like it

      you and I are not representative sample of whole cf community

      Well, GP of Zhejiang is my top-3 GP in the last OpenCup season, and the scoreboard is one of the reasons for that. It's just lovely. I think it's an ideal ICPC scoreboard. :)

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      TooDifficult contest on Petrozavodsk Summer 2018

      Username checks out

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +70 Vote: I do not like it

I am the author of problems B1 and B2 in Codeforces Round #601 (Div 1), so I will try to play the devil's advocate here.

In my viewpoint, B1 as a problem is much easier than B2, as you don't need the core observation (one step is equivalent to increasing/decreasing the prefix sum) to solve B1. That's one of the reasons why we decided to make B1 worth so little; the other reason is to discourage people from solving B1 first. And I am quite sure it worked: most people who tried to solve B1 first gained zero (even negative) advantage compared to those who didn't. All they got is an insurance that their round would not end up being a disaster just because they missed that one observation to solve B.

So you may ask, why did I prepare subtasks for B in the first place? Well, at first, I also thought that this problem would fit nicely as Div1 B. Our testers didn't really agree with me though:

spoiler

Only one of them solved it in their first submission (the other one is upsolved), which made me question myself. "Was this problem all cute and nice as I thought?". "What if the observation was actually hard to spot (thankfully it was not the case), would contestants enjoy my problem and the contest as a whole as much as I'd love them to?". Now, I won't try to convince you that this is the only method in the world to deal with difficulty spikes in contests. However, in this particular case, having B1 (also E1 in Division 2) as a subtask solved my concern with (subjectively) minimal side effect. I'm quite sure that the idea introduced in B1, while classic, is still new and interesting enough for many contestants here.

As for subtasks in Codeforces in general, I don't think it's necessarily a bad idea. Is it overused? Quite a bit, and I'm sorry for joining the trend. Is it evil? No. Not trying to make your contest as enjoyable as possible is evil. That being said, we can improve the subtasks by:

  • using it only if the potential imbalance may happen in easier problems (in general, having subtasks in Div1 D or E is bad; they are meant to be hard),

  • making the easy version worth as little as possible (but still worth the effort),

  • not spamming it.

As I really want to get involved with creating contests, I'd love to hear appreciate constructive comments on this issue.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    In that problem, I didn't immediately see what to do for B2, so I solved B1 and then went for C. Afterwards, I returned to B2 and immediately saw that I just need to slightly upgrade my solution for B1. It did affect me, but if there was no B1, I'd just solve A->C->B.

    I think this subtask would've been fine for div2 only. It just doesn't give div1 contestants anything useful and the full problem isn't very hard for div1.

    in general, having subtasks in Div1 D or E is bad; they are meant to be hard

    Unless there really is a fairly hard halfway step where a subtask would be useful.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your solution was quite different from ours, I didn't take that case into account, sorry haha :)

      I think this subtask would've been fine for div2 only.

      Good point. I don't think it has ever been done yet, but it's indeed an interesting idea.

      Unless there really is a fairly hard halfway step where a subtask would be useful.

      So far, my take on subtasks in Codeforces, besides it being a great help to manage difficulty span, has always been "a consolation prize to make people who couldn't solve the full problem feel less shitty" rather than "a suggestion to solve the full problem". Maybe it's just preferences, and in certain cases it might help, but for me solving Div1 E is itself an achievement, and I don't want to make it easy for people :)

      Sorry in advance if my wording choice was weird. I'm half asleep right now xD

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, my solution seems like the obvious thing: if the GCD is divisible by $$$p$$$, then we want to group up the first $$$p$$$ units at one point, the next $$$p$$$ units at one point and so on, the rest is just efficient simulation.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +10 Vote: I do not like it

        "I don't think it has ever been done yet"

        1248D1 - The World Is Just a Programming Task (Easy Version)

        1248D2 - The World Is Just a Programming Task (Hard Version)

        1239B - The World Is Just a Programming Task (Hard Version)

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for the info, I'll definitely consider it the next time I set a subtask (if there's any).

          → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it -10 Vote: I do not like it

          Smaller constraints don't count! It has to be something a contestant might not think of to count as a suggestion how to solve a problem.

          → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        "a consolation prize to make people who couldn't solve the full problem feel less shitty"

        Codeforces is not a mine for self-esteem lol

        In fact, usually, the first subtask is brute-force, or something not really smart and done by >= 800 contestant. If second subtask is solved by let's say 200 and I was obliged to solve the first along with the 800-1000 I would feel more shitty than the situation when there would be just the hard subtask and solved by 200. (This is just a personal view, my first point still holds).

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +12 Vote: I do not like it

          Yeah, what you are describing is what I want to avoid as well. What I meant was that I want contestants to try to solve the full problem first, then if they a) cannot come up with anything or b) don't have enough time left, they can switch to the easier one, not the other way around. Maybe this clarifies the "make people feel less shitty" part.

          Again, I'm not saying that this method is perfect, but it has shown from time to time that it can be very efficient if done correctly.

          → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why don't we introduce subtasks only in Div.2? Div.2 has problems AB(C1C2)DE while Div.1 has problems CDEFG.

→ Reply