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

Автор Namnamseo, история, 8 лет назад, По-английски

Everyday, problems (for competitive programming) are made — and so are the datas.

I've seen tons of problems involvig a graph, directed or undirected, cyclic or acyclic, weighted or unweighted, dense or sparse, random or having some special requirements (i.e. perfect, cactus, scorpion, etc.). And preparing testcases for such problems inevitably involve building such graph. Also, there are so many problems involving trees, strings, arrays, and points on 2D or 3D space.

I learned a few tricks for making such datas, including making a connected graph by first building its spanning tree, putting a few special trees(all points lying on a line, 'sea urchin' trees, sqrt(N) vertices having sqrt(N) neighbors) to cut out some suboptimal solutions, and such. (Put it the other way, take a look at APIO 2013, the third task.)

But somehow, it feels tedious to code the same things every time(yes, I'm being lazy here), and I believe there are many ideas we can share to make the testcases better (and harder). I googled a little bit, but it seems there aren't one that's well-maintained.

I think it'd be good to have one that:

  • can be run directly as a tool, or can be used as a library;
  • provides templates for common structures and constraints;
  • its outputs should be easily formattable;
  • custom constraints can be easily added;
  • is open-source and well-maintained

Is there any?

  • Проголосовать: нравится
  • +53
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I found SPOJ Toolkit's Test Case Generator and fushar/tcframe; But they don't really look like what I expected... any suggestions?