Проблема алгоритма TopCoder - как добиться прогресса на этом?

Question

Я недавно присоединился к TopCoder и последние несколько дней тренировался в тренировочных залах. Я столкнулся с этой проблемой, которую не могу решить. Любая помощь будет оценена.

Проблема

Значением произведения строки является произведение всех цифр ('0' - '9') в строка. Например, продукт значение «123» равно 1 * 2 * 3 = 6. A Строка называется красочной, если она содержит только цифры и продукт стоимость каждого его непуста смежные подстроки различны.

Например, строка "263" имеет шесть подстроки: «2», «6», «3», «26», «63» и "263". Значения продукта этих подстроки: 2, 6, 3, 2 * 6 = 12, 6 * 3 = 18 и 2 * 6 * 3 = 36 соответственно. Поскольку все шесть продукта значения различны, "263" красочный.

С другой стороны, «236» не красочный, потому что два его подстроки «6» и «23» имеют та же стоимость продукта (6 = 2 * 3).

Возврат к-й (на основе 1) лексикографически маленький цветной строка длиной n. Если есть меньше чем k разноцветных струн длиной n, вместо этого верните пустую строку.

Мой подход

Мы не можем иметь «0» и «1» в качестве цифр в n. Все цифры должны быть разными. Поэтому для начала n должно быть меньше 9. (можно использовать только цифры 2, 3, 4, 5, 6, 7, 8, 9, каждая из которых только один раз).

Поскольку мы знаем это, мы можем начать с «23» (наименьшая двухзначная цветная строка) в качестве базовой строки и добавить одну из разрешенных цифр (проверьте, является ли строка все еще цветной или нет, при каждом добавлении) пока мы не достигнем длины п.

Как только мы достигнем длины n, мы можем «поиграть» с цифрами, чтобы найти k-наименьшее.

Мой вопрос

Я чувствую, что такой подход не будет достаточно быстрым. Даже если и так, каким систематическим образом я должен играть с цифрами, чтобы я начал с самого маленького и пробился через kth-самый маленький?

Как я могу добиться прогресса в этой проблеме с этим подходом? Или есть более разумные способы решения подобных проблем?

Я не прошу никаких решений или чего-либо еще. Я просто прошу несколько подсказок и свинца.

Некоторые проблемы, которые я решаю за считанные секунды, некоторые занимают часы, а некоторые, как это, я не могу это сделать. Но я верю, что все это требует некоторой практики, но я не смогу добиться прогресса без того, чтобы кто-то шел впереди.

Заранее спасибо =)

* кстати, этот вопрос из SRM 464 DIV 2 - 500pt. проблема. Все авторские права принадлежат TopCoder.

Answer 1

У Topcoder есть форум, на котором они создают ветку для каждого SRM (464 - здесь ).Может на ваш вопрос там уже ответили :)

Answer 2

Один из способов уменьшить пространство поиска - рассмотреть это: строка длиной n может быть красочной, только если подстрока, заданная ее первыми n-1 символами, также является красочной. То, что это утверждение верно, должно быть достаточно очевидным.

Предположим, у вас есть функция colorful(n), которая возвращает набор всех цветных строк длиной n. Вы можете реализовать это рекурсивно, например так:

colorful(n):
  if n = 1:
    return { "0", "1", "2", "3", "4", "5", "6", "7", "8", "9" }

  def colorful_subs = colorful(n-1)
  def colorfuls

  for each sub in colorful_subs:
    remaining_digits = { 2, 3, 4, 5, 6, 7, 8, 9 } - digits_in(sub)

    for each digit in remaining_digits:
      if is_colorful(sub, digit):
        colorfuls += (sub + digit)

  return colorfuls

А вспомогательная функция is_colorful может использовать тот факт, что подстрока, заданная в качестве первого аргумента, уже известна как цветная и не содержит добавленной цифры .

Затем вызовите colorful(n) и выберите k -й элемент возвращаемого набора. (обратите внимание, что мы do должны включить «0» и «1» в базовом случае, иначе это даст неправильный ответ для n = 1)

Это в основном подход динамического программирования . Я уверен, что это могло бы быть улучшено - мог бы быть умный способ выяснить, добавит ли определенная цифра к красочному номеру номер больше не красочный, фактически не делая это и проверяя. Но это, безусловно, проверяет значительно меньшее число, чем все возможные перестановки 2-9.

Answer 3

Я чувствую, что такой подход не будет достаточно быстрым.

Почему бы и нет? Я бы даже не потрудился быть «умным» по этому поводу: у вас есть 8 цифр, каждую из которых можно использовать не более одного раза. Это имеет общее количество 8 * 7 + 8 * 7 * 6 + 8 * 7 * 6 * 5 + ... 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 109592, что быстро для компьютер для запуска.

Перечислите все это в лексикографическом порядке, и проверьте каждый из них, чтобы видеть, "красочно" это или нет.

Answer 4

Вот краткий код, который я собрал, показался забавным вопросом ... Надеюсь, я не неправильно понял проблему.

Приветствия

    public class Colorful {


    /**
     * Find the k-th colorful number that has n digits
     * @param n The number of digits
     * @param k The k-th colorful position
     * @return  The colorful number 
     */
    public static String findColorfulNumber(int n, int k) {
        int start=(int) Math.pow(10, n-1);
        int end=(int) Math.pow(10, n);
        Stack<String> colorfulNumbers=new Stack<String>();
        for(int i=start;i<end;i++){
            String currentNumber=i+"";
            if(isColorful(currentNumber)){
                colorfulNumbers.push(currentNumber);
                if(colorfulNumbers.size()==k)
                    break;
            } 
        }

        return colorfulNumbers.size()==k?"":colorfulNumbers.pop();
    }

    /**
     * Checks if a given number is colorful
     * @param number    The number to check
     * @return  Returns <code>true</code> if the number is colorful, <code>false</code> otherwise
     */
    private static boolean isColorful(String number) {
        char[] numberAsArray = number.toCharArray();
        Set<Integer> uniqueProducts=new LinkedHashSet<Integer>();

        return generateUniqueNumbers(numberAsArray,1,uniqueProducts);
    }


    /**
     * Recursive function that checks whether a number is colorful or not
     * @param numberAsArray The number as an array
     * @param charCount The sequence size of a number of characters to check at a given recursive iteration, starts from 0 ends at array length... 
     * @param uniqueProducts    The set of unique products computed until current iteration 
     * @return
     */
    private static boolean generateUniqueNumbers(char[] numberAsArray, int charCount,
            Set<Integer> uniqueProducts) {

        if(charCount>numberAsArray.length)
            return true;

        for(int i=0;(i+charCount-1)<numberAsArray.length;i++){
            int product=1;
            for(int j=0;j<charCount;j++){
                product=product*Integer.parseInt(new String(numberAsArray[i+j]+""));
            }
            if(!uniqueProducts.add(product))
                return false;
        }
        return generateUniqueNumbers(numberAsArray,charCount+1,uniqueProducts);
    }
}