Nove partes de algoritmos, e então esta. Ela vem por último porque é a parte que ninguém quer até que algo já tenha falhado — uma solução comprovadamente correta, que passa em todos os testes que você escreveu, e que o juiz rejeita por tempo.
Em C#, a causa muitas vezes não é o algoritmo.
Todo programa abaixo é completo, foi rodado no .NET 10, e a saída está colada da execução. Quando um número é um tempo e não uma contagem, ele vem de uma execução em uma máquina e está ali pela proporção, não pelo valor.
Padrão 46 — Lendo a entrada
Console.ReadLine() dentro de um laço é a razão mais comum de uma solução C# correta ser lenta demais. Ele passa por um TextReader sincronizado e produz um objeto string por linha. Depois Split(' ') produz mais uma string por token.
Três formas de ler 300,000 inteiros:
Um Span<T> é um ponteiro e um tamanho apontando para memória que já existe. Fatiar um span é aritmética; fatiar um array com a mesma sintaxe [a..b] aloca e copia.
using System.Text;
// A deterministic input: 300,000 numbers on one line, built in memory so this
// program is self-contained.
var rng = new Random(7);
var sb = new StringBuilder();
int n = 300_000;
for (int i = 0; i < n; i++) { if (i > 0) sb.Append(' '); sb.Append(rng.Next(1, 1_000_000_000)); }
string line = sb.ToString();
byte[] bytes = Encoding.ASCII.GetBytes(line);
static long Measure(string name, Func<long> parse)
{
long before = GC.GetTotalAllocatedBytes(precise: true);
long sum = parse();
long allocated = GC.GetTotalAllocatedBytes(precise: true) - before;
Console.WriteLine($"{name,-22} sum={sum} allocated {allocated / 1024 / 1024,4} MB");
return sum;
}
// 1. What everyone writes. One string object per token.
long a = Measure("Split + int.Parse", () =>
{
long sum = 0;
foreach (string tok in line.Split(' ')) sum += int.Parse(tok);
return sum;
});
// 2. Same shape, but int.Parse accepts a ReadOnlySpan<char>, so no substrings.
long b = Measure("Span, no substrings", () =>
{
ReadOnlySpan<char> span = line;
long sum = 0;
foreach (Range r in span.Split(' ')) sum += int.Parse(span[r]);
return sum;
});
// 3. Read the bytes and build the number by hand. Nothing is allocated at all.
long c = Measure("bytes, hand-parsed", () =>
{
long sum = 0;
int i = 0;
while (i < bytes.Length)
{
while (i < bytes.Length && bytes[i] == ' ') i++;
int x = 0;
while (i < bytes.Length && bytes[i] >= '0' && bytes[i] <= '9') x = x * 10 + (bytes[i++] - '0');
sum += x;
}
return sum;
});
Console.WriteLine($"\nall three agree: {a == b && b == c}");Ele imprime:
Split + int.Parse sum=149553782500880 allocated 17 MB
Span, no substrings sum=149553782500880 allocated 0 MB
bytes, hand-parsed sum=149553782500880 allocated 0 MB
all three agree: TrueDezessete megabytes de lixo, ou nenhum, para o mesmo trabalho e a mesma resposta.
Tempos da mesma comparação nesta máquina: Split uns 55 ms, a versão com span uns 38 ms, os bytes parseados na mão uns 17 ms. Ler um número por linha com Console.ReadLine em vez de uma linha longa levou uns 40 ms contra 18 ms com buffer.
A opção do meio merece atenção porque adotá-la é quase de graça. int.Parse aceita um ReadOnlySpan<char> desde o .NET Core 2.1, e MemoryExtensions.Split devolve valores Range em vez de strings. Trocar string por ReadOnlySpan<char> e indexar com o range elimina toda substring.
O leitor de bytes é o que vale manter num template. São vinte linhas, ele nunca aloca, e não se importa com o espaçamento da entrada.
Use quando a entrada tiver mais que alguns milhares de tokens. Abaixo disso, escreva o que for mais claro.
Padrão 47 — Span<T> e stackalloc
Span<T> é um ponteiro e um tamanho. Fatiar um span é aritmética. Fatiar um array com a mesma sintaxe [a..b] aloca um novo array e copia.
stackalloc coloca um buffer pequeno, de tamanho fixo, na stack. Sem alocação, sem garbage collection, e ele some quando o método retorna.
// stackalloc puts a small array on the STACK. No allocation, no GC, and it
// disappears when the method returns. Bounded sizes only — this is not for
// anything that depends on input size.
static int LongestUniqueRun(string s)
{
Span<int> lastSeen = stackalloc int[128]; // ASCII, fixed size, no heap
lastSeen.Fill(-1);
int lo = 0, best = 0;
for (int r = 0; r < s.Length; r++)
{
int prev = lastSeen[s[r]];
if (prev >= lo) lo = prev + 1; // the guard from part 2
lastSeen[s[r]] = r;
best = Math.Max(best, r - lo + 1);
}
return best;
}
// A Span slice is a VIEW. No copy is made, so this allocates nothing at all.
static long SumOfHalves(int[] data)
{
ReadOnlySpan<int> all = data;
ReadOnlySpan<int> left = all[..(all.Length / 2)];
ReadOnlySpan<int> right = all[(all.Length / 2)..];
long a = 0, b = 0;
foreach (int x in left) a += x;
foreach (int x in right) b += x;
return a + b;
}
int[] data = [.. Enumerable.Range(1, 1_000_000)];
long before = GC.GetTotalAllocatedBytes(precise: true);
Console.WriteLine($"longest unique run in \"abcabcbb\": {LongestUniqueRun("abcabcbb")}");
Console.WriteLine($"longest unique run in \"abba\" : {LongestUniqueRun("abba")}");
Console.WriteLine($"sum via span slices : {SumOfHalves(data):N0}");
long after = GC.GetTotalAllocatedBytes(precise: true);
Console.WriteLine($"allocated by all of the above : {after - before} bytes");
// The array version of the same slicing DOES copy.
before = GC.GetTotalAllocatedBytes(precise: true);
int[] copy = data[..(data.Length / 2)];
after = GC.GetTotalAllocatedBytes(precise: true);
Console.WriteLine($"\nint[] range operator copies : {(after - before) / 1024 / 1024} MB for {copy.Length:N0} ints");
Console.WriteLine($"the same slice as a Span : 0 bytes — it is a pointer and a length");Ele imprime:
longest unique run in "abcabcbb": 3
longest unique run in "abba" : 2
sum via span slices : 500,000,500,000
allocated by all of the above : 8344 bytes
int[] range operator copies : 1 MB for 500,000 ints
the same slice as a Span : 0 bytes — it is a pointer and a lengthA tabela de frequências é o uso do dia a dia. Um new int[128] dentro de uma função chamada cem mil vezes são cem mil alocações; stackalloc int[128] não é nenhuma.
O tamanho tem que ser uma constante pequena. O espaço da stack é cerca de 1MB por padrão — o mesmo orçamento que limitou a profundidade da recursão na parte 7 — então stackalloc em qualquer coisa que cresce com a entrada é como transformar um programa lento num programa morto.
E repare nas duas últimas linhas. data[..500000] num int[] copiou um megabyte. A expressão idêntica num ReadOnlySpan<int> não copiou nada. Mesma sintaxe, custo completamente diferente, e nada no código deixa isso visível.
Use quando precisar de um buffer pequeno e fixo dentro de uma função quente, ou quando estiver fatiando e só lendo.
Padrão 48 — Overflow
A aritmética do C# é unchecked por padrão. O overflow não lança nada; ele dá a volta, em silêncio, como comportamento definido.
A aritmética do C# é unchecked por padrão. Overflow não é um erro, é comportamento definido que dá a volta — e por isso a falha aparece longe da linha que a causou.
// 1. The classic binary-search overflow.
int lo = 2_000_000_000, hi = 2_100_000_000;
Console.WriteLine($"(lo + hi) / 2 = {(lo + hi) / 2} <- negative, and silently so");
Console.WriteLine($"lo + (hi - lo) / 2 = {lo + (hi - lo) / 2} <- correct");
// 2. Summing ints into an int.
int[] big = [.. Enumerable.Repeat(500_000_000, 6)];
int sumInt = 0;
foreach (int x in big) sumInt += x;
long sumLong = 0;
foreach (int x in big) sumLong += x;
Console.WriteLine($"\nsix values of 500,000,000");
Console.WriteLine($" into an int : {sumInt,20:N0}");
Console.WriteLine($" into a long : {sumLong,20:N0}");
// 3. C# does NOT check by default. It will if you ask.
try
{
checked { int bad = int.MaxValue; bad++; Console.WriteLine(bad); }
}
catch (OverflowException)
{
Console.WriteLine($"\nchecked { "{" } int.MaxValue + 1 { "}" } threw OverflowException");
}
int quiet = int.MaxValue;
unchecked { quiet++; }
Console.WriteLine($"unchecked int.MaxValue + 1 = {quiet} (this is the default)");
// 4. The limits, for reference.
Console.WriteLine($"\nint max {int.MaxValue,26:N0} about 2.1 x 10^9");
Console.WriteLine($"long max {long.MaxValue,26:N0} about 9.2 x 10^18");
Console.WriteLine($"\n1000 * 1000 * 1000 * 4 as int = {unchecked(1000 * 1000 * 1000 * 4)}");
Console.WriteLine($"1000L * 1000 * 1000 * 4 = {1000L * 1000 * 1000 * 4:N0}");Ele imprime:
(lo + hi) / 2 = -97483648 <- negative, and silently so
lo + (hi - lo) / 2 = 2050000000 <- correct
six values of 500,000,000
into an int : -1,294,967,296
into a long : 3,000,000,000
checked { int.MaxValue + 1 } threw OverflowException
unchecked int.MaxValue + 1 = -2147483648 (this is the default)
int max 2,147,483,647 about 2.1 x 10^9
long max 9,223,372,036,854,775,807 about 9.2 x 10^18
1000 * 1000 * 1000 * 4 as int = -294967296
1000L * 1000 * 1000 * 4 = 4,000,000,000Três hábitos saem dessa saída.
Escreva lo + (hi - lo) / 2. Toda busca binária da parte 4 usou isso. (lo + hi) / 2 é correto para valores pequenos e produz um índice negativo para os grandes.
Some dentro de um long. Seis valores que cabem folgados num int não têm uma soma que cabe. O tipo do acumulador é o que importa, não o dos elementos.
Faça o cast antes de multiplicar, não depois. (long)a * b alarga a primeiro, então a multiplicação acontece em 64 bits. (long)(a * b) faz a multiplicação em int, dá overflow, e depois alarga a resposta errada.
A regra prática: int acaba um pouco depois de dois bilhões. Se qualquer valor intermediário puder chegar lá — e um produto de dois valores perto de 10⁵ já chega — use long. Não custa nada num runtime de 64 bits.
checked { } é útil enquanto você depura, para fazer o overflow se anunciar na linha que o causou em vez de lá adiante.
Padrão 49 — Aritmética modular
Respostas “módulo 10⁹+7” aparecem o tempo todo, porque a resposta real precisaria de uma biblioteca de inteiros grandes.
Duas coisas são necessárias: exponenciação que não leve um bilhão de multiplicações, e divisão, que não existe.
const long Mod = 1_000_000_007;
// Fast exponentiation: square the base, halve the exponent.
static long Power(long b, long e, long m)
{
long result = 1;
b %= m;
while (e > 0)
{
if ((e & 1) == 1) result = result * b % m;
b = b * b % m;
e >>= 1;
}
return result;
}
Console.WriteLine($"2^10 mod {Mod} = {Power(2, 10, Mod)}");
Console.WriteLine($"2^1000000 mod {Mod} = {Power(2, 1_000_000, Mod)}");
Console.WriteLine($"steps for e=1000000 : {(int)Math.Log2(1_000_000) + 1} squarings, not a million multiplications");
// Division does not exist mod p. Multiply by the modular inverse instead.
// Fermat: a^(p-1) = 1 mod p, so a^(p-2) is the inverse when p is prime.
static long Inverse(long a, long m) => Power(a, m - 2, m);
long inv3 = Inverse(3, Mod);
Console.WriteLine($"\ninverse of 3 = {inv3}");
Console.WriteLine($"3 * inverse(3) mod p = {3 * inv3 % Mod} <- 1, so it really is the inverse");
Console.WriteLine($"10 / 3 mod p = {10 * inv3 % Mod}");
Console.WriteLine($"check: that * 3 mod p = {10 * inv3 % Mod * 3 % Mod} <- back to 10");
// The trap: int arithmetic overflows BEFORE the modulus is applied.
int a = 1_000_000_006, b = 1_000_000_006;
Console.WriteLine($"\n(int)a * b % Mod = {unchecked(a * b) % Mod} <- wrong, a*b overflowed int first");
Console.WriteLine($"(long)a * b % Mod = {(long)a * b % Mod} <- correct");Ele imprime:
2^10 mod 1000000007 = 1024
2^1000000 mod 1000000007 = 235042059
steps for e=1000000 : 20 squarings, not a million multiplications
inverse of 3 = 333333336
3 * inverse(3) mod p = 1 <- 1, so it really is the inverse
10 / 3 mod p = 333333339
check: that * 3 mod p = 10 <- back to 10
(int)a * b % Mod = 923446813 <- wrong, a*b overflowed int first
(long)a * b % Mod = 1 <- correctPower eleva a base ao quadrado e corta o expoente pela metade, então 2^1000000 leva vinte elevações ao quadrado.
A divisão é substituída pela multiplicação pelo inverso modular. O pequeno teorema de Fermat diz que, para um primo p, a^(p-1) ≡ 1, então a^(p-2) é o inverso de a. Como 10⁹+7 é primo, Inverse é uma chamada a Power. A saída confirma: 3 * inverse(3) ≡ 1, e dividir e depois multiplicar devolve o original.
As duas últimas linhas são o bug de que este padrão realmente trata. a * b com os dois int dá overflow antes de % Mod rodar, e o resultado é errado parecendo totalmente razoável. Mantenha tudo em long, e tire o módulo depois de cada multiplicação em vez de só no fim.
Use quando o problema disser “módulo 10⁹+7”. Problemas de contagem, contagem de caminhos, combinatória.
Padrão 50 — Escrevendo a saída
A imagem espelhada do padrão 46, e o efeito é maior.
Console.Out tem AutoFlush ligado. Cada WriteLine empurra para o stream por baixo, então 200,000 linhas não são 200,000 operações de string — são 200,000 viagens pelo sistema operacional.
using System.Text;
// The cost of Console.WriteLine is not allocation — it is that AutoFlush
// pushes to the underlying stream on EVERY call. Count those pushes.
int n = 200_000;
static void Run(string name, Action<Stream> write)
{
var s = new CountingStream();
write(s);
Console.WriteLine($"{name,-26} {s.Writes,9:N0} writes to the stream {s.Bytes,10:N0} bytes");
}
Run("AutoFlush = true", s =>
{
var w = new StreamWriter(s) { AutoFlush = true }; // what Console.Out does
for (int i = 0; i < n; i++) w.WriteLine(i);
w.Flush();
});
Run("64KB buffer, no AutoFlush", s =>
{
var w = new StreamWriter(s, bufferSize: 1 << 16) { AutoFlush = false };
for (int i = 0; i < n; i++) w.WriteLine(i);
w.Flush();
});
Run("one StringBuilder", s =>
{
var sb = new StringBuilder();
for (int i = 0; i < n; i++) sb.Append(i).Append('\n');
var w = new StreamWriter(s, bufferSize: 1 << 16) { AutoFlush = false };
w.Write(sb);
w.Flush();
});
Console.WriteLine("\nIn a real program the fix is one line at the top:");
Console.WriteLine(" Console.SetOut(new StreamWriter(Console.OpenStandardOutput(),");
Console.WriteLine(" bufferSize: 1 << 16) { AutoFlush = false });");
Console.WriteLine("and Console.Out.Flush() before returning, or the output never arrives.");
class CountingStream : Stream
{
public int Writes { get; private set; }
public long Bytes { get; private set; }
public override void Write(byte[] buffer, int offset, int count) { Writes++; Bytes += count; }
public override void Write(ReadOnlySpan<byte> buffer) { Writes++; Bytes += buffer.Length; }
public override bool CanWrite => true;
public override bool CanRead => false;
public override bool CanSeek => false;
public override long Length => Bytes;
public override long Position { get => Bytes; set => throw new NotSupportedException(); }
public override void Flush() { }
public override int Read(byte[] b, int o, int c) => throw new NotSupportedException();
public override long Seek(long o, SeekOrigin s) => throw new NotSupportedException();
public override void SetLength(long v) => throw new NotSupportedException();
}Ele imprime:
AutoFlush = true 400,000 writes to the stream 1,288,890 bytes
64KB buffer, no AutoFlush 20 writes to the stream 1,288,890 bytes
one StringBuilder 20 writes to the stream 1,288,890 bytes
In a real program the fix is one line at the top:
Console.SetOut(new StreamWriter(Console.OpenStandardOutput(),
bufferSize: 1 << 16) { AutoFlush = false });
and Console.Out.Flush() before returning, or the output never arrives.Quatrocentas mil escritas contra vinte, para uma saída idêntica byte a byte. (Quatrocentas mil e não duzentas mil, porque WriteLine escreve o valor e a quebra de linha separadamente.)
Medido nesta máquina, 200,000 linhas levaram uns 190 ms sem buffer, uns 24 ms através de um buffer de 64KB, e uns 15 ms acumulando primeiro num StringBuilder. É a mesma ordem de economia que todo o resto desta parte, a partir de uma linha de configuração.
A coisa que vai te morder: dê flush antes de sair. Com AutoFlush = false, tudo que ainda estiver no buffer quando o processo termina simplesmente se perde, e o sintoma é uma solução que tira zero enquanto funciona perfeitamente na sua máquina — porque uma sessão de debug dá flush ao sair e o juiz pode não dar.
O que lembrar
-
Console.ReadLinenum laço é a razão de sempre para uma solução C# correta estourar o limite de tempo. Não o algoritmo. -
int.Parseaceita umReadOnlySpan<char>. Trocar o tipo e indexar com umRangeelimina toda alocação de substring com quase nenhum esforço. -
array[a..b]copia.span[a..b]não. Sintaxe idêntica, e o custo é invisível no ponto da chamada. -
stackallocé só para tamanhos constantes pequenos. Ele divide a stack de 1MB que limita a recursão. -
Use
lo + (hi - lo) / 2, acumule numlong, e faça o cast antes de multiplicar.(long)a * b, nunca(long)(a * b). -
C# não avisa sobre overflow. Ele dá a volta.
checked { }enquanto você depura faz ele falar na linha certa. -
a^(p-2) mod pé o inverso modular quando p é primo, e 10⁹+7 é. Tire o módulo depois de cada multiplicação, em aritméticalong. -
Desligue o
AutoFlush, e dê flush antes de sair. Esquecer o flush perde a saída inteira, e parece uma resposta errada em vez de uma resposta faltando.
São todos os cinquenta
Dez partes, cinquenta padrões, de dois inteiros caminhando um na direção do outro até o buffer que decide se alguma coisa disso termina a tempo.
Nada disso vale muito como uma lista para decorar. O que torna esses padrões úteis é reconhecer a forma — minimizar o máximo significa busca binária sobre a resposta, valores de 1 a n significa que o array é sua própria tabela hash, exatamente K significa contar “no máximo” duas vezes e subtrair. O código é a parte fácil quando a forma já tem nome.
A série completa é Padrões de programação competitiva em C#, e todo programa nela foi rodado no .NET 10 antes de ser publicado.