A Regra Prática de 10^8
Relacione a quantidade de operações ao limite de tempo.
A Regra Prática de 10^8 é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 2 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.
O orçamento mágico
Um juiz on-line típico executa cerca de 10^8 operações simples por segundo. Esse número é seu orçamento de tempo para o programa inteiro. 💡
Das etapas aos segundos
Multiplique sua contagem de operações pelo trabalho de cada etapa e compare o resultado com o limite de tempo. Se as etapas couberem no orçamento, é provável que sua solução seja aceita.
O linear é barato
Uma varredura O(n) sobre n = 10^6 tem apenas um milhão de etapas, muito abaixo do orçamento. Soluções lineares quase sempre passam com folga.
n log n é seguro
Para n = 10^6, uma ordenação O(n log n) executa cerca de 2 vezes 10^7 etapas. Isso ainda fica bem dentro do orçamento de um segundo, portanto a ordenação raramente é o gargalo.
O quadrático tem um limite
Uma abordagem O(n^2) atinge o orçamento perto de n = 10^4, quando custa 10^8 etapas. A partir daí, o quadrático começa a exceder o limite de tempo.
O cúbico só funciona para valores pequenos
Uma solução O(n^3) sobrevive apenas até cerca de n = 500. Elevando esse valor ao cubo, você chega a aproximadamente 10^8 etapas, no limite do orçamento.
O exponencial permanece pequeno
O(2^n) dobra a cada etapa, portanto só funciona para valores muito pequenos de n, em torno de 20 a 25. Depois disso, a contagem de operações explode e ultrapassa 10^8.
Python tem um custo adicional
Python é mais lento por etapa, portanto considere o orçamento mais próximo de 10^7 em laços apertados. Seja conservador quando as restrições parecerem estar no limite.
Considere a constante oculta
A regra de 10^8 conta etapas simples. Trabalho pesado dentro de um laço, como construir uma sequência de caracteres, acrescenta um fator constante que reduz seu orçamento real.
Leia o limite
O limite de tempo costuma ser de 1 ou 2 segundos. Um limite de 2 segundos aproximadamente dobra seu orçamento, oferecendo um pouco mais de margem.
Estime antes de programar
Sempre substitua n na sua complexidade e compare primeiro com 10^8. Essa rápida verificação de plausibilidade evita que você programe uma solução fadada ao fracasso.
Verificação rápida
Coloque a regra de 10^8 em prática.
Recapitulação
Agora você relaciona operações ao tempo: aproximadamente 10^8 por segundo. Soluções lineares e n log n são seguras, as quadráticas chegam ao limite perto de 10^4, e você verifica tudo antes de programar. ✅
Perguntas Frequentes
A aula “A Regra Prática de 10^8” é grátis?
Sim — o texto completo de “A Regra Prática de 10^8” é 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 “A Regra Prática de 10^8”?
Relacione a quantidade de operações ao limite de tempo. 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 2 de 4.
Quanto tempo leva a aula “A Regra Prática de 10^8”?
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
- Contando Operações com Big-O
- A Regra Prática de 10^8
- Leia as Restrições e Escolha a Complexidade
- Por que TLE Acontece e Como Identificá-lo