2677-par-ou-impar

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.5" id: 2677 name: "Par ou Ímpar" slug: "par-ou-impar" timelimit: 1.0 memlimit: 200 difficultyLevelId: B author: "Hamilton José Brumatto" origin: "Beecrowd" description: 'Aplique Programação Dinâmica (MiniMax) sobre um array para maximizar aquisição de números pares retirados das pontas.' editorial: | Temos um clássico Minimax resolvido com Programação Dinâmica em Intervalos (DP on Arrays/Intervals). A matriz dp[i][j] guardará a diferença máxima de "Números Pares" que o primeiro a jogar consegue garantir usando o sub-vetor de i a j. Sendo S(i, j) a quantidade total de números pares no intervalo de i a j: dp[i][j] = S(i, j) - MIN( dp[i+1][j], dp[i][j-1] ) Isso ocorre porque o oponente jogará de forma ótima e garantirá o DP do subintervalo que restar para ele, roubando assim parte dos S(i, j) totais. As iterações da DP avançam ordenadas pelos tamanhos de subarray (len = 1 até 2N). successmsg: 'Brilhante! DPs de jogo em arrays costumam assustar, mas quando se nota que "O meu ganho é O que existe menos o que o oponente conseguirá ganhar" a mágica acontece.' timeComplexity: O(N^2) skills: - dp - minimax - game-theory statements: - id: a-par testScenarioLevel: A thematicSkills: - skill: dp points: 2 - skill: game-theory points: 1 testScenarios: - id: a-performance name: Carga N Máximo description: "N até 499 (Tamanho 998)." helpTip: "Você otimizou a DP para reutilizar a sub-solução em uma matriz?" level: A testType: PERFORMANCE skills: - skill: dp points: 1 - id: b-fuzzing name: Arrays Variados description: "Pares e impares embaralhados." helpTip: "Validando a lógica de que subtraímos as respostas filhas do valor total S(i, j)." level: B testType: TDD skills: - skill: minimax points: 1 - id: c-edge name: Casos Limites description: "N = 1, só um par." helpTip: "Caso base len=1 funcionando corretamente?" level: C testType: TDD skills: - skill: dp points: 1 - id: d-sample name: Exemplo do Enunciado description: "Casos de teste do problema original." helpTip: "Passe os casos de teste." level: D testType: TDD skills: - skill: basic-io points: 1 solutions: - id: a-otima-basica name: Programação Dinâmica em Arrays (Len Iteration) description: Constrói a DP de dentro pra fora em O(N^2). level: A implementations: - language: cpp paradigm: Imperative main: par.cpp filenames: - par.cpp - language: py paradigm: Imperative main: par.py filenames: - par.py - language: java paradigm: OO main: Par filenames: - Par.java authorSlugProblem: Unknown defaultStatement: a-par