1. Introdução
Já em outubro de 2018, recordamos com prazer o calendário do Advento com as tarefas de 2017 (as condições estão
aqui ) e começamos a pensar no que pode ser feito este ano. Entre várias idéias dignas, escolhemos uma opção na qual selecionamos diversas tarefas "cativantes", unidas por uma bela história de Ano Novo.
Não havia mais nada: na verdade, pegue tarefas, componha uma história, crie um site com uma tabela de classificação, bonito e bem unido ao Yandex.Constest e comece no início de dezembro :-)
Resultado
Como você sabe, o apetite vem da comida e mergulhámos de cabeça no processo de elaboração do conteúdo das tarefas e de sua implementação técnica. Cada descoberta bem-sucedida inspirou novas melhorias. Como resultado, criamos um servidor separado para uma das tarefas, transformamos o outro em otimização (ainda não temos uma resposta exata), gravamos a música, restauramos as distribuições - não ficamos entediados!
O resultado é:
Fatos e histórias interessantes
780 participantes registrados, 333 pessoas começaram a resolver, 203 pessoas passaram com sucesso pelo menos duas tarefas.
Inicialmente, estimamos o tempo líquido para resolver todos os problemas em sete dias para um participante despreparado e dois dias para um participante muito experiente (também conhecido como recém-formado no CS). O primeiro assistente do Papai Noel que resolveu corretamente todas as onze tarefas foi concluído cerca de um dia, mais dois conseguiram o segundo!
Carta de um dos participantes: “Boa tarde! Por causa do seu concurso, parei o escritório (40 pessoas) especificamente a segunda tarefa sobre o café do Papai Noel, me dê uma dica, por favor. Todos somos muito atormentados.
Analisando Tarefas
Termos
aqui .
Tarefa D “Mensagem Musical” (Mikhail Plotkin)É muito simples resolver o problema, tendo uma educação musical mínima.
Uma tentativa de encontrar uma pista no padrão rítmico não levou ao sucesso. A próxima idéia era sentar ao piano e tocar a música que você ouvia. Descobriu-se la, do, mi, si, la, re, sal, mi. Em uma clave de sol como esta:
Após as três primeiras notas, seguiu-se uma breve pausa, como se dividisse a frase musical em duas palavras. Restava apenas escrever notas na notação tradicional (A = la, B = si, C = do, D = pe, E = mi, F = fa, G = sal) e duas palavras abertas: ACE BADGE.
Sem nenhum conhecimento de alfabetização musical, resolver um problema é mais difícil. Por exemplo, alguém poderia usar algum programa para processar sons e descobrir as próprias notas ou as frequências dos sons em hertz e, em seguida, descobrir quais frequências correspondem a quais notas.
A tarefa necessária para escrever cartas juntas sem separadores, portanto a resposta é ACEBADGE.
Tarefa F “Saco de flocos de neve” (Mikhail Plotkin)A área do triângulo inicial é 1. Em seguida, na enésima etapa, t_n triângulos são adicionados, cada um dos quais com uma área s_n. A área total da figura resultante é expressa como a soma de uma série infinita:
S = 1 + Σ (t_n * s_n), a soma sobre n é de 0 a ∞ (1)
No passo zero, t_0 = 3, s_0 = 1/9, uma vez que o triângulo possui 3 lados, em cada um dos quais um triângulo é construído com um lado 3 vezes menor que o original e, portanto, uma área 9 vezes menor que a área do triângulo original.
A cada passo seguinte, cada lado se transforma em quatro lados três vezes menores, ou seja,
t_n = t_ {n-1} * 4 = t_0 * 4n = 3 * 4n,
s_n = s_ {n-1} * (1/9) = s_0 * (1/9) ^ n = 1/9 * (1/9) ^ n.
Portanto, a área necessária:
S = 1 + Σ (t_n * s_n) = 1 + 1/3 * Σ ((4/9) ^ n), a soma sobre n é de 0 a ∞ (2)
O segundo termo é a soma de uma progressão geométrica infinitamente decrescente. Para calcular, use a fórmula da escola
Σ ((4/9) ^ n) = 1 / (1-4/9) = 9/5.
Substituindo na fórmula (2), obtemos a resposta:
S = 1 + 1/3 * 9/5 = 8/5 = 1,6
Tarefa G e L “O percurso está construído” (Artyom Romanov)Obrigado a Artyom
mehrunesartem pela solução! A propósito, o gráfico usado no Problema G é baseado no metrô de Londres :)
Para resolver esse problema, usaremos uma versão modificada da primeira pesquisa de largura. Obtemos um vértice imaginário (fonte), a partir do qual desenhamos bordas com peso zero em cada vértice do gráfico. Cada estado é determinado exclusivamente pelo caminho transmitido da fonte. Além disso, armazenaremos o tempo gasto e a alegria recebida.
Iniciamos uma fila de prioridade com um tamanho fixo, no qual colocaremos o estado. Como uma avaliação das condições na fila, usaremos a proporção de felicidade recebida em relação ao tempo gasto. Esta avaliação não está correta, mas mostrou bons resultados nesta tarefa.
Em cada etapa, obteremos o estado com a melhor estimativa da fila e colocaremos os estados formados a partir dele na fila. Com essa abordagem, levará muito tempo para obter o resultado final.
Para acelerar a solução, procuraremos a resposta passo a passo. A cada passo, para procurar o próximo vértice no caminho, limparemos a fila e colocaremos o estado atual nela. Em seguida, executaremos um número fixo de etapas, atualizando simultaneamente o estado que proporciona a maior quantidade de alegria. Como o próximo vértice do caminho, pegamos o vértice após o último vértice do estado atual no caminho do estado resultante que dá a maior quantidade de alegria. Repetimos as ações realizadas até podermos melhorar o estado atual.
Possíveis melhorias
- Use as melhores heurísticas.
- Com esta implementação do algoritmo, estados extras aparecerão, pois a cada passo adicionaremos todos os estados que poderiam vir do atual. Para evitar isso, usando o algoritmo Dijkstra, para cada vértice do gráfico, você pode primeiro construir uma árvore de caminhos mais curtos para todos os outros vértices e fazer transições não em uma única etapa, mas ao longo da árvore construída até atingirmos os vértices em que nunca estivemos.
Essas mudanças não deram melhorias significativas, provavelmente devido ao fato de haver apenas um teste fechado e não um grupo de testes gerados diferentes.
Tarefa I “Digitalizadores de ursos” (Alexander Samofalov)Vamos dar uma olhada no
código fonte do serviço .
Uma lista de todos os IDs disponíveis para o usuário pode ser obtida em
/data .
Se houver um ID, os dados poderão ser obtidos usando uma solicitação para o endereço
/data/id .
Para acessar dados, o serviço requer um token para autenticação. Temos um
token disponível, mas ele expirou e o serviço não o aceita mais.
Vamos ver no código
como esses tokens são gerados . O token é obtido criptografando JSON no formato
{ “userId” : “id”, expireDate: “date”} e codificando-o em base64. O serviço usa o RSA para criptografia e a chave pública pode ser obtida mediante solicitação em
/key .
Vamos fazer uma solicitação: e = 30593, n = 66043. Como n é pequeno o suficiente, podemos calcular facilmente a chave privada.
Para fazer isso, decompomos n em fatores primos: 211 * 313.
Calculamos
a função de
Euler de n: φ (n) = (211 - 1) (313 - 1) = 65520.
Temos d = e-1 (mod φ (n)) = 257.
O módulo de elemento inverso pode ser calculado usando o
algoritmo avançado Euclidiano .
Depois de calcular a chave privada, descriptografamos o token disponível para nós.
{"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2018-12-06T14:38:00.898026+00:00"} o seguinte JSON:
{"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2018-12-06T14:38:00.898026+00:00"}Observe que é
suficiente que o serviço para o usuário com o userId fornecido exista e expireDate seja menor que o horário atual no servidor.
Ou seja, conhecendo userId, podemos gerar um novo token válido.
Para fazer isso, expireDate suficientemente grande para passar no teste - por exemplo
{"userId":"448f0a79-e2d8-4ccd-9009-53858914dcaa","expireDate":"2100-01-01T12:00:00.000000+00:00"} .
Criptografamos nosso novo token usando a chave pública.
Após fazer uma solicitação para
/data , descobrimos que o usuário criou mensagens com identificadores de 1 a 4.
Nós vamos resolver todos eles.
Entre eles está uma frase maravilhosa:
Ano Novo está batendo na porta, abra-a em breve! .
Dicas para resolver alguns outros problemas (de Artyom Romanov)Tarefa A “Seguro com letras”Você pode perceber que a cada vinte etapas você obterá o mesmo número.
Tarefa B “O Segredo do Professor”Ordene as palavras em ordem decrescente de popularidade. Você pode perceber que cada palavra subsequente ocorre em aproximadamente 2, 3, 4, etc. vezes menos que a palavra mais popular. Agora você pode restaurar a resposta.
Tarefa C "Desastre de Computador"Pense na linguagem de programação Whitespace.
Tarefa J "Bengala"Possível posicionamento:
Problema K “Padrão gelado”Para resolver esse problema, você pode escolher qualquer triângulo conveniente, por exemplo, o certo e calcular a resposta para ele.
Agradecimentos
Todo o processo, da ideia à implementação, foi conduzido e coordenado por Katya Lebedeva. Katya Artamonova, Alina Mozhina, Sasha Komissarov e eu a ajudamos a concluir as tarefas. Lyosha Tolstikov escreveu três damas complexas, Sasha Komissarov e Seryozha Zherevchuk criaram um servidor, Svyato e Seryozha criaram um site desinteressadamente, bonito, com forte integração com as tarefas: cada participante podia ver seu progresso e seu ranking.