KemoCode's blog

Question for problemsetters regarding number of test cases in input.
By KemoCode, history, 4 years ago, In English

I've seen a lot of problems where the input does not take into account a variable t for a number of test cases per code execution and I would like to ask why? For example today's E1 in Round 726 Div 2, why does it not for example include a t variable with the added constraint of "It is guaranteed that the sum of n,k over all test cases does not exceed 5000" or something like that? It seems like there is no advantage to not including test cases and that it only leads to weaker pre-tests.

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by KemoCode (previous revision, new revision, compare).

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

Because you can make as many tests as you want. Also lets say someone has an O(1) solution that work with any input, meaning if lets say both a string of 100 chars and 5000 chars take 1.99 seconds to complete. That solves that problem following those constraints. So lets say we now has 2 test cases with a string of length 2, now that solution to the problem doesn't work and would require something completely different.

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

    "Making as many tests as you want" is the exact opposite of the point of pre-tests, otherwise why even have pre-tests and system tests instead of just putting all the tests in pre-tests? The purpose of pre-tests are to evaluate your code as accurately and quickly as possible. Sure the authors could put more pre-tests but that means testing each submission would take more time and thus slow down the queue more.

    You only stand to benefit from including test cases in your input(As it allows you to merge what would have otherwise been several pre-tests into one or two singular pre-tests).

    Also as far as the counter example you provided for the O(1) solution that would be true if the problem could be solved in O(1). That isn't the case. Infact the counter example you provided isn't the case for at least 90% of problems(including today's E) so I disagree with that rebuttal.

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

      O(1) was an example. It could be a slow O(n) that takes a minimum amount of time and then increases in a linear fashion. Example: 0.5 sec minimum of some calculation O(1) and the actual O(n) solution. I just gave an example

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

        Ah, I get your point now. I've personally never seen a solution that takes that much constant time(and maybe a solution that takes that much constant time shouldn't even AC but I guess it technically still solves the problem so idk) so I still think that most problems and submissions/solutions would benefit from having several test cases in the input.

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

Mostly for convenience — it leads to a somewhat simpler input and output format and also provides some convenience for implementation (as well as a bit in preparation). There are probably even more convenience gains when you write your code in a way that you would need to reset a bunch of arrays after/before each case.

In cases like today's E1/E2, most likely the writers didn't consider having tests in a way that would require multitest, i. e. they didn't see the need for or possibly even think of having an extremely large amount of small tests. In hindsight this was a mistake, as the hack was small (ddcd in the case of E2) and could have been caught by for example having all possible inputs of length at most $$$4$$$ (or something like that) as a single test under multitest.

→ Reply