SRM 403

Итак, матч проходил в четверг, 29 мая, в 7:00 по местному времени. Как справедливо отметил сцуко sharpc, мне удалось побить почти все возможные антирекорды, заняв почётное 428-е место из 429 возможных, потеряв 170 рейтинговых очков и сменив свой цвет с козырного ж0лтого на позорный синий.

Примечание: если кто не в курсе, на топкодере принята цветовая дифференциация штанов: серый < зелёный < синий < жёлтый < красный. Сине-жёлто-красно-штанные камрады тусуются в Division 1, где задачи посложнее; остальные соревнуются в Division 2 — там всё гораздо проще, и даже не очень умелому топкодеру легко решить все три задачи. Задач по три в каждом дивизионе (лёгкая, средняя и сложная), но шесть уникальных не бывает никогда — обычно, например, Div2 Medium совпадает с Div1 Easy.

В этот раз произошло довольно уникально событие: задачи оказались объединены общей идеей, что на tc-контестах довольно редкое явление (а вот условия задач ICPC-контестов сплошь и рядом такие, например, последний чемпионат УрГУ был посвящён трамваям :)). Всё строилось вокруг следующего определения:

Итак, задачи.

Div1 Easy — TheLuckyNumbers

В Division 2 эта задача была medium'ом.

Сразу понятно, что простой перебор чисел от a до b с проверкой каждого из них на наличие счастья не уложится в две секунды, отведённые каждому решению на один тест. Но можно сообразить, что счастливых чисел до миллиарда не так уж много. Фактически, если рассматривать счастливые числа как записанные в двоичной системе счисления (4 мысленно заменим на 0, а 7 — на 1), то их в точности , где mx — длина максимального рассматриваемого счастливого числа. В нашем случае таким числом будет 777777777, mx будет равно 9, и формула даст 1022 числа. И правда, счастливых чисел очень мало.

Таким образом, достаточно просто сгенерировать все возможные счастливые числа и проверить, попадают ли они в заданный диапазон. За пять минут я придумал и написал вот такое рекурсивное решение (приведена правильная версия):

public class TheLuckyNumbers
{
    int total;
    int[] lucky = { 4, 7 };

    void Rec(int a, int b, int start, int length)
    {
        if (start >= a && start <= b)
            total++;
        if (length < 9) // здесь я почему-то написал 7

        {
            foreach (int i in lucky)
                Rec(a, b, start * 10 + i, length + 1);
        }
    }

    public int count(int a, int b)
    {
        Rec(a, b, 0, 0);
        return total;
    }
}

Вот только в месте с комментарием я по каким-то непонятным даже для себя причинам ограничил максимальную длину числа семью вместо девяти. Более того, я специально протестировал перед отправкой решение на тесте a = 1, b = 10⁹, увидел результат 254, просуммировал степени двойки до 7, «убедившись» в корректности этого ответа, и стремительно засабмитил программу. Осознал я свою ошибку, только увидев надпись Failed System Tests в Division Summary. :(

Div1 Medium — TheLuckySequence

Действительно, эту задачу можно решить двумя разными способами. Решение возведением матрицы в степень уже рассказал sharpc. Однако второй способ, как оказалось, проще для понимания и изящнее. Так что излагать я буду именно его. :)

Для начала напишем вспомогательную функцию IsLucky, которая будет проверять, является число счастливым. В хаскелле это просто и элегантно записалось бы как

isLucky x = all ((flip elem $ [4, 7]) . (`mod` 10)) $ takeWhile (/= 0) $ iterate (`div` 10) x

(Хорош ржать, да, это просто и элегантно!!!)

Я же пишу топкодер на C#, поэтому моё определение выглядит так:

private bool IsLucky(int num)
{
    while (num > 0)
    {
        int z = num % 10;
        if (z != 4 && z != 7)
            return false;
        num /= 10;
    }
    return true;
}

Ограничение на длину последовательности достаточно велико, чтобы даже не задумываться о решении за O(length) (такой алгоритм придумывается достаточно легко). Нужно придумать что-то более эффективное.

