🔐 🚕 👨🏽‍🍳 Sair da roda de Sansara, extremismo e um pouco de coisa verde - uma análise de tarefas do livreto GridGain na conferência Joker 2018 😊 🚢 🔢

A conferência Joker foi realizada nos dias 19 e 20 de outubro em São Petersburgo - o melhor evento para quem gosta das mesmas coisas que nós: relatórios legais, comunicação com especialistas e tarefas avançados em Java. Não elogiaremos a terceira edição das tarefas do GridGain ( 1 , 2 ), citamos melhor o feedback dos participantes:

"Suas tarefas pareciam estúpidas e não relacionadas à TI"
“Excelentes tarefas, como sempre (embora eu não tenha dominado uma)”
"Dependência em tarefas"
"Principais tarefas, como sempre"

Publicamos, como prometido, soluções detalhadas. Eles o publicaram sob o spoiler para que aqueles que perdessem a conferência pudessem experimentar.

Tarefa 1

Há três meses, escrevemos essa tarefa, mas em outubro de 2018, o presidente teve a iniciativa de descriminalizar 282 artigos, dos quais estamos incrivelmente felizes, mas estávamos cansados de refazer textos. Portanto, deixe tudo permanecer nessa tarefa como estava. *

O centro da carta monitora a colocação de memes ofensivos, bem como seus gostos e republicações nas redes sociais. Como parte da transformação digital, todo o escritório do departamento de monitoramento foi substituído por inteligência artificial. A inovação ajudou a calcular rapidamente a probabilidade de usuários mudarem de curtidas para republicações, a fim de levar o caso a tribunal com sucesso. Anteriormente, uma condenação de uma letra era emitida com uma probabilidade de 90% em 192 dias. A automação do processo levou os indicadores a 12 dias, com probabilidade de 99,9%.

Pergunta: quantas vezes a abordagem inovadora aumentou a conversão de memasics em condenações em 282, se a frequência das sentenças tiver uma distribuição exponencial?

Solução para o Problema 1

* Depois de citar um nome e um trabalho no estande do nosso autor, você poderá receber imediatamente um presente. Claro, este é Yuri Khoy (Klinsky), "Setor de Gás" e a faixa "Homeless"

De acordo com a condição inicial, já que a frequência das sentenças tem uma distribuição exponencial, antes da introdução do robô e depois das seguintes expressões para avaliar a probabilidade de uma sentença ser pronunciada no tempo ≤ t:

F_{1} (t) = 1 - e^{- l a m b d a_{1} * t} F_{2} (t) = 1 - e^{- l a m b d a_{2} * t}

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

onde

l a m b d a_{1}, l a m b d a_{2}

$\ lambda_1, \ lambda_2$ - são parâmetros desconhecidos que especificam a frequência das sentenças, t é o parâmetro de tempo, de acordo com a condição em que se verifica que:

F_{1} (192) = 0, 9 F_{2} (12) = 0, 999

$F_1 (192) = 0,9 \\ F_2 (12) = 0,999$

A partir dessas equações, os parâmetros são facilmente expressos

l a m b d a_{1}, l a m b d a_{2}

$\ lambda_1, \ lambda_2$

l a m b d a_{1} = - l n (1 - 0, 9) / 192 s i m = 0, 012 l a m b d a_{2} = - l n (1 - 0, 999) / 12 s i m = 0, 576

$\ lambda_1 = - \ ln (1 - 0,9) / 192 \ sim = 0,012 \\ \ lambda_2 = - \ ln (1 - 0,999) / 12 \ sim = 0,576$

Partindo do pressuposto de que o número de sentenças e o número de memasics estão linearmente relacionados, podemos concluir que a razão

l a m b d a_{1}, l a m b d a_{2}

$\ lambda_1, \ lambda_2$ apenas fornece o valor desejado:

l a m b d a_{2} / l a m b d a_{1} s i m = 48

$\ lambda_2 / \ lambda_1 \ sim = 48$

Tarefa 2

Do ponto de vista da Vasily budista, o código é perfeito não quando não há nada a acrescentar, mas quando nada pode ser removido. Motivados por essa ideia, nosso Vasily decidiu melhorar o EpsilonGC e revelou ao mundo o Dzen-GC - um produto de pensamento perfeito que pode não apenas limpar a memória da pilha, mas também não permite que ela seja alocada. Obviamente, a alocação na JVM com este GC inovador só é possível na pilha e apenas para tipos primitivos.

