0806-dabriel-e-suas-strings

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: '1.0' id: 806 idBeecrowd: 2842 name: Dabriel e Suas Strings origin: beecrowd slug: dabriel-e-suas-strings authorSlugEditorial: alessio authorSlugProblem: gabriel-duarte description: Neste problema, você ajudará Dabriel a determinar o tamanho da menor string que contém duas outras strings dadas como subsequência. Essencialmente, o desafio consiste em encontrar a menor supersequência comum (Shortest Common Supersequence) entre as duas palavras informadas. editorial: 'Este problema requer conhecimento prévio em Programação Dinâmica e processamento de strings. É um excelente exercício pedagógico para treinar a formulação de estados de recorrência bidimensionais e a modelagem do clássico problema da Longest Common Subsequence (LCS). Dada a sua natureza, encaixa-se perfeitamente no nível Intermediário de algoritmos, ideal para módulos de otimização em cursos de graduação. A estratégia principal consiste em perceber que o tamanho da menor supersequência comum (SCS) é exatamente a soma dos comprimentos das duas strings subtraído da quantidade de caracteres que ambas compartilham na mesma ordem (a LCS). Ao calcular a LCS através de uma matriz `dp[i][j]` em tempo O(|A| * |B|), podemos aplicar a fórmula `|A| + |B| - LCS(A, B)`. Como o limite de tamanho é 1000, essa complexidade é aceitável para o tempo limite estipulado. For full implementation details, refer to the level-D statement.' successmsg: Excelente! Você estruturou perfeitamente a programação dinâmica para resolver a Shortest Common Supersequence. difficultyLevelId: C timeComplexity: O(N × M) spaceComplexity: O(N × M) timeLimitSegs: 1 defaultStatement: a_pt_dabriel-e-suas-strings.md skills: - longest-common-subsequence - dp-tabulation - strings statements: - id: a-dabriel-e-suas-strings testScenarioLevel: A thematicSkills: - skill: daily-life points: 1 testScenarios: - id: d-sample name: Sample description: Entrada Básica de exemplo do exercício. helpTip: Hm... algo deu errado, você está escrevendo certo? level: D testType: TDD skills: - skill: longest-common-subsequence points: 1 - skill: strings points: 1 - id: c-edge-cases name: Casos Extremos description: Strings totalmente disjuntas ou idênticas. helpTip: Verifique se as matrizes processam corretamente interseções nulas (LCS = 0) ou strings perfeitamente iguais. level: C testType: TDD skills: - skill: longest-common-subsequence points: 1 - id: b-greedy-breaker name: Quebra-Gulosos description: Testes criados especificamente para forçar falha em heurísticas gulosas de casamento direto. helpTip: Se o seu algoritmo simplesmente casa a primeira letra comum que encontra, ele pode perder uma sequência maior escondida logo à frente. É necessário avaliar todas as ramificações. level: B testType: TDD_FALSE_GREEN skills: - skill: longest-common-subsequence points: 1 - id: a-performance-load name: Teste de Carga O(N*M) description: Strings de tamanho máximo (1000) para derrubar complexidades O(2^N). helpTip: Uma árvore de recursão simples vai estourar o Time Limit. Alocação em grade DP é mandatória. level: A testType: PERFORMANCE skills: - skill: dp-tabulation points: 2 solutions: - id: a-otima-basica name: Solução Completa O(N * M) description: Soluções ótimas baseadas em LCS para Shortest Common Supersequence. level: A implementations: - filenames: - solucao.cpp language: cpp paradigm: Imperative - filenames: - optimal.py language: py paradigm: Imperative - filenames: - OptimalSCS.java language: java paradigm: Imperative main: OptimalSCS - filenames: - DabrielESuasStringsMain.java language: java paradigm: Imperative main: DabrielESuasStringsMain - id: b-greedy name: Heurística Gulosa description: Solução que tenta parear os caracteres gulosamente da esquerda para a direita. Vai falhar nos casos específicos (greedy breakers). level: B implementations: - filenames: - greedy.py language: py paradigm: Imperative