Подумаем, как мы можем упростить исходную задачу? Например, попробуем зафиксировать две цифры: ту, с которой будет начинаться первое число последовательности и ту, которой будет заканчиваться последнее. Если мы научимся находить количество таких последовательностей, то достаточно будет перебрать все возможные варианты расстановки первой и последней цифр (4/4, 7/7, 4/7 и 7/4) и просуммировать ответы по ним.

Перед тем, как двигаться дальше, обработаем входные данные и выкинем их. :) Введём обозначения:

число x начинается c цифры i

число x заканчивается цифрой i

Если вдуматься, нам интересны только множества вида Nums_{i, j}, где , то есть те, куда попадают счастливые числа (несчастливые мы просто выкинем). Более того, относительно этих множеств нас интересует только их мощность, а не содержимое (числа 47477 и 47 для нас неразличимы; там, куда мы можем поставить одно число, можно легко поставить и другое). Количество чисел в множестве Nums_{i, j} запишем в массив numCnt[i & 1, j & 1], по дороге удаляя дубликаты (выражение x & 1 четвёрке сопоставит ноль, а семёрке — единицу; мы делаем это исключительно для удобства и уменьшения размера массива):

int[,] numCnt = new int[2,2];

numbers = Array.FindAll(numbers, IsLucky);
Dictionary<int, int> unique = new Dictionary<int, int>();

foreach (int num in numbers)
{
    if (!unique.ContainsKey(num))
    {
        string tmp = num.ToString();
        numCnt[tmp[0] & 1, tmp[tmp.Length - 1] & 1]++;
        unique[num] = 1;
    }
}

Окей, попробуем построить функцию Rec(n, a, b), которая принимает длину последовательности n, первую её цифру a и последнюю цифру b (опять же для удобства будем от цифр 4 и 7 перейдём к цифрам 0 и 1) и возвращает количество таких последовательностей.

Положим m = n div 2.

• Если n = 1, то ответ равен просто numCnt[a, b].
• Если n чётно, то наша последовательность разбивается на две одинаковые, длины m. Первая часть должна заканчиваться той же цифрой x, какой начинается вторая. Ответ, очевидно, будет равен будет равен сумме Rec(m, a, x) * Rec(m, x, b) по всем возможным x (либо 0, либо 1).
• Если n нечётно, то последовательность снова разбивается на две, длины m, но теперь в середине между ними есть ещё одна последовательность длины 1. Если мы зафиксируем, в какое из множеств Nums_{i, j} попадает единственное число в этой последовательности, то ответ будет равен Rec(m, a, i) * Rec(1, i, j) * Rec(m, j, b). Возможных вариантов для i и j всего 4, достаточно перебрать их все.

Уф. Кажется, получилось что-то рабочее. Относительно этого чего-то есть две новости: хорошая и плохая. :)

Хорошая: на каждом шаге мы уменьшаем параметр n аж в два раза. Это означает, что перед тем, как мы дойдём до последовательностей длины 1, пройдёт всего шагов, что совсем немного. :)

Плохая: Поскольку на каждом шаге мы делаем два или четыре рекурсивных вызова, дерево рекурсии разрастётся экспоненциально, и на больших n алгоритм будет не будет завершаться за разумное время.

К счастью, плохую новость легко превратить в хорошую, используя мемоизацию — технику запоминания значений, возвращённых рекурсивными вызовами. Понятно, что значение функции Rec() полностью определяется её параметрами. Возможных значений параметров не так много: длина последовательности может принимать всего логарифм разных значений (например, если исходно length было равно 67, то Rec() может вызываться только с n = 67, 33, 16, 8, 4, 2 или 1), а а и b и вовсе равны либо 0, либо 1. Поэтому поступим так: если мы уже посчитали значение Rec(n, a, b), и оно равно x, то запомним это в специальном словаре. Когда Rec() снова вызовется с теми же параметрами, просто вернём уже посчитанное значение из словаря.

