Doido Dev

2025.2.17 A: Sede de Sal As operações que exigem custo adicional são executadas no máximo uma vez. Portanto, existem três cenários. O primeiro é saltar diretamente para a frente e gastar um custo extra para recuar. O segundo é não realizar nenhuma operação com custo adicional; ambos são simples. No primeiro caso, basta consultar o mínimo de pre ...

Problema Eva adora colecionar moedas de todo o universo, incluindo outros planetas como Marte. Um dia, ela visitou um shopping universal que aceitava todos os tipos de moedas como pagamento. No entanto, havia um requisito especial: para cada conta, ela deve pagar o valor exato. Como ela tem até 10^4 moedas, ela definitivamente precisa da sua aj ...

Problema da Mochila 0/1 (0-1 Knapsack) No cenário clássico da mochila 0/1, dispomos de $N$ itens e uma mochila com capacidade máxima $V$. Cada item possui um volume $v_i$ e um valor $w_i$. A restrição fundamental é que **cada item pode ser escolhido apenas uma vez**. O objetivo é maximizar o valor total sem exceder a capacidade $V$. ### Defi ...

Resolvendo o Problema do Triângulo Numérico com Programação Dinâmica O problema do Triângulo Numérico é um exercício fundamental em Programação Dinâmica (PD). Consiste em uma estrutura triangular de números, onde o objetivo é determinar o caminho de cima para baixo que resulta na maior soma, movendo-se apenas para as células adjacentes na linha ...

Problemas de Programação Competitiva: Contagem de Inversões Neste artigo, exploraremos soluções para problemas de contagem de inversões, abordando tanto abordagens diretas quanto soluções otimizadas usando programação dinâmica com soma de prefixos. Problema 1: Contagem de Inversões (P1521) O problema consiste em encontrar o número de permutaçõe ...

A programação dinâmica (PD) possui diversas técnicas de otimização, sendo uma das mais importantes a utilização de árvores de segmentos. Este artigo apresenta os tipos mais comuns desse método, seus padrões e alguns exemplos práticos. Pré-requisitos: Programação dinâmica linear e conhecimento sobre árvores de segmentos. Definições Para facilita ...

Tópicos Diversos DP com transição linear entre estados Inicialização Inicializar todos os estágios conforme o contexto do problema DP sobre Subconjuntos Iteração sobre submáscaras para DP em conjuntos DP de Dígitos Dependência com dígitos anteriores Independência entre dígitos DP Matricial Definição da matriz base, matriz de transição ...

Este problema envolve determinar se uma terceira string é formada pela intercalação de caracteres de duas outras strings, mantendo a ordem original dos caracteres dentro de cada uma das duas primeiras strings. Por exemplo, "cat" e "tree" podem formar "cattree", mas não "tretac". Uma abordagem inicial para ...

\(100+100+40+0\), T3 não otimizado corretamente resultou em \(20\) pontos perdidos. Posteriormente, descobri que durante a competição, a solução para T3 tinha complexidade de tempo e correção corretas, apenas com uma grande contsante que me fez achar que não executaria dentro do tempo limite. A. Conjunto A resposta satisfaz a propriedade monóto ...

Fundametnos de Grafos Bipartidos Um grafo é bipartido se e somente se não contém ciclos de comprimento ímpar. Um método eficiente para verificar essa propriedade é a coloração por busca em profundidade (DFS). A ideia é tentar atribuir dois rótulos (0 ou 1) aos vértices de modo que vértices adjacentes tenham rótulos diferentes. Se em algum momen ...