Encontro no Meio
Reduza pela metade o expoente dividindo a busca.
Encontro no Meio é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
Quando a força bruta é lenta demais
Alguns problemas têm N próximo de 40, e tentar todos os 2^N subconjuntos é inviável. O encontro no meio resolve esses casos de tamanho intermediário. 🤝
A ideia central
Divida a entrada em duas metades. Resolva cada metade por força bruta e depois combine de maneira inteligente os dois resultados parciais.
Reduzindo o expoente pela metade
Duas metades de tamanho N/2 custam 2^(N/2) cada, em vez de 2^N no total. Essa redução pela raiz quadrada transforma 2^40 em um 2^20 viável.
Um alvo clássico: soma de subconjuntos
Verifique se algum subconjunto soma um alvo T. A soma de subconjuntos com N próximo de 40 é o problema clássico do encontro no meio.
Enumerando a primeira metade
Liste cada soma de subconjunto da metade esquerda e armazene-as. Com N/2 itens, são apenas 2^(N/2) somas.
from itertools import combinations
left = arr[:len(arr)//2]
sums_l = []Enumerando a segunda metade
Faça o mesmo para a metade direita, construindo sua lista completa de somas de subconjuntos. Agora você tem duas listas gerenciáveis.
Combinando com uma consulta
Para cada soma direita r, você precisa de uma soma esquerda igual a T menos r. Um conjunto ou uma lista ordenada torna essa verificação rápida.
need = T - r
found = need in left_setDuas maneiras de encontrar correspondências
Para alvos exatos, use um conjunto de dispersão. Para contar ou encontrar somas mais próximas, ordene uma metade e faça uma pesquisa binária nela.
O custo temporal
O trabalho total é aproximadamente 2^(N/2) vezes um fator logarítmico para a pesquisa ou ordenação. Essa complexidade é o que torna viável trabalhar com N próximo de 40.
A memória é o custo da troca
Você armazena uma metade inteira, então a memória cresce para 2^(N/2). Mantenha apenas o que for necessário para respeitar o limite.
Onde mais ela brilha
Além da soma de subconjuntos, use essa técnica para encontrar o maior subconjunto sob um limite, contar pares e resolver problemas no estilo do logaritmo discreto. Ela funciona muito bem com uma divisão bem escolhida.
Verificação rápida
Você aplica o encontro no meio a um problema de subconjuntos com N itens. Qual é o custo temporal aproximado?
Recapitulação
Divida em duas metades, resolva cada uma por força bruta e depois associe as somas da esquerda e da direita. Você trocou um pouco de memória por um enorme ganho de velocidade. 🚀
Aprenda Python com um tutor de IA — grátis
Escreva e execute código real no seu navegador, obtenha ajuda instantânea de um tutor de IA 24/7 e continue de onde parou na web ou no app.
- Cursos
- 30
- Aulas
- 120
Perguntas Frequentes
A aula “Encontro no Meio” é grátis?
Sim — o texto completo de “Encontro no Meio” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Encontro no Meio”?
Reduza pela metade o expoente dividindo a busca. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Encontro no Meio”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Estados Vencedores e Perdedores em Jogos
- Nim e o Número de Grundy
- Encontro no Meio
- Depure Rapidamente: Testes de Estresse e Triagem