С такой оптимизацией сложность алгоритма уменьшается до логарифмической (относительно length) с не очень большой константой. Двоичный логариф от миллиарда — это что-то порядка 30, так что беспокоиться не о чём, решение, как говорится, will pass with flying colors.

Сердце решения будет выглядеть примерно так:

private Dictionary<State, int> ways = new Dictionary<State, int>();


private int Rec(State s)
{
    if (ways.ContainsKey(s))
        return ways[s];
    if (s.Length == 1)
        return numCnt[s.Begin, s.End];

    int res = 0;

    int[,] halfWays = new int[2, 2];
    int half = s.Length / 2;
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 2; j++)
            halfWays[i, j] = Rec(new State(i, j, half));
    }

    if (s.Length % 2 == 0)
    {
        for (int i = 0; i < 2; i++)
            res = Add(res, Mul(halfWays[s.Begin, i], halfWays[i, s.End]));
    }
    else

    {
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 2; j++)
                res = Add(res, Mul(halfWays[s.Begin, i], numCnt[i, j], halfWays[j, s.End]));
        }
    }

    return ways[s] = res;
}

Полный исходник.

Div1 Hard — TheLuckySum

Это очень красивая задача: она требует хитрой идеи и внимания при реализации. Стоит отметить, что в Div2 hard'ом послужила та же самая задача, но с n до миллиона. С таким ограничением задача решается проще, но разбирать её смысла нет — лучше решить сложную задачу, тогда лёгкая решится автоматически. :)

На первый взгляд непонятно, как к ней подступиться так, чтобы уложиться в 2 секунды. Попробуем нащупать путь методом последовательных упрощений.

Сначала определим, когда надо вернуть пустой массив? Понятно, что все числа, меньшие 4, определённо не поддадутся разложению. Если почеркаться на бумажке, то станет понятно, что неразложимых чисел совсем мало, не больше десятка, и все они меньше 20. Понять это можно, например, так:

• 19 = 4 + 4 + 4 + 7
• 20 = 4 + 4 + 4 + 4
• 21 = 7 + 7 + 7
• 22 = 4 + 4 + 7 + 7

Дальше в дело вступает индукция: для бо́льших чисел вычтем четвёрку и получим разложимое по предположению индукции число. Также видно, что маленькие числа представимы в виде x * 4 + y * 7. Ergo, если число маленькое, можно запустить полный перебор по x и y и вернуть результат этого перебора:

if (n <= 30)
{
    for (int len = 1; len <= 5; len++)
    {
        for (int c4 = len; c4 >= 0; c4--)
        {
            int c7 = len - c4;
            if (c7 * 7 + c4 * 4 == n)
                return CreateArr(0, c4, c7);
        }
    }
    return new int[0];
}

Функция CreateArr() создаёт массив с заданным количеством нулей, четвёрок и семёрок (она нам ещё понадобится).

int[] CreateArr(int c0, int c4, int c7)
{
    int total = c0 + c4 + c7;
    int[] arr = new int[total];
    for (int i = 0; i < total; i++)
        arr[i] = i >= c0 ? i >= c0 + c4 ? 7 : 4 : 0;
    return arr;
}

Теперь можно решать задачу в предположении, что ответ существует. Следующее соображение — длина ответа достаточно мала (по крайней мере, её можно грубо оценить логарифмом разлагаемого числа n: в его окрестности найдётся всегда найдётся счастливое число, примерно равное n / 2; вычтем его и продолжим по индукции). Поэтому можно сделать ещё одно упрощение: будем перебирать длину ответа k, начиная с единицы, и решать задачу «разложить ровно в k счастливых чисел». Как только для какого-то k ответ нашёлся, немедленно возращаем его.

Вот теперь пришло время сделать действительно важное наблюдение, которое фактически решает задачу. Предположим, что мы нашли правильный ответ — k чисел. Выпишем их одно под другим (как будто собрались складывать), под ними напишем n и внимательно посмотрим на них.

04 = a1
44 = a2
47 = a3
--
95 = n

