I got something like 0.05 points. I am curious for what innovative algorithms you all used to solve that problem to get above 0.05 points.
In the contest my approach was as follows:
Create a class containing each string together with its index in the original array.
Build an array of instances of this class.
For each possible character position in the string
-
Sort the array based on this character position. If any string is too short to have a character in this position, put it at the start of the sorted array.
-
Identify the first string with enough characters, by binary search.
-
Output the indexes from the array. Work forwards when the position is even,
and backwards when the position is odd, so that the sequence of digits
is 0 0 … 0 1 1 … 1 … 8 8 … 8 9 9 . 9 8 … 8 … 1 1 … 1 0 0 …
etc.
Towards the end there may be a few gaps, but with such a large number
of strings there are not likely to be many.
This solution earned me about 70 points.
You can find this solution at https://www.codechef.com/viewsolution/23511542
Since then I have thought of a better approach, which I have implemented.
Start with the same array, sorted by the first digit. With each string store the next digit to be used.
Make 10 queues, each one an array for its digit, containing the strings which are able to be added next.
In the first pass, as we add the first digit to the output, we check the next digit.
If it is the same, we add it to the output as well. If it is a different digit, we add it to the corresponding queue.
After adding each index from the original sorted array, we add more from the corresponding queue.
We want to avoid any gaps, for example going straight from 2s to 5s, to reduce the cost. On finding a gap, look back to find a string which ends with the missing digit and has already been added to the output.
If this is in a run of at least two of the same digit, we move it from where it was to the current position in the output before continuing.
Housekeeping of previous runs of consecutive digits enable these to be found with little searching.
We then move up and down the queues in alternating directions, until we have used all the strings.
Because there may be more 0s and 1s than other digits, a refinement is to start with 1s, go back to 0s, and then work forward and backward alternately.
When I submit this in practice I get 0 points, but then I don’t know how challenge problems are scored in practice submissions.
My own tests with random data show that this method produces sequences with smaller cost than the method I submitted previously,
typically a cost of 685 instead of 903.
You can find this solution at https://www.codechef.com/viewsolution/23602577