You are not logged in. Please login at to post your questions!


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.

asked 06 Aug, 19:56

the_extractor's gravatar image

accept rate: 8%

edited 06 Aug, 20:24


Exactly what I wanted to say finally someone else did xD

(06 Aug, 20:04) eobardthawne4★

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

(10 Aug, 18:25) admin ♦♦0★

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

(20 Aug, 17:03) the_extractor4★

Asking @admin.

(20 Aug, 17:48) vijju123 ♦♦5★

@vijju123 So what did the @admin say?

(22 Aug, 19:06) the_extractor4★

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.


answered 22 Aug, 19:07

admin's gravatar image

0★admin ♦♦
accept rate: 35%

Okay, thanks!

(22 Aug, 19:13) the_extractor4★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 06 Aug, 19:56

question was seen: 425 times

last updated: 22 Aug, 19:06