4 ms·
The ACM contest has it right: specify the size of the input and the running time available. The program must be able to run an input up to that size in the giv
by DarkShikari 16y ago
The ACM contest has it right: specify the size of the input and the running time available. The program must be able to run an input up to that size in the given runtime. That's it: no more, no less.
At Harvey Mudd College, we have a class based on the ACM which works similarly, though with relaxed runtime constraints: 42 minutes per problem. In practice, you rarely need more than a few seconds, but the 42 minute cutoff (combined with large problem sizes) is a great way to prevent people from using brute-force approaches when there's a smarter option available.
- JoachimSchipper 16y ago42 minutes? I recall more than one ACM problem that could be bruteforced just within the running time (in C). Actually, I did really badly in one contest because I applied serious mathematics to one such problem (which gave a much faster program, but writing it took a lot of time and fast enough is fast enough.)
- DarkShikari 16y agoSure, some can be bruteforced, but typically it's intentional. A good example of what I mentioned was an assignment this week. Last week, the input size was constrained to a thousand or so, and Floyd-Warshall was able to solve the problem. This week, it's the same problem, but with inputs up to ~50,000 in size. The old program, run on the new test cases, doesn't finish in a day.