Getting out of the wheel of Samsara, extremism and some greens - analysis of tasks from the GridGain booklet at the 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 presentations, 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 (though I haven’t mastered any of them)”
"Drug addiction in tasks"
"Top 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 everything in this task remain as it was. *
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 with artificial intelligence. Innovation has helped to quickly calculate the likelihood of users from the likes will go to 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 performance 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:
In order 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 originally 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.
The value of each component of RGB can not exceed # FF, that is, the further use of pills or brilliant green has no effect. Zelenki initially had several full bubbles of 20 ml each, a total of 2 times less quantity per ml than the total number of tablets in pieces. After the exit from the Matrix, in which the second drug addict ate
54 red pills more than the first blue, addicts have nothing left.
Question: how many tablets and brilliant green each addict consumed, if in the end 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?
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 (though I haven’t mastered any of them)”
"Drug addiction in tasks"
"Top 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 everything in this task remain as it was. *
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 with artificial intelligence. Innovation has helped to quickly calculate the likelihood of users from the likes will go to 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 performance 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
* Having called the author of the quotation and the work on our stand, one could immediately receive a gift. Of course, this is Yuri Khoy (Klinsky), “The Gas Sector” and the track “Bum”
According to the original condition, since the frequency of sentences has an exponential distribution, then before and after the introduction of the robot, we have the following expressions for estimating the probability that a sentence was pronounced in a time ≤ t:
Where - these are unknown parameters that set the frequency of sentencing, t is a time parameter, according to the condition that:
From these equations, parameters are very easily expressed.
From the assumption that the number of sentences and the number of memesics are linearly dependent, we can conclude that the ratio just gives the desired value:
According to the original condition, since the frequency of sentences has an exponential distribution, then before and after the introduction of the robot, we have the following expressions for estimating the probability that a sentence was pronounced in a time ≤ t:
Where - these are unknown parameters that set the frequency of sentencing, t is a time parameter, according to the condition that:
From these equations, parameters are very easily expressed.
From the assumption that the number of sentences and the number of memesics are linearly dependent, we can conclude that the ratio just gives the desired value:
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:
public static int mode(int n0, int n1, int n2, int n3, int n4, int n5) In order 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
Let's try to figure out how this problem could be solved if there were no such strict restrictions. We simply say that the values are transferred in an array, and it is advisable not to use additional memory (but a little bit is possible).
Then we mark the options that use Map <Integer, Integer>, and note that it is most convenient to look for fashion in a sorted array: if the value is repeated, all duplicates are nearby. We will sort the array and in one pass (and two variables) find the value with the maximum number of repetitions.
Now note that:
1) You can sort the values recursively.
2) We have a total of 6 sorted values.
3) If the value is repeated 3 times (half of all values) - this is already a fashion!
3.1) If not, but there are 2 repetitions - then it is a fashion!
3.2) If there are no duplicate values, then any value is a fashion.
Strictly speaking, a task can have many solutions, but we liked it as the simplest and harmonious one.
Then we mark the options that use Map <Integer, Integer>, and note that it is most convenient to look for fashion in a sorted array: if the value is repeated, all duplicates are nearby. We will sort the array and in one pass (and two variables) find the value with the maximum number of repetitions.
Now note that:
1) You can sort the values recursively.
// 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) We have a total of 6 sorted values.
3) If the value is repeated 3 times (half of all values) - this is already a fashion!
3.1) If not, but there are 2 repetitions - then it is a fashion!
3.2) If there are no duplicate values, then any value is a fashion.
// 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; } Strictly speaking, a task can have many solutions, but we liked it as the simplest and harmonious one.
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 originally 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.
The value of each component of RGB can not exceed # FF, that is, the further use of pills or brilliant green has no effect. Zelenki initially had several full bubbles of 20 ml each, a total of 2 times less quantity per ml than the total number of tablets in pieces. After the exit from the Matrix, in which the second drug addict ate
54 red pills more than the first blue, addicts have nothing left.
Question: how many tablets and brilliant green each addict consumed, if in the end 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?
Problem solving 3
To begin with, we will select among the final values for colors only those that are strictly less than 0xFF, because, by the condition, for the value 0xFF we can only give the lower limit of the color amplifier used. These are the values 0xF0, 0x6B and 0xFE. We get the following equations:
or
Here k is the coefficient of action of the red tablets, , Is the number of used amplifiers (we measure tablets in pieces, brilliant green in milliliters) of the corresponding color by the corresponding consumer. Further, we know that the second one ate 54 more red tablets than the first one blue, everything is simple:
Another equation is obtained from the condition on the ratio between the number of tablets and milliliters of greens:
Also we have from the ratio between red and blue pills:
In addition, we know that the brilliant greens were some 20 ml each time:
where z is non-negative integer.
From the assumption that k is whole and the pills are eaten whole (brilliant green you can drink as you please), the only answer that suits the following:
It can be obtained quite simply, for example, in the manner described below.
We have the ratio . The only expansions of 39 into two factors are {1, 39}, {3, 13}. Thus, k can take values only from the set {1, 3, 13, 39}. Let's try the value "3".
But at the same time must be a multiple of 20, which is not the case for the value (79.5 + 3).
The values “13” and “39” are eliminated in exactly the same way. The only value that remains for k is one. Substituting it, we do not come to contradictions and get an answer.
In fact, since nowhere in the problem it is not said that the linear increment coefficient k of the red component RGB is an integer, the solutions result in a whole family, * even * if we assume that green stuff is drunk only in multiples of 1 ml, and the tablets are consumed as a whole (which also not specified separately):
n is a nonnegative integer.
To obtain this family, you need to get rid of k in the first 3 equations, rewriting them, for example, as:
then solve the system of linear Diophantine equations (of course, by including in it the other equations reduced to the proper form). If we do not assume that brilliant green is consumed only by volumes that are multiples of a milliliter, we obtain the already nonlinear system of Diophantine equations, taking the numerator and denominator g1 and g2 as whole unknowns (which, obviously, should be rational). If we solve the problem in the most general form (all values are continuous), then there are even more solutions.
or
Here k is the coefficient of action of the red tablets, , Is the number of used amplifiers (we measure tablets in pieces, brilliant green in milliliters) of the corresponding color by the corresponding consumer. Further, we know that the second one ate 54 more red tablets than the first one blue, everything is simple:
Another equation is obtained from the condition on the ratio between the number of tablets and milliliters of greens:
Also we have from the ratio between red and blue pills:
In addition, we know that the brilliant greens were some 20 ml each time:
where z is non-negative integer.
From the assumption that k is whole and the pills are eaten whole (brilliant green you can drink as you please), the only answer that suits the following:
It can be obtained quite simply, for example, in the manner described below.
We have the ratio . The only expansions of 39 into two factors are {1, 39}, {3, 13}. Thus, k can take values only from the set {1, 3, 13, 39}. Let's try the value "3".
But at the same time must be a multiple of 20, which is not the case for the value (79.5 + 3).
The values “13” and “39” are eliminated in exactly the same way. The only value that remains for k is one. Substituting it, we do not come to contradictions and get an answer.
In fact, since nowhere in the problem it is not said that the linear increment coefficient k of the red component RGB is an integer, the solutions result in a whole family, * even * if we assume that green stuff is drunk only in multiples of 1 ml, and the tablets are consumed as a whole (which also not specified separately):
n is a nonnegative integer.
To obtain this family, you need to get rid of k in the first 3 equations, rewriting them, for example, as:
then solve the system of linear Diophantine equations (of course, by including in it the other equations reduced to the proper form). If we do not assume that brilliant green is consumed only by volumes that are multiples of a milliliter, we obtain the already nonlinear system of Diophantine equations, taking the numerator and denominator g1 and g2 as whole unknowns (which, obviously, should be rational). If we solve the problem in the most general form (all values are continuous), then there are even more solutions.
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!
Source: https://habr.com/ru/post/428369/
All Articles