0640-invertendo-setas

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "1.0" id: 640 idBeecrowd: 2576 name: "Invertendo Setas" origin: "mineira-2017" slug: "invertendo-setas" authorSlugEditorial: "alessio" authorSlugProblem: "dâmi-henrique" description: "Bibi e Bibika jogam um jogo num tabuleiro formado por círculos e setas direcionadas. O objetivo é descobrir qual das duas precisa inverter a menor quantidade de setas para encontrar um caminho válido de A até B (Bibi) ou de B até A (Bibika). O aluno deve calcular o número mínimo de inversões necessárias em cada sentido e determinar a vencedora ou se houve empate." editorial: | **Professor's Briefing** Este problema é ideal para fixar conceitos de teoria dos grafos, especificamente a busca de caminhos mínimos em cenários com custos restritos. O aluno precisa estar confortável com representação de grafos direcionados e algoritmos de travessia clássicos. É uma excelente oportunidade para introduzir ou praticar a técnica de BFS 0-1, sendo classificado como especialista (nível B) e encaixando-se perfeitamente em módulos de Algoritmos em Grafos. **Strategy Summary** A chave é modelar a "inversão de setas" como o custo de atravessar uma aresta num grafo direcionado. Para cada seta U -> V, adicionamos uma aresta U -> V com custo 0 e uma aresta invertida V -> U com custo 1. O problema se reduz a encontrar o caminho mais barato de A para B e de B para A. Como os pesos são apenas 0 e 1, a abordagem ótima com complexidade O(C + S) usa uma BFS 0-1 (com Deque). O algoritmo de Dijkstra clássico, com complexidade O(S log C), também resolverá eficientemente as instâncias do problema. For full implementation details, refer to the level-D statement. successmsg: "Incrível! Você dominou os algoritmos de caminhos mínimos e encontrou a vencedora com sucesso!" difficultyLevelId: "B" timeComplexity: "O(C + S)" spaceComplexity: "O(C + S)" timeLimitSegs: 2 memoryLimitMb: 256 defaultStatement: "b_pt_invertendo-setas.pdf" skills: - "grafos" - "busca-largura" - "shortest-path" - "dijkstra" statements: - id: "a-invertendo-setas" testScenarioLevel: "A" thematicSkills: - points: 1 skill: "games" testScenarios: - id: "d-sample" name: "Exemplos" description: "Casos de teste de exemplo do enunciado." helpTip: "Verifique se a sua solução passa nos exemplos dados." level: "D" testType: "TDD" skills: - skill: "grafos" points: 1 - id: "c-simples" name: "Casos Simples" description: "Testes pequenos com poucos vértices e arestas, fáceis de rastrear manualmente." helpTip: "A lógica básica para grafos simples está correta?" level: "C" testType: "TDD" skills: - skill: "busca-largura" points: 1 - id: "c-edge-cases" name: "Casos Limites" description: "Testa situações extremas: ausência de caminhos, vértices A e B iguais, ou arestas repetidas." helpTip: "Você tratou o empate quando é impossível chegar ao destino (Bibibibika)? E quando A = B?" level: "C" testType: "TDD" skills: - skill: "shortest-path" points: 1 - id: "c-arestas-repetidas" name: "Multigrafos e Arestas Repetidas" description: "Casos em que existem múltiplas arestas direcionadas para o mesmo vértice, testando redundância." helpTip: "Você considerou o caminho ótimo mesmo existindo múltiplas arestas entre os mesmos nós?" level: "C" testType: "TDD" skills: - skill: "grafos" points: 1 - id: "c-nenhuma-inversao" name: "Nenhuma Inversão" description: "Casos em que o caminho já existe perfeitamente da origem ao destino sem inverter nenhuma seta." helpTip: "A sua contagem inicia corretamente do 0? E processa o empate em 0 de ambos lados?" level: "C" testType: "TDD" skills: - skill: "shortest-path" points: 1 - id: "c-todas-inversoes" name: "Todas as Inversões" description: "Casos em que absolutamente todas as arestas do caminho precisam ser invertidas para se chegar ao destino." helpTip: "A soma das inversões atinge o máximo permitido corretamente sem ignorar a última aresta?" level: "C" testType: "TDD" skills: - skill: "busca-largura" points: 1 - id: "b-fuzzing" name: "Comportamento Randômico (Fuzzing)" description: "Simula cenários aleatórios não padronizados para quebrar heurísticas fracas e ciclos longos." helpTip: "O seu código se perde em ciclos ou lida bem com múltiplos caminhos aleatórios?" level: "B" testType: "TDD" skills: - skill: "dijkstra" points: 1 - id: "a-performance-load" name: "Carga de Performance" description: "Testa os limites máximos: 10.000 vértices e 500.000 arestas para garantir complexidade O(S log C) ou melhor." helpTip: "Algoritmos O(V^2) resultarão em Time Limit Exceeded. Você usou uma fila de prioridades adequada?" level: "A" testType: "PERFORMANCE" skills: - skill: "dijkstra" points: 2 solutions: - id: "a-optimal-dijkstra" name: "Solução Principal (Dijkstra/BFS 0-1)" description: "Solução que implementa o algoritmo de caminho mínimo para determinar a menor quantidade de setas invertidas, executando em tempo eficiente O(V+E) ou O(E log V)." level: "A" implementations: - filenames: - "dijkstra_optimal.java" language: "java" paradigm: "OO" main: "dijkstra_optimal" - filenames: - "dijkstra_optimal.py" language: "py" paradigm: "Imperative" - filenames: - "dijkstra_optimal.cpp" language: "cpp" paradigm: "Imperative" - id: "b-suboptimal-bellman" name: "Solução Subótima (Bellman-Ford)" description: "Solução correta logicamente usando Bellman-Ford O(V*E), porém ineficiente e propensa a dar Time Limit Exceeded em grafos muito grandes." level: "B" implementations: - filenames: - "bellman_ford.py" language: "py" paradigm: "Imperative"