3010-dna-dinossauro

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: '1.0' id: 3010 name: DNA Dinossauro origin: wok slug: dna-dinossauro authorSlugEditorial: alessio authorSlugProblem: alessio description: Neste laboratório de bioinformática, sua missão é comparar o código genético de duas espécies de dinossauros para descobrir o quão próximas elas são evolutivamente. O desafio é calcular o tamanho da maior cadeia de DNA que ambas as espécies compartilham em comum, mantendo a ordem original, mas sem a necessidade de que as bases nitrogenadas sejam contíguas. Um problema clássico para testar suas habilidades algorítmicas de alinhamento em strings. editorial: "**Professor's Briefing:**\r\nEste problema exige que o aluno conheça o conceito de Programação Dinâmica bidimensional\ \ (matrizes de preenchimento bottom-up). É considerado o \"Hello World\" da PD em strings, encaixando-se perfeitamente no\ \ início de qualquer módulo de algoritmos avançados, logo após o ensino de recursão. A dificuldade é intermediária (Nível\ \ C), servindo como pré-requisito absoluto para desafios de grafos ou strings como Shortest Common Supersequence e Edit\ \ Distance.\r\n\r\n**Strategy Summary:**\r\nO cerne (key insight) do problema é a clássica Longest Common Subsequence (LCS).\ \ Dada a impossibilidade de testar as $2^N$ combinações de força bruta, aplicamos uma técnica de Programação Dinâmica matricial.\ \ A matriz `DP[i][j]` constrói a resposta ótima iterativamente usando duas transições lógicas sobre o final de cada prefixo:\ \ se houver um \"Match\" entre as bases nitrogenadas, somamos +1 ao valor da diagonal (`1 + DP[i-1][j-1]`). Se for um \"\ Mismatch\", propagamos a melhor solução vizinha ignorando um dos caracteres iterados (`max(DP[i-1][j], DP[i][j-1])`). A\ \ complexidade desta travessia dupla cai vertiginosamente para O(N * M), suportando perfeitamente fitas de DNA de até 1000\ \ caracteres. For full implementation details, refer to the level-D statement.\r\n" successmsg: Genial! Você alinhou as fitas de DNA dominando a técnica de Longest Common Subsequence (LCS) e Programação Dinâmica com otimização de espaço! O Jurassic Park é logo ali! difficultyLevelId: C timeComplexity: O(N × M) timeLimitSegs: 1 memoryLimitMb: 256 defaultStatement: b_pt_dna-dinossauro.pdf skills: - dp-space-optimization - dp-tabulation - dynamic-programming - longest-common-subsequence statements: - id: a-dna-dinossauro testScenarioLevel: A thematicSkills: - points: 1 skill: biology testScenarios: - id: d-sample name: Sample description: Exemplo básico do enunciado. helpTip: Você pode resolver este caso base manualmente cruzando as letras no papel. level: D testType: TDD skills: - skill: dynamic-programming points: 1 - skill: longest-common-subsequence points: 1 - id: c-no-match name: Nenhum Match description: As fitas de DNA não possuem absolutamente nenhum caractere em comum. helpTip: O que sua matriz retorna quando não há como realizar a transição de match? Verifique sua inicialização. level: C testType: TDD skills: - skill: dp-tabulation points: 1 - skill: longest-common-subsequence points: 1 - id: c-identical name: Fitas Idênticas description: As duas sequências de DNA são perfeitamente idênticas. helpTip: Sua diagonal principal deve carregar o valor até o final sem problemas. level: C testType: TDD skills: - skill: dynamic-programming points: 1 - skill: dp-tabulation points: 1 - id: b-greedy-trap name: Armadilha Gulosa (Greedy Trap) description: Padrão criado para derrubar algoritmos gulosos que dão match na primeira letra que encontram sem avaliar o fluxo ótimo futuro. helpTip: 'Atenção: uma letra pode casar com múltiplas posições. Um algoritmo guloso errará este caso. Use DP.' level: B testType: TDD skills: - skill: longest-common-subsequence points: 1 - skill: dynamic-programming points: 1 - id: b-fuzzing name: Fuzzing Test description: Teste de fuzzing com letras aleatórias. helpTip: Verificação cega contra heurísticas harcoded. level: B testType: TDD skills: - skill: dp-tabulation points: 1 - skill: dynamic-programming points: 1 - id: a-performance-load name: Maximum Performance Load description: Carga máxima da matriz (1000 x 1000). helpTip: Se você estiver usando recursão sem memoização ou uma abordagem O(2^N), você receberá Time Limit Exceeded aqui. level: A testType: PERFORMANCE skills: - skill: dp-space-optimization points: 2 - skill: longest-common-subsequence points: 1 solutions: - id: a-optimal-dp name: Programação Dinâmica O(N*M) description: Solução ideal utilizando DP bidimensional com otimização de espaço para vetor 1D. level: A implementations: - filenames: - optimal_dp.py language: py paradigm: Imperative - filenames: - optimal_dp.cpp language: cpp paradigm: Imperative - filenames: - OptimalDp.java language: java paradigm: Imperative main: OptimalDp - id: b-recursive name: Recursão Ingênua O(2^N) description: Solução ineficiente por busca completa. Falhará por Time Limit Exceeded em matrizes maiores devido a sobreposição de subproblemas. level: B implementations: - filenames: - recursive_tle.py language: py paradigm: Imperative