Выход из колеса Сансары, экстремизм и немного зелёнки — разбор задач из буклета GridGain на конференции Joker 2018

    19 и 20 октября в Петербурге прошла конференция Joker — лучшее мероприятие для тех, кто любит то же самое, что и мы: крутые доклады, общение с продвинутыми Java-экспертами и задачки. Не будем нахваливать третий выпуск задач от GridGain (1, 2), лучше процитируем отзывы участников:

    «Их задачи показались глупыми и не относящимися к ИТ»
    «Отличные задачи, как всегда (хоть ни одной и не осилил)»
    «Наркомания в задачах»
    «Топовые задачи, как всегда»


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



    Задача 1


    Три месяца назад мы написали эту задачу, но в октябре 2018 года президент выступил с инициативой по декриминализации 282 статьи, чему мы несказанно рады, но задолбались тексты переделывать. Так что пусть в этой задаче все остается, как было.*

    Центр-на-некую-букву мониторит размещение оскорбительных мемов, а также их лайки и репосты в соцсетях. В рамках цифровой трансформации целый кабинет сотрудников отдела мониторинга заменили на искусственный интеллект. Инновация помогла быстро рассчитать, с какой вероятностью пользователи от лайков перейдут к репостам, чтобы можно было успешно довести дело до суда. Раньше обвинительный приговор по запросу Центра-на-одну-букву выносился с вероятностью 90% за 192 дня. Автоматизация процесса довела показатели до 12 дней с вероятностью 99,9%.

    Вопрос: во сколько раз благодаря инновационному подходу увеличилась конверсия мемасиков в обвинительные приговоры по 282, если периодичность приговоров имеет показательное распределение?

    Решение задачи 1
    *Назвав на нашем стенде автора цитаты и произведение, можно было сразу получить подарок. Конечно, это Юрий Хой (Клинских), «Сектор газа» и трек «Бомж»

    Согласно изначальному условию, т.к. периодичность приговоров имеет показательное распределение, то до введения робота и после мы имеем следующие выражения для оценки вероятности того, что вынесли приговор за время ≤ t:

    $F_1(t) = 1 - e^{-\lambda_1 * t} \\ F_2(t) = 1 - e^{-\lambda_2 * t}$

    где $\lambda_1, \lambda_2$ — это неизвестные параметры, задающие частоту вынесения приговоров, t — параметр времени, по условию выходит что:

    $F_1(192) = 0.9 \\ F_2(12) = 0.999$

    Из этих уравнений очень легко выражаются параметры $\lambda_1, \lambda_2$

    $\lambda_1 = -\ln(1 - 0.9)/192 \sim = 0.012\\ \lambda_2 = -\ln(1 - 0.999)/12 \sim = 0.576$

    Из предположения, что число приговоров и число мемасиков имеют линейную зависимость, можно заключить, что отношение $\lambda_1, \lambda_2$ как раз и дает искомую величину:

    $\lambda_2 / \lambda_1 \sim = 48$




    Задача 2


    С точки зрения буддиста Василия, код совершенен не тогда, когда в него уже нечего добавить, а когда уже ничего нельзя убрать. Движимый этой идеей наш Василий решил усовершенствовать EpsilonGC и явил миру Dzen-GC — продукт совершенной мысли, который не умеет не только очищать heap memory, но даже не позволяет ее аллоцировать. Очевидно, что аллокация в JVM с этим инновационным GC возможна только на стеке и только для примитивных типов.

    Для проверки нового функционала Василий решил написать на Java функцию, которая находит моду для 6 значений (мода — значение во множестве наблюдений, которое встречается наиболее часто) то есть имеет следующую сигнатуру:

    public static int mode(int n0, int n1, int n2, int n3, int n4, int n5)

    Чтобы приблизиться к просветлению, Василий не объявлял в своем коде дополнительные локальные переменные и методы, а также программировал только мизинцем левой ноги.

    Задача: помогите Василию в реализации данной функции (разрешается пользоваться всеми пальцами).

    Решение задачи 2
    Давайте попробуем прикинуть, как можно было бы решить эту задачу, если бы не было таких строгих ограничений. Просто скажем, что значения передаются в массиве, и дополнительную память желательно не использовать (но чуть-чуть можно).

    Тогда мы отметем варианты, использующие Map<Integer, Integer>, и заметим, что моду удобнее всего искать в отсортированном массиве: если значение повторяется, все дубликаты находятся рядом. Мы отсортируем массив и за один проход (и две переменные) найдем значение с максимальным количеством повторов.

    Теперь заметим что:

    1) Отсортировать значения можно рекурсивно.

    
        // Expectation: if there are more than one mode, we are free to return any of them.
        // 2,2,3,3,4,4 has 3 modes : 2,3,4. I expect that 3 is correct answer.
        public static int mode (int a, int b, int c, int d, int e, int f){
            // If arguments are not sorted, let's sort them with bubble sort :)
            if (a > b)
                return mode(b,a,c,d,e,f);
            if (b > c)
                return mode(a,c,b,d,e,f);
            if (c > d)
                return mode(a,b,d,c,e,f);
            if (d > e)
                return mode(a,b,c,e,d,f);
            if (e > f)
                return mode(a,b,c,d,f,e);


    2) У нас всего 6 отсортированных значений.
    3) Если значение повторяется 3 раза (половина всех значений) — это уже мода!
    3.1) Если нет, но есть 2 повторения — тогда это мода!
    3.2) Если нет повторяющихся значений, то любое значение является модой.

      
            // Check for mode with 3+ repeats. 3 repeats is enough to say value is a mode (3 is half of 6).
            // Since args are sorted, a == b && b == c is the same as a == c;
            if (a == c)
                return a;
            if (b == d)
                return b;
            if (c == e)
                return c;
            if (d == f)
                return d;
    
            // Check for 2 repeats.
            if (a == b)
                return a;
            if (b == c)
                return b;
            if (c == d)
                return c;
            if (d == e)
                return d;
            if (e == f)
                return e;
    
            return f;
           }


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



    Задача 3


    Два наркомана решили выбраться из Матрицы и понять, кто из них Избранный. Для этого они добыли 1 пачку синих и 4 пачки красных таблеток (пачки одинакового размера), а чтобы усилить эффект, решили запивать их зеленкой.

    Внезапно выяснилось, что из-за глюка Матрицы (так подумали наркоманы) их лица, изначально имевшие RGB цвета #2D241D и #F4E3E1, стали меняться в зависимости от количества употребленных таблеток и зеленки: каждая таблетка (или 1 мл зеленки) линейно увеличивает количество соответствующего цвета на лице наркомана.

    При этом значение каждого компонента RGB не может превышать #FF, то есть дальнейшее употребление таблеток или зеленки не оказывает эффекта. Зеленки изначально было несколько полных пузырьков по 20 мл, в сумме в 2 раза меньшее количество в мл, чем общее количество таблеток в штуках. После мероприятия по выходу из Матрицы, в котором второй наркоман съел
    на 54 красных таблетки больше, чем первый синих, у наркоманов не осталось ничего.

    Вопрос: сколько таблеток и зеленки употребил каждый наркоман, если в итоге их лица были цветов #F0FF6B и #FFFEFF соответственно, и известно, что зеленка действует в 3 раза сильнее красных таблеток, которые, в свою очередь, в 2 раза
    слабее синих?

    Решение задачи 3
    Для начала отберем среди конечных значений для цветов только те, что строго меньше 0xFF, ибо, по условию, для значения 0xFF мы можем дать только нижнюю границу употребленного усилителя цвета. Это значения 0xF0, 0x6B и 0xFE. Получаем следующие уравнения:

    $r_1 * k = (0xF0 - 0x2D) = 195\\ b_1 * 2k = (0x6B - 0x1D) = 78 \\ g_2 * 3k = (0xFE - 0xE3) = 27\\ $

    или

    $r_1 * k = 195\\ b_1 * k = 39 \\ g_2 * k = 9\\ $

    Здесь k — коэффициент действия красных таблеток, $col_i, col \in \{r, g, b\}, i \in \{1, 2\}$, — количество употребленных усилителей (таблетки измеряем в штуках, зеленку — в миллилитрах) соответствующего цвета соответствующим потребителем. Далее, мы знаем, что второй съел на 54 больше красных таблеток, чем первый синих, тут все просто:

    $r_2 = 54 + b_1$

    Еще одно уравнение получается из условия на соотношение между количеством таблеток и миллилитрами зеленки:

    $2 * (g_1 + g_2) = (r_1 + b_1 + r_2 + b_2)$

    Также имеем из соотношения между красными и синими таблетками:

    $(r_1 + r_2) = 4(b_1 + b_2)$

    Кроме того, мы знаем, что зеленки было сколько-то раз по 20мл:

    $(g_1 + g_2) = 20 z$, где z — целое неотрицательное.

    Из предположения, что k целое и таблетки едятся целиком (зеленку можно пить как угодно), единственный ответ, который подходит следующий:

    $r_1 = 195\\ g_1 = 171\\ b_1 = 39\\$

    $r_2 = 93\\ g_2 = 9\\ b_2 = 33\\$

    Его можно получить довольно просто, например, способом, описанным далее.
    Мы имеем соотношение $b_1 * k = 39$. Единственные разложения числа 39 на два множителя это {1, 39}, {3, 13}. Таким образом, k может принимать значения только из множества {1, 3, 13, 39}. Попробуем значение «3».

    $r_1 = 195 / 3 = 65,\\ b_1 = 39 / 3 = 13,\\ g_2 = 9 / 3 = 3,\\ r_2 = 54 + b1 = 54 + 13 = 67,\\ b_2 = ((r1 + r2) - 4 * b1) / 4 = (65 + 67 - 4 * 13) / 4 = 20,\\ g_1 = ((r1 + b1 + r2 + b2) - 2 * g2) / 2 = (65 + 13 + 67 + 20 - 2 * 3) / 2 = 79 / 2.$

    Но при этом $g_1 + g_2$ должно быть кратно 20, что не выполняется для значения (79.5 + 3).

    Ровно таким же образом отсеиваются значения «13» и «39». Единственное значение, которое остается для k — это единица. Подставив его, мы не приходим к противоречиям и получаем ответ.

    На самом деле, поскольку нигде в задаче не сказано, что коэффициент линейного приращения k красного компонента RGB — целая величина, решений получается целое семейство, *даже* если считать, что зеленку пьют только объемами, кратными 1мл, а таблетки потребляются целиком (что также не оговаривалось отдельно):

    $r_1 = 1040n + 195\\ g_1 = 732n + 171\\ b_1 = 208n + 39\\ $

    $r_2 = 208n + 93\\ g_2 = 48n + 9\\ b_2 = 104n + 33\\ $
    n — целое неотрицательное.

    Для получения данного семейства нужно избавиться от k в первых 3-х уравнениях, переписав их, например, как:

    $3 r_1 - 15 b_1=0,\\ 3 r_1 - 65 g_2=0,\\ 15b_1 - 65g_2=0,\\ $

    после чего решить систему линейных диофантовых уравнений (естественно, включив в нее остальные уравнения, приведенные к надлежащему виду). Если не предполагать, что зеленка потребляется только объемами, кратными миллилитру, получаем уже нелинейную систему диофантовых уравнений, приняв за целые неизвестные числитель и знаменатель g1 и g2 (которые, очевидно, должны быть рациональными). Если же решать задачу в самом общем виде (все значения непрерывные), то решений еще больше.

    Победители


    Верно все задачи решили Алексей Рыжиков и Валентин Шипилов. Также призы получили Алексей Галкин, Антон Блинов, Илья Перевозчиков и еще несколько участников. Поздравляем!
    GridGain
    100,00
    Компания
    Поделиться публикацией

    Комментарии 2

      +5
      Решение второй чертовски изящно. Первое, что пришло в голову мне — это кодогенерация. Рабочая, но тупая и человеконечитаемая функция, текст которой сгенерирован скриптом. Ради интереса, такое решение было бы принято?
        +3
        Да, коллеги, проверявшие решения, говорят, что было как раз одно, которое перебирало все возможные тройки, потом двойки, и оно было засчитано. Засчитывали любой работающий метод. У нас и внутри было несколько версий, опубликовали самую элегантную.

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое