DWITE 2009-2010 Round 1, Problem 2

[bbi5291]

In my opinion, this is not a good problem to put on a contest, because it can be trivial if one's language has a built-in function to generate permutations, as does C++. Look, for example, at my code - solving this problem required essentially no thinking. But if you use a language like Pascal (look at Delay(-1)'s code, for example) then you have to use recursion or something like that.

[Zampano]

I noticed your solution myself. On the other hand, my panicked solution is way too much for such a simple problem (recursion).
STL and its equivalent libraries do seem to slant the field toward the languages they reside in.

[chili5]

Actually I think it is a good question for a contest. If you are using C++ and you know about next_permutation than that is good for you.

If your language doesn't include a feature then that is your loss. Is it unfair to have a big int question since Java has the BigInteger class? No. Part of the contests is knowing your language and something in your language can solve the problem for you, then do it.

[A.J]

Practically everyone who used C++ included next_permutation in their solution.

[bbi5291]

chili5 @ Thu Oct 22, 2009 5:32 pm wrote:

Is it unfair to have a big int question since Java has the BigInteger class? No.

There is a reason why algorithm contests of great reputation, like the IOI, either disallow Java or avoid asking questions that require big numbers.

I will not pretend that languages don't have their various advantages or disadvantages in these contests. For example, there have been problems on USACO that require data structures that have similar functionality to C++'s "set" and "map". Pascal users have to implement these themselves. But there are times when this is acceptable and times when this is not.

Here's an example of when it is OK to require big numbers: this problem from SPOJ. The big numbers are the "easy" part, even in a language with no built-in support for them; the DP is the hard part. Nobody who is good enough to solve the DP part will be impeded by the need to code big numbers himself (contrapositively, nobody who is impeded by the need to code big numbers has a chance of solving the hard part); that is to say that the problem is sufficiently difficult that language differences are relatively unimportant, or, equivalently, that no language has a feature that makes the problem trivial.

This stands in contrast to a problem like Q2. If your language has a function to generate permutations, then the problem is trivial. Otherwise, it is not.