Порядок цифр в каждом столбике нас абсолютно не волнует, их можно спокойно переставлять, как захочется. Например, так, чтобы сделать ответ лексикографически минимальным. :) Если представить, что все числа дополнены ведущими нулями до длины десятичной записи числа n, то можно считать, что каждый столбик имеет вид 0…04…4…7…7 (какие-то цифры могут отсутствовать, важен именно порядок: все четвёрки после всех нулей, а все семёрки после четвёрок и нулей). А теперь стало примерно понятно, что решать надо в формулировке «по данному номеру столбика опеределить лексикографически минимальный набор чисел (если такой есть) дающий в сумме число, получающееся из n обрезанием всех цифр правее данного столбика». Наверное, чтобы в это вникнуть, надо порисовать немного на бумажке. :D

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

Ещё здесь надо учесть три тонкости:

• Кроме текущего столбика, надо хранить перенос из предыдущего — иначе мы не сможем корректно посчитать сумму.
• Ещё надо хранить количество нулей в предыдущем столбике и следить за тем, чтобы при проходе справа налево количество нулей монотонно не убывало (иначе у нас появятся нули в середине чисел).
• Когда мы пришли в самый левый столбик, переходить дальше влево не надо :), зато надо проследить, чтобы перенос при данной расстановке цифр был равен нулю — иначе появится «лишний» разряд.

Извините, если взорвал ваш мозг — на словах изложить решение так, чтобы было кристально понятно, достаточно сложно. Ручка и бумажка — ваши друзья. :)

Итак, рекурсивная функция принимает: номер столбика, перенос и количество нулей и возвращает определённый набор чисел. Для полного счастья снова прикрутим мемоизацию (хотя здесь она особо и не нужна — опытным путём было определено, что алгоритм будет достаточно быстро работать и без неё). На этот раз в качестве средства для запоминания значений можно использовать даже массив — все параметры достаточно небольшие.

Вот основная часть решения:

private int[,,][] best; // массив для мемоизации

private readonly List<int> digits = new List<int>(); // цифры числа n
private int numCnt; // количество чисел k

private int digCnt; // количество цифр в n; можно было явно не хранить, но я не стал исправлять

private int[] Rec(int digit, int carry, int zeroes)
{
    // digit — номер столбца

    // carry — перенос из предыдущего столбца
    // zeroes — количество нулей в предыдущем стобце
    if (best[digit, carry, zeroes] != null)
        return best[digit, carry, zeroes];

    int[] ans = new int[0];

    // перебор расстановки цифр в текущем столбце

    for (int c0 = zeroes; c0 <= numCnt; c0++)
    {
        for (int c4 = numCnt - c0; c4 >= 0; c4--)
        {
            int c7 = numCnt - (c0 + c4);
            int z = c4 * 4 + c7 * 7 + carry;
            int sumDigit = z % 10; // сумма цифр с учётом предыдущего переноса

            int sumCarry = z / 10; // новый перенос
            if (sumDigit == digits[digit])
            {
                bool ok = false; // текущая расстановка даёт какой-то ответ?

                int[] cand = CreateArr(c0, c4, c7); // создаём расстановку в явном виде

                if (digit != digCnt - 1) // слева есть столбцы
                {
                    int[] prevBest = Rec(digit + 1, sumCarry, c0); // решаем подзадачу, сместившись влево

                    if (prevBest.Length > 0)
                    {
                        ok = true; // нашли решение
                        for (int i = 0; i < cand.Length; i++)
                            cand[i] = prevBest[i] * 10 + cand[i]; // склеиваем столбцы

                    }
                }
                else
                    ok = sumCarry == 0; // самый левый столбец; следим, чтобы переноса не было

                // расстановка подходит, и новое решение меньше предыдущего
                if (ok && (ans.Length == 0 || Less(cand, ans)))
                    ans = cand;
            }
        }
    }
    return best[digit, carry, zeroes] = ans;
}


// лексикографическое сравнение
private bool Less(int[] a, int[] b)
{
    for (int i = 0; i < a.Length; i++)
    {
        if (a[i] < b[i])
            return true;
    }
    return false;
}

Полный исходник.

Решение Пети Митричева.

Решение Томаша Чайки.