Wrong Problem in the Contest 'Coding Hours'

In the contest COHR2018, the problem ‘Chef And His Algorithm’ is probably wrong.

The problem asks us to compute the minimum length of a string which consists of all the permutations of the given string, if the latter has all unique characters. This problem is the same as the Minimal Superpermutation Problem, and it stands unsolved for n > 5 as of now.

The answer to the problem was conjectured to be the following value by D. Ashlock and J. Tillotson:

\sum_{i = 1}^n i!

The conjecture has been verified for n \leqslant 5, but it was later proven wrong for n \geqslant 6. The value of the above sum for n = 6 is 873, but Robin Houston provided a counterexample, which was a superpermutation of length 872, one less than the conjectured length, to disprove the conjecture. This paper explains the problem and the conjecture, and proof that the conjecture is wrong, in detail.

Quoting from the paper:

The minimal length is still unknown for n ≥ 6, but we can show that for all n ≥ 6 it is strictly less than the conjectured length \sum_{i = 1}^n i!

In the contest, what people have done for this problem is, they have printed the conjectured length for n \leqslant 5, and one less than the conjectured length for n > 5. However, “strictly less than” the conjectured length does not mean one less than the conjectured length.

So I request @admin to do something about it. Probably remove the problem and its submissions from CodeChef, if possible.

1 Like

Exactly what I wanted to say finally someone else did xD

2 Likes

Hi, thanks for reporting this. We are looking into it.

1 Like

@admin @vijju123 Is there any progress on this issue?

Asking @admin.

@vijju123 So what did the @admin say?

Sorry for the delay. We have contacted the organizer and found that their intended solution is wrong. The problem has been removed from the Practice section. Apologies for the error.

1 Like

Okay, thanks!