0643-pontes-de-sao-petersburgo

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.5" id: 643 name: "Pontes de São Petersburgo" slug: "pontes-de-sao-petersburgo" timelimit: 1.0 memlimit: 256 difficultyLevelId: D author: OBI Clássico / Unknown origin: Mundo do Código description: 'Encontre um subconjunto de regiões onde a soma dos graus seja exatamente igual a K.' editorial: | O problema pede para verificar se existe um subconjunto de vértices $S$ tal que a soma dos graus desses vértices seja exatamente $K$. Cada ponte conectando $u$ e $v$ contribuirá 1 para a soma se apenas um extremo for escolhido e 2 se ambos forem escolhidos. Trata-se de um Subset Sum sobre os graus dos vértices. Como $R \le 100$ e $K \le \frac{R(R-1)}{2} \le 4950$, uma Programação Dinâmica simples 1D resolve o problema em $O(R \times K)$. successmsg: 'Isso aí! Subset Sum com graus dos vértices, ótimo uso de DP.' timeComplexity: O(R * K) skills: - dp - subset-sum - graphs statements: - id: a-pontes testScenarioLevel: A thematicSkills: - skill: graphs points: 1 - skill: dp points: 2 testScenarios: - id: a-performance name: Teste de Desempenho description: Casos máximos onde R=100 e K próximo a 4950. helpTip: 'Atenção aos limites máximos. Use DP iterativa ou com memoização eficiente.' level: A testType: PERFORMANCE skills: - skill: dp points: 2 - id: b-fuzzing name: Fuzzing Aleatório description: Casos aleatórios variando tamanho de R e quantidade K. helpTip: 'Verifique se não está acessando fora dos limites do array de DP.' level: B testType: TDD skills: - skill: graphs points: 1 - id: c-edge name: Casos Extremos description: Grafos desconexos, ciclos completos, estrela e mínimo (R=2). helpTip: 'Funciona corretamente quando nem todo mundo está conectado?' level: C testType: TDD skills: - skill: graphs points: 1 - id: d-sample name: Exemplos do Enunciado description: Casos de teste presentes no PDF. helpTip: 'Sua solução deve passar no exemplo básico.' level: D testType: TDD skills: - skill: basic-io points: 1 solutions: - id: a-otima-basica name: DP 1D (Mochila) description: Resolve Subset Sum em O(R*K) com espaço otimizado O(K). level: A implementations: - language: cpp paradigm: Imperative main: pontes.cpp filenames: - pontes.cpp - language: py paradigm: Imperative main: pontes.py filenames: - pontes.py - language: java paradigm: OO main: Pontes filenames: - Pontes.java - id: b-subotima-basica name: DP 2D Inteira description: Solução sub-ótima em memória (O(R*K)) mas que resolve no tempo hábil. level: B implementations: - language: py paradigm: Imperative main: subotima.py filenames: - subotima.py authorSlugProblem: Unknown