brezhart's blog

Samples ruined a great task
By brezhart, history, 3 years ago, In English

I feel really disappointed after todays Codeforces Round 741 (Div. 2) because of very strong samples in 1562D1 - Двести двадцать один (простая версия).

  • the fact that answer is always <= 2 is not so obvious, but samples made it clear.

  • samples also made it clear that answer is depends on parity of the sign-variable sum

I know a lot of people (including myself) who did not prove it at all. I think problem solving is not about just getting Accepted by staring at samples, but analysing problem and come up with ideas. I spent more time analysing problem A and I don't think it is right

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

Comments Comments (18)
| Write comment?
»
3 years ago, # |
  Vote: I like it +84 Vote: I do not like it

Round coordinated by antontrygubO_o -> guaranteed guessable problems where you can AC without proving.

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

Woah same rating!

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

There was the next problem — D2, where contestants were supposed to prove their solutions, isn't it? Moreover, the contestants could have analyzed some random tests on paper and still come up with the guess. I'm not quite sure why you think that the task was ruined, to be honest.

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

    Moreover, the contestants could have analyzed some random tests on paper and still come up with the guess.

    Is this supposed to make a problem interesting? Checking small tests until you find a pattern and then YOLO submit it with no understanding as to why it works?

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

      No, it is not supposed to make a problem interesting. That sentence was about pretty much the opposite. The OP was saying that the samples ruined the task, and I was arguing that if the samples weren't that good, contestants would have needed to check a couple of tests by hand, but the majority of them still would have come up with the solution. The author of the round just wanted to be nice and decided to actually provide good samples.

      Whether such "guessing" problems are good for Codeforces rounds is a separate topic and I'm not going to dig into this deeply. All I want to say is that there actually was the next problem which was about proving the guess, so in my opinion, in this case it was more than acceptable.

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

        I was arguing that if the samples weren't that good, contestants would have needed to check a couple of tests by hand, but the majority of them still would have come up with the solution.

        I am almost certain I would not have gotten the problem if it weren't for the samples. Literally just went "woah there are lots of 0, 1, 2 and nothing else", submitted the solution and stared open-mouthed at the screen when it passed pretests.

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

          Yeah, such situation is definitely possible. But let's try to have a thought experiment: the samples say nothing about the solution, you have no idea how to solve the problem. Wouldn't you at least try to check some small examples to notice something interesting?

          I'm actually really curious about though processes of others. I am and always was quite bad at mathematics and coming up with creative solutions. The first and the most natural thing for me when I don't know how to solve the problem is to check some small tests on paper.

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

            I usually don’t try small tests.

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

              Orz guess you can AC all problems simply by reading it

              In all seriousness you should try next time, it is particularly useful if the input is a single number i.e. math problem (then just throw it into oeis)

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

          For me it was the other way round. I was thinking about the task and at some point i went like "Hey, this suspiciously looks, as if the answer can only be 0, 1 or 2." Only then I checked the samples, noticed them also having only 0, 1 or 2 as answers and went for it.

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

            For me too... I was analyzing what will happen if when a rod in the middle is deleted and then it suddenly occurred to me that answer cannot exceed 2..... And the samples sort of confirmed my suspicion.

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

    It is possible to solve D2 without proving the solution by just writing out the equation that should hold for the number which makes the sum zero when deleted. My accepted code: 127101270

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

      Isn't at this point it pretty much obvious why this solution works?

      UPD. I think that I understand what you mean. Instead of waving hands and saying "blah-blah discrete continuity" we can say, "hey, I know from the previous problem that the result should be 1 for odd-length segments, so there must exist an element which satisfies something". I wasn't aware of that solution, thanks!

      Still, for me it looks like that at this point it's already quite easy to notice why the solution works or at least have some intuition why such element should exist.

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

D1 alone have less value than A+B. It was made to be easy, because D2 is more challenging.

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

I've made this on purpose to make the task easier.

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

I was thinking the same after the contest. During the contest I just skipped D1 and tried to solve D2 directly, I manage to have the right idea for D1 somewhat fast just trying solving D2 and when I was about to submit I just realize that the sample were so stupid. Also, I don't like the way question C was written guaranteeing the existence of a solution, it just gives you the case where you just have a string of 1s.

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

A good sample will let almost every solution (right or wrong) pass. Real tests are the hiding snipers.

→ Reply