Petr's blog

A week with SSE
By Petr, history, 9 years ago, In English

http://petr-mitrichev.blogspot.com/2015/08/topcoder-srm-666-happened-very-early-on.html

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

»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

"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.

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

    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.

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

      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.

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

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

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

          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 :).

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

          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.

          → Reply