Para testar a nova funcionalidade, Vasily decidiu escrever uma função em Java que encontre um modo para 6 valores (mode é o valor no conjunto de observações que ocorre com mais frequência), ou seja, possui a seguinte assinatura:

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

Para se aproximar da iluminação, Vasily não declarou variáveis e métodos locais adicionais em seu código, e também programou apenas com o dedo mínimo do pé esquerdo.

Tarefa: ajudar o Vasily na implementação desta função (é permitido o uso de todos os dedos).

Solução para o Problema 2

Vamos tentar descobrir como esse problema poderia ser resolvido se não houvesse restrições tão rígidas. Apenas diga que os valores são transferidos em uma matriz e é aconselhável não usar a memória adicional (mas um pouco é possível).

Depois, observaremos as opções que usam Mapa <Inteiro, Inteiro> e perceberemos que o modo é mais conveniente para procurar em uma matriz classificada: se o valor for repetido, todas as duplicatas estarão próximas. Classificamos a matriz e, em uma passagem (e duas variáveis), encontramos o valor com o número máximo de repetições.

Agora observe que:

1) Você pode classificar os valores recursivamente.

 // 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) Temos apenas 6 valores classificados.
3) Se o valor for repetido 3 vezes (metade de todos os valores) - isso já é um mod!
3.1) Se não, mas existem 2 repetições - então este é um mod!
3.2) Se não houver valores duplicados, qualquer valor será um modo.

 // 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; }

A rigor, um problema pode ter muitas soluções, mas gostamos dele como o mais simples e harmonioso.

Tarefa 3

Dois viciados em drogas decidiram sair da Matrix e entender qual deles era o escolhido. Para fazer isso, eles receberam 1 pacote de azul e 4 pacotes de pílulas vermelhas (embalagens do mesmo tamanho) e, para aumentar o efeito, eles decidiram beber com verde.

De repente, descobriu-se que, devido à falha da Matrix (como pensavam os viciados em drogas), seus rostos, que inicialmente tinham as cores RGB # 2D241D e # F4E3E1, começaram a mudar de acordo com o número de comprimidos e a água verde usada: cada comprimido (ou 1 ml de água verde) aumentou linearmente a quantidade do correspondente as cores no rosto do viciado.

Ao mesmo tempo, o valor de cada componente RGB não pode exceder #FF, ou seja, o uso posterior de tablets ou verde brilhante não tem efeito. Zelenka tinha inicialmente vários frascos para injetáveis de 20 ml cada, 2 vezes menos no total em ml do que o número total de comprimidos em pedaços. Após o evento de saída da Matrix, no qual o segundo viciado comeu
54 mais comprimidos vermelhos do que o primeiro azul, os viciados em drogas não tinham mais nada.

Pergunta: quantas pílulas e notas de dólar cada viciado usava se, como resultado, seus rostos fossem # F0FF6B e #FFFEFF, respectivamente, e sabe-se que as notas de dólar são 3 vezes mais fortes que os comprimidos vermelhos, que, por sua vez, são 2 vezes
mais fraco que o azul?

Solução para o Problema 3

Para começar, selecionaremos entre os valores finais para as cores apenas aquelas estritamente menores que 0xFF, porque, por condição, para o valor 0xFF, podemos apenas fornecer a borda inferior do intensificador de cores usado. Estes são os valores 0xF0, 0x6B e 0xFE. Obtemos as seguintes equações:

r_{1} * k = (0 x F 0 - 0 x 2 D) = 195 b_{1} * 2 k = (0 x 6 B - 0 x 1 D) = 78 g_{2} * 3 k = (0 x F E - 0 x E 3) = 27

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

ou

r_{1} * k = 195 b_{1} * k = 39 g_{2} * k = 9

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

Aqui k é o coeficiente de ação das pílulas vermelhas,

col_i, col \ in \ {r, g, b \}, i \ in \ {1, 2 \}

$col_i, col \ in \ {r, g, b \}, i \ in \ {1, 2 \}$ , - o número de amplificadores utilizados (os comprimidos são medidos em pedaços, verde - em mililitros) da cor correspondente pelo consumidor correspondente. Além disso, sabemos que o segundo comia mais 54 comprimidos vermelhos do que o primeiro azul, tudo é simples:

r_{2} = 54 + b_{1}

$r_2 = 54 + b_1$

Outra equação é obtida a partir da condição na razão entre o número de comprimidos e mililitros de verde:

2 * (g_{1} + g_{2}) = (r_{1} + b_{1} + r_{2} + b_{2})

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

Também temos a partir da razão entre comprimidos vermelhos e azuis:

(r_{1} + r_{2}) = 4 (b_{1} + b_{2})

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

Além disso, sabemos que havia várias vezes 20 ml de dólares:

(g_{1} + g_{2}) = 20 z

$(g_1 + g_2) = 20 z$ onde z é um número inteiro não negativo.

Partindo do pressuposto de que k é inteiro e que as pílulas são consumidas inteiras (você pode beber notas como quiser), a única resposta que se encaixa na seguinte:

r_{1} = 195 g_{1} = 171 b_{1} = 39

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

r_{2} = 93 g_{2} = 9 b_{2} = 33

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

Pode ser obtido de maneira bastante simples, por exemplo, pelo método descrito abaixo.
Nós temos uma relação

b_{1} * k = 39

$b_1 * k = 39$ . As únicas fatorações de 39 são {1, 39}, {3, 13}. Portanto, k pode receber valores apenas do conjunto {1, 3, 13, 39}. Vamos tentar o valor "3".

r_{1} = 195 / 3 = 65, b_{1} = 39 / 3 = 13, g_{2} = 9 / 3 = 3, r_{2} = 54 + b 1 = 54 + 13 = 67, b_{2} = ((r 1 + r 2) - 4 * b 1) / 4 = (65 + 67 - 4 * 13) / 4 = 20, g_{1} = ((r 1 + b 1 + r 2 + b 2) - 2 * g 2) / 2 = (65 + 13 + 67 + 20 - 2 * 3) / 2 = 79 / 2.

$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.$

Mas ao mesmo tempo

g_{1} + g_{2}

$g_1 + g_2$ deve ser um múltiplo de 20, o que não é verdadeiro para o valor (79,5 + 3).

Exatamente da mesma maneira que os valores "13" e "39" são eliminados. O único valor que resta para k é um. Substituindo-o, não chegamos a contradições e obtemos uma resposta.

De fato, como em nenhum lugar do problema se diz que o coeficiente de incremento linear k do componente RGB vermelho é um número inteiro, as soluções são uma família inteira, * mesmo * se assumirmos que o verde é consumido apenas em múltiplos de 1 ml e os comprimidos são consumidos por inteiro (o que também não especificado separadamente):

r_{1} = 1040 n + 195 g_{1} = 732 n + 171 b_{1} = 208 n + 39

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

r_{2} = 208 n + 93 g_{2} = 48 n + 9 b_{2} = 104 n + 33

$r_2 = 208n + 93 \\ g_2 = 48n + 9 \\ b_2 = 104n + 33 \\$
n é um número inteiro não negativo.

Para obter essa família, você precisa se livrar de k nas 3 primeiras equações reescrevendo-as, por exemplo, como:

3 r_{1} - 15 b_{1} = 0, 3 r_{1} - 65 g_{2} = 0, 15 b_{1} - 65 g_{2} = 0,

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

então resolva o sistema de equações diofantinas lineares (naturalmente, incluindo o restante das equações reduzidas à forma correta). Se não assumirmos que o verde é consumido apenas por volumes que são múltiplos de um mililitro, obtemos um sistema não-linear de equações diofantinas, utilizando g1 e g2 (que obviamente devem ser racionais) para todo o numerador e denominador desconhecido. Se resolvermos o problema em sua forma mais geral (todos os valores são contínuos), haverá ainda mais soluções.

Vencedores

É verdade que todas as tarefas foram resolvidas por Alexey Ryzhikov e Valentin Shipilov. Além disso, os prêmios foram recebidos por Alexey Galkin, Anton Blinov, Ilya Perevozchikov e vários outros participantes. Parabéns!

Sair da roda de Sansara, extremismo e um pouco de coisa verde - uma análise de tarefas do livreto GridGain na conferência Joker 2018

Tarefa 1

Tarefa 2

Tarefa 3

Vencedores

More articles: