Getting out of the wheel of Samsara, extremism and a little bit of green - analysis of tasks from the GridGain booklet at Joker 2018 conference
On October 19 and 20, a Joker conference was held in St. Petersburg - the best event for those who love the same thing as us: cool reports, communication with advanced Java experts and problems. We will not praise the third release of tasks from GridGain ( 1 , 2 ), we better quote the feedback from participants:
“Their tasks seemed silly and unrelated to IT”
“Excellent tasks, as always (although I haven’t mastered one)”
“Addiction in tasks”
“Top-priority tasks, as always.” We
publish, as promised, detailed solutions. They brought it under a spoiler so that those who missed the conference could also try their hand.
Three months ago, we wrote this task, but in October 2018, the President took the initiative to decriminalize 282 articles, which we are very happy about, but we were crammed to redo the texts. So let this remain as it was in this task. *
The center-on-a-letter monitors the placement of offensive memes, as well as their likes and reposts in social networks. As part of the digital transformation, the whole office of the employees of the monitoring department was replaced by artificial intelligence. Innovation has helped to quickly calculate how likely the users will go from the likes to the repost, so that you can successfully bring the case to court. Previously, a conviction at the request of the Center-for-one-letter was delivered with a probability of 90% for 192 days. Process automation brought the figures up to 12 days with a probability of 99.9%.
Question: How many times did the conversion of memases into convictions increase by 282, thanks to an innovative approach, if the frequency of sentences has an exponential distribution?
From the point of view of the Buddhist Basil, the code is perfect not when there is nothing to add to it, but when nothing can be removed. Driven by this idea, our Basil decided to improve EpsilonGC and revealed to the world Dzen-GC - a product of perfect thought, which can not only clear heap memory, but does not even allow it to be allocated. It is obvious that allocation in JVM with this innovative GC is possible only on the stack and only for primitive types.
To test the new functional, Vasily decided to write a Java function that finds a mode for 6 values (a mode is a value in the set of observations that occurs most often), that is, it has the following signature:
To get closer to enlightenment, Vasily did not declare additional local variables and methods in his code, and also programmed only the little finger of his left foot.
Task: help Vasily in the implementation of this function (it is allowed to use all fingers).
Two drug addicts decided to get out of the Matrix and figure out which one is the Chosen One. To do this, they extracted 1 pack of blue and 4 packs of red tablets (packs of the same size), and in order to enhance the effect, they decided to wash them down with green paint.
Suddenly, it turned out that because of the glitch of the Matrix (as drug addicts thought), their faces, which initially had RGB colors # 2D241D and # F4E3E1, began to change depending on the number of pills and green stuff consumed: each tablet (or 1 ml of green stuff) linearly increases the number of colors on the face of the addict.
At the same time, the value of each RGB component cannot exceed #FF, that is, the further use of pills or brilliant green has no effect. Zelenki initially had several full vials of 20 ml, a total of 2 times less quantity per ml than the total number of tablets in pieces. After the event of leaving the Matrix, in which the second drug addict ate
54 red pills more than the first blue, the drug addicts had nothing left.
The question is: how many tablets and brilliant green did each addict use if their faces were # F0FF6B and #FFFEFF respectively, and it is known that brilliant green acts 3 times stronger than red tablets, which, in turn, are 2 times
weaker than blue ones?
True, all problems were solved by Alexey Ryzhikov and Valentin Shipilov. Also Alexey Galkin, Anton Blinov, Ilya Perevozchikov and several other participants received prizes. Congratulations!
“Their tasks seemed silly and unrelated to IT”
“Excellent tasks, as always (although I haven’t mastered one)”
“Addiction in tasks”
“Top-priority tasks, as always.” We
publish, as promised, detailed solutions. They brought it under a spoiler so that those who missed the conference could also try their hand.
Task 1
Three months ago, we wrote this task, but in October 2018, the President took the initiative to decriminalize 282 articles, which we are very happy about, but we were crammed to redo the texts. So let this remain as it was in this task. *
The center-on-a-letter monitors the placement of offensive memes, as well as their likes and reposts in social networks. As part of the digital transformation, the whole office of the employees of the monitoring department was replaced by artificial intelligence. Innovation has helped to quickly calculate how likely the users will go from the likes to the repost, so that you can successfully bring the case to court. Previously, a conviction at the request of the Center-for-one-letter was delivered with a probability of 90% for 192 days. Process automation brought the figures up to 12 days with a probability of 99.9%.
Question: How many times did the conversion of memases into convictions increase by 282, thanks to an innovative approach, if the frequency of sentences has an exponential distribution?
Problem solving 1
*Назвав на нашем стенде автора цитаты и произведение, можно было сразу получить подарок. Конечно, это Юрий Хой (Клинских), «Сектор газа» и трек «Бомж»
Согласно изначальному условию, т.к. периодичность приговоров имеет показательное распределение, то до введения робота и после мы имеем следующие выражения для оценки вероятности того, что вынесли приговор за время ≤ t:
где — это неизвестные параметры, задающие частоту вынесения приговоров, t — параметр времени, по условию выходит что:
Из этих уравнений очень легко выражаются параметры
Из предположения, что число приговоров и число мемасиков имеют линейную зависимость, можно заключить, что отношение как раз и дает искомую величину:
Согласно изначальному условию, т.к. периодичность приговоров имеет показательное распределение, то до введения робота и после мы имеем следующие выражения для оценки вероятности того, что вынесли приговор за время ≤ t:
где — это неизвестные параметры, задающие частоту вынесения приговоров, t — параметр времени, по условию выходит что:
Из этих уравнений очень легко выражаются параметры
Из предположения, что число приговоров и число мемасиков имеют линейную зависимость, можно заключить, что отношение как раз и дает искомую величину:
Task 2
From the point of view of the Buddhist Basil, the code is perfect not when there is nothing to add to it, but when nothing can be removed. Driven by this idea, our Basil decided to improve EpsilonGC and revealed to the world Dzen-GC - a product of perfect thought, which can not only clear heap memory, but does not even allow it to be allocated. It is obvious that allocation in JVM with this innovative GC is possible only on the stack and only for primitive types.
To test the new functional, Vasily decided to write a Java function that finds a mode for 6 values (a mode is a value in the set of observations that occurs most often), that is, it has the following signature:
publicstaticintmode(int n0, int n1, int n2, int n3, int n4, int n5)To get closer to enlightenment, Vasily did not declare additional local variables and methods in his code, and also programmed only the little finger of his left foot.
Task: help Vasily in the implementation of this function (it is allowed to use all fingers).
Problem solving 2
Давайте попробуем прикинуть, как можно было бы решить эту задачу, если бы не было таких строгих ограничений. Просто скажем, что значения передаются в массиве, и дополнительную память желательно не использовать (но чуть-чуть можно).
Тогда мы отметем варианты, использующие Map<Integer, Integer>, и заметим, что моду удобнее всего искать в отсортированном массиве: если значение повторяется, все дубликаты находятся рядом. Мы отсортируем массив и за один проход (и две переменные) найдем значение с максимальным количеством повторов.
Теперь заметим что:
1) Отсортировать значения можно рекурсивно.
2) У нас всего 6 отсортированных значений.
3) Если значение повторяется 3 раза (половина всех значений) — это уже мода!
3.1) Если нет, но есть 2 повторения — тогда это мода!
3.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.publicstaticintmode(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;
}Строго говоря, у задачи может быть много решений, но это нам понравилось как самое простое и гармоничное.
Task 3
Two drug addicts decided to get out of the Matrix and figure out which one is the Chosen One. To do this, they extracted 1 pack of blue and 4 packs of red tablets (packs of the same size), and in order to enhance the effect, they decided to wash them down with green paint.
Suddenly, it turned out that because of the glitch of the Matrix (as drug addicts thought), their faces, which initially had RGB colors # 2D241D and # F4E3E1, began to change depending on the number of pills and green stuff consumed: each tablet (or 1 ml of green stuff) linearly increases the number of colors on the face of the addict.
At the same time, the value of each RGB component cannot exceed #FF, that is, the further use of pills or brilliant green has no effect. Zelenki initially had several full vials of 20 ml, a total of 2 times less quantity per ml than the total number of tablets in pieces. After the event of leaving the Matrix, in which the second drug addict ate
54 red pills more than the first blue, the drug addicts had nothing left.
The question is: how many tablets and brilliant green did each addict use if their faces were # F0FF6B and #FFFEFF respectively, and it is known that brilliant green acts 3 times stronger than red tablets, which, in turn, are 2 times
weaker than blue ones?
Problem solving 3
Для начала отберем среди конечных значений для цветов только те, что строго меньше 0xFF, ибо, по условию, для значения 0xFF мы можем дать только нижнюю границу употребленного усилителя цвета. Это значения 0xF0, 0x6B и 0xFE. Получаем следующие уравнения:
или
Здесь k — коэффициент действия красных таблеток, , — количество употребленных усилителей (таблетки измеряем в штуках, зеленку — в миллилитрах) соответствующего цвета соответствующим потребителем. Далее, мы знаем, что второй съел на 54 больше красных таблеток, чем первый синих, тут все просто:
Еще одно уравнение получается из условия на соотношение между количеством таблеток и миллилитрами зеленки:
Также имеем из соотношения между красными и синими таблетками:
Кроме того, мы знаем, что зеленки было сколько-то раз по 20мл:
, где z — целое неотрицательное.
Из предположения, что k целое и таблетки едятся целиком (зеленку можно пить как угодно), единственный ответ, который подходит следующий:
Его можно получить довольно просто, например, способом, описанным далее.
Мы имеем соотношение . Единственные разложения числа 39 на два множителя это {1, 39}, {3, 13}. Таким образом, k может принимать значения только из множества {1, 3, 13, 39}. Попробуем значение «3».
Но при этом должно быть кратно 20, что не выполняется для значения (79.5 + 3).
Ровно таким же образом отсеиваются значения «13» и «39». Единственное значение, которое остается для k — это единица. Подставив его, мы не приходим к противоречиям и получаем ответ.
На самом деле, поскольку нигде в задаче не сказано, что коэффициент линейного приращения k красного компонента RGB — целая величина, решений получается целое семейство, *даже* если считать, что зеленку пьют только объемами, кратными 1мл, а таблетки потребляются целиком (что также не оговаривалось отдельно):
n — целое неотрицательное.
Для получения данного семейства нужно избавиться от k в первых 3-х уравнениях, переписав их, например, как:
после чего решить систему линейных диофантовых уравнений (естественно, включив в нее остальные уравнения, приведенные к надлежащему виду). Если не предполагать, что зеленка потребляется только объемами, кратными миллилитру, получаем уже нелинейную систему диофантовых уравнений, приняв за целые неизвестные числитель и знаменатель g1 и g2 (которые, очевидно, должны быть рациональными). Если же решать задачу в самом общем виде (все значения непрерывные), то решений еще больше.
или
Здесь k — коэффициент действия красных таблеток, , — количество употребленных усилителей (таблетки измеряем в штуках, зеленку — в миллилитрах) соответствующего цвета соответствующим потребителем. Далее, мы знаем, что второй съел на 54 больше красных таблеток, чем первый синих, тут все просто:
Еще одно уравнение получается из условия на соотношение между количеством таблеток и миллилитрами зеленки:
Также имеем из соотношения между красными и синими таблетками:
Кроме того, мы знаем, что зеленки было сколько-то раз по 20мл:
, где z — целое неотрицательное.
Из предположения, что k целое и таблетки едятся целиком (зеленку можно пить как угодно), единственный ответ, который подходит следующий:
Его можно получить довольно просто, например, способом, описанным далее.
Мы имеем соотношение . Единственные разложения числа 39 на два множителя это {1, 39}, {3, 13}. Таким образом, k может принимать значения только из множества {1, 3, 13, 39}. Попробуем значение «3».
Но при этом должно быть кратно 20, что не выполняется для значения (79.5 + 3).
Ровно таким же образом отсеиваются значения «13» и «39». Единственное значение, которое остается для k — это единица. Подставив его, мы не приходим к противоречиям и получаем ответ.
На самом деле, поскольку нигде в задаче не сказано, что коэффициент линейного приращения k красного компонента RGB — целая величина, решений получается целое семейство, *даже* если считать, что зеленку пьют только объемами, кратными 1мл, а таблетки потребляются целиком (что также не оговаривалось отдельно):
n — целое неотрицательное.
Для получения данного семейства нужно избавиться от k в первых 3-х уравнениях, переписав их, например, как:
после чего решить систему линейных диофантовых уравнений (естественно, включив в нее остальные уравнения, приведенные к надлежащему виду). Если не предполагать, что зеленка потребляется только объемами, кратными миллилитру, получаем уже нелинейную систему диофантовых уравнений, приняв за целые неизвестные числитель и знаменатель g1 и g2 (которые, очевидно, должны быть рациональными). Если же решать задачу в самом общем виде (все значения непрерывные), то решений еще больше.
Winners
True, all problems were solved by Alexey Ryzhikov and Valentin Shipilov. Also Alexey Galkin, Anton Blinov, Ilya Perevozchikov and several other participants received prizes. Congratulations!