Блог пользователя Petr

Автор Petr, история, 9 лет назад, По-английски
  • Проголосовать: нравится
  • +57
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

"While both issues could probably be avoided by investing more effort into the round preparation, I think they actually highlight one of the main good aspects of competitive algorithmic programming: it's extremely objective. Every solution is judged against the same testcases, under the same time and memory limits, and completely automatically." — in my opinion that is exactly what makes it subjective. Objectively good solutions definitely should pass all possible testcases. I would definitely want to live in a competitive programming world where problemsetters don't have to worry about how stupid solutions contestants can create and what to do in order not to let them pass. Specific choice of testcases is what makes everything subjective. However I think that I've read somewhere that people on FBHC were given significantly different testcases, some of sets of testcases weren't including some special cases which other testcases covered and that is of course even worse.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    It is objective. It is not a correct solution, since the test cases aren't complete (do not completely cover the domain), but it's not influenced by personal prejudice and so is objective.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -15 Проголосовать: не нравится

      OK, I admit that maybe the use of objective/subjective is somewhat unfortunate here, if we focus on fact that all solutions are graded against same tests and limits then in that meaning it is objective, however one can look from different angle and state "Objectively good solutions definitely should pass all possible testcases." and say that if acceptance depends on a choice of testcases then it is subjective whether solution is correct.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

        So, randomized solutions are bad, because for every seed there are testcases for which that seed doesn't work?

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +4 Проголосовать: не нравится

          Haha, nice catch :). In fact randomized solutions are different topic, what I can add is that if you will Hamilton's cycle problem in linear time using randomization you will not get million dollars :).

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +13 Проголосовать: не нравится

          Sometimes there are no testcases for which chosen seed gives wrong result. E.g. it could happen that probability of mistake is low compared to number of possible inputs.