Nueve partes de algoritmos, y después esto. Va al final porque es la parte que nadie quiere hasta que algo ya falló — una solución demostrablemente correcta, que pasa todas las pruebas que escribiste, y que el juez rechaza por tiempo.
En C#, muy a menudo la causa no es el algoritmo.
Todos los programas de abajo están completos, se ejecutaron en .NET 10, y su salida está pegada de la ejecución. Cuando un número es un tiempo y no un conteo, viene de una sola ejecución en una sola máquina y está ahí por la proporción, no por el valor.
Patrón 46 — Leer la entrada
Console.ReadLine() dentro de un bucle es la razón más común de que una solución correcta en C# sea demasiado lenta. Pasa por un TextReader sincronizado y produce un objeto string por línea. Después Split(' ') produce otra cadena por token.
Tres formas de leer 300,000 enteros:
Un Span<T> es un puntero y una longitud que apuntan a memoria que ya existe. Rebanarlo es aritmética; rebanar un arreglo con la misma sintaxis [a..b] asigna y 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}");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: TrueDiecisiete megabytes de basura, o ninguno, para el mismo trabajo y la misma respuesta.
Tiempos de la misma comparación en esta máquina: Split unos 55 ms, la versión con span unos 38 ms, los bytes parseados a mano unos 17 ms. Leer un número por línea con Console.ReadLine en vez de una sola línea larga tomó unos 40 ms frente a 18 ms con búfer.
La opción del medio merece atención porque adoptarla es casi gratis. int.Parse acepta un ReadOnlySpan<char> desde .NET Core 2.1, y MemoryExtensions.Split devuelve valores Range en lugar de cadenas. Cambiar string por ReadOnlySpan<char> e indexar con el rango elimina todas las subcadenas.
El lector de bytes es lo que conviene guardar en una plantilla. Son veinte líneas, nunca asigna memoria, y no le importa cómo esté espaciada la entrada.
Úsalo cuando la entrada tenga más de unos pocos miles de tokens. Por debajo de eso, escribe lo que sea más claro.
Patrón 47 — Span<T> y stackalloc
Span<T> es un puntero y una longitud. Rebanarlo es aritmética. Rebanar un arreglo con la misma sintaxis [a..b] asigna un arreglo nuevo y copia.
stackalloc pone un búfer pequeño de tamaño fijo en la pila. Sin asignación, sin recolección de basura, y desaparece cuando el 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");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 lengthLa tabla de frecuencias es el uso de todos los días. Un new int[128] dentro de una función que se llama cien mil veces son cien mil asignaciones; stackalloc int[128] no es ninguna.
El tamaño tiene que ser una constante pequeña. La pila es de alrededor de 1MB por defecto — el mismo presupuesto que limitó la profundidad de recursión en la parte 7 — así que hacer stackalloc de algo que escala con la entrada es la forma de convertir un programa lento en uno muerto.
Y fíjate en las dos últimas líneas. data[..500000] sobre un int[] copió un megabyte. La expresión idéntica sobre un ReadOnlySpan<int> no copió nada. La misma sintaxis, un costo completamente distinto, y nada en el código lo hace visible.
Úsalo cuando necesites un búfer pequeño y fijo dentro de una función caliente, o cuando estés rebanando y solo leyendo.
Patrón 48 — Desbordamiento
La aritmética de C# es unchecked por defecto. El desbordamiento no lanza una excepción; da la vuelta, en silencio, como comportamiento definido.
La aritmética de C# es unchecked por defecto. El desbordamiento no es un error, es comportamiento definido que da la vuelta — por eso la falla aparece lejos de la línea que la causó.
// 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}");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,000De esa salida salen tres hábitos.
Escribe lo + (hi - lo) / 2. Todas las búsquedas binarias de la parte 4 lo usaron. (lo + hi) / 2 es correcto para valores pequeños y produce un índice negativo para los grandes.
Acumula en un long. Seis valores que caben cómodamente en un int cada uno no tienen una suma que quepa. Lo que importa es el tipo del acumulador, no el de los elementos.
Convierte antes de multiplicar, no después. (long)a * b amplía a primero, así que la multiplicación ocurre en 64 bits. (long)(a * b) hace la multiplicación en int, se desborda, y después amplía la respuesta equivocada.
La regla práctica: int se acaba un poco más allá de dos mil millones. Si algún valor intermedio puede llegar ahí — y el producto de dos valores cercanos a 10⁵ ya llega — usa long. No cuesta nada en un runtime de 64 bits.
checked { } es útil mientras depuras, para que un desbordamiento se anuncie en la línea que lo causó y no en algún lugar más adelante.
Patrón 49 — Aritmética modular
Las respuestas “módulo 10⁹+7” aparecen constantemente, porque la respuesta real necesitaría una biblioteca de enteros grandes.
Hacen falta dos cosas: exponenciación que no tome mil millones de multiplicaciones, y división, que no 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");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 la base al cuadrado y parte el exponente a la mitad, así que 2^1000000 toma veinte elevaciones al cuadrado.
La división se reemplaza multiplicando por el inverso modular. El pequeño teorema de Fermat dice que para un primo p, a^(p-1) ≡ 1, así que a^(p-2) es el inverso de a. Como 10⁹+7 es primo, Inverse es una sola llamada a Power. La salida lo verifica: 3 * inverse(3) ≡ 1, y dividir y luego multiplicar devuelve el original.
Las dos últimas líneas son el error del que trata en realidad este patrón. a * b donde ambos son int se desborda antes de que % Mod llegue a ejecutarse, y el resultado es incorrecto aunque se vea del todo razonable. Mantén todo en long, y toma el módulo después de cada multiplicación en lugar de al final.
Úsalo cuando el problema dice “módulo 10⁹+7”. Problemas de conteo, conteo de caminos, combinatoria.
Patrón 50 — Escribir la salida
La imagen espejo del patrón 46, y el efecto es más grande.
Console.Out tiene AutoFlush activado. Cada WriteLine empuja al stream subyacente, así que 200,000 líneas no son 200,000 operaciones de cadena — son 200,000 viajes por el sistema operativo.
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();
}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.Cuatrocientas mil escrituras contra veinte, para una salida idéntica byte a byte. (Cuatrocientas mil y no doscientas mil, porque WriteLine escribe el valor y el salto de línea por separado.)
Medido en esta máquina, 200,000 líneas tomaron unos 190 ms sin búfer, unos 24 ms a través de un búfer de 64KB, y unos 15 ms acumulándolas primero en un StringBuilder. Es el mismo orden de ahorro que todo lo demás en esta parte, a partir de una línea de configuración.
Lo único que te va a morder: vacía el búfer antes de salir. Con AutoFlush = false, lo que quede en el búfer cuando el proceso termina simplemente se pierde, y el síntoma es una solución que saca cero mientras funciona perfecto en tu máquina — porque una sesión de depuración vacía el búfer al salir y el sistema del juez puede que no.
Qué recordar
-
Console.ReadLinedentro de un bucle es la razón habitual de que una solución correcta en C# exceda el límite de tiempo. No el algoritmo. -
int.Parseacepta unReadOnlySpan<char>. Cambiar el tipo e indexar con unRangeelimina toda asignación de subcadenas casi sin esfuerzo. -
array[a..b]copia.span[a..b]no. Sintaxis idéntica, y el costo es invisible en el punto donde lo escribes. -
stackalloces solo para tamaños constantes y pequeños. Comparte la pila de 1MB que limita la recursión. -
Usa
lo + (hi - lo) / 2, acumula enlong, y convierte antes de multiplicar.(long)a * b, nunca(long)(a * b). -
C# no te avisa del desbordamiento. Da la vuelta.
checked { }mientras depuras hace que hable en la línea correcta. -
a^(p-2) mod pes el inverso modular cuando p es primo, y 10⁹+7 lo es. Toma el módulo después de cada multiplicación, en aritméticalong. -
Apaga
AutoFlush, y vacía el búfer antes de salir. Olvidar el vaciado pierde toda la salida, y parece una respuesta equivocada en vez de una respuesta que falta.
Eso es todo, los cincuenta
Diez partes, cincuenta patrones, desde dos enteros caminando uno hacia el otro hasta el búfer que decide si algo de eso termina a tiempo.
Nada de esto vale mucho como una lista para memorizar. Lo que los hace útiles es reconocer la forma — minimizar el máximo significa búsqueda binaria sobre la respuesta, valores de 1 a n significa que el arreglo es su propia tabla hash, exactamente K significa contar “como máximo” dos veces y restar. El código es la parte fácil una vez que la forma tiene nombre.
La serie completa es Patrones de programación competitiva en C#, y todos los programas en ella se ejecutaron en .NET 10 antes de publicarse.