Newtech66's blog

Generating testcases whose sum of parameters is bounded by a given value
By Newtech66, history, 4 years ago, In English

In newer problems on CodeForces and other sites, I usually see multi-test inputs that say something like "it is guaranteed that sum of $$$n$$$ over all testcases does not exceed XXXXX".

I am unable to figure out how to implement such a generator in Polygon. Can someone tell me how exactly I should go about this?

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

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

1) generate k tests with n = bound / k

2) generate one big test and a lot of small tests

3) generate tests with n = random(1, bound — sum of generated n) until their sum exceeds bound

→ Reply