Fast I/O and Performance in C# for Competitive Programming

Nine parts of algorithms, and then this. It is last because it is the part nobody wants until something has already failed — a solution that is provably correct, that passes every test you wrote, and that the judge rejects on time.

In C#, the cause is very often not the algorithm.

Every program below is complete, was run on .NET 10, and its output is pasted from the run. Where a number is a timing rather than a count, it comes from one run on one machine and is there for the ratio, not the value.

Pattern 46 — Reading input

Console.ReadLine() inside a loop is the single most common reason a correct C# solution is too slow. It goes through a synchronised TextReader and produces a string object per line. Then Split(' ') produces another string per token.

Three ways to read 300,000 integers:

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}");

It prints:

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: True

Seventeen megabytes of garbage, or none, for identical work and an identical answer.

Timings from the same comparison on this machine: Split about 55 ms, the span version about 38 ms, the hand-parsed bytes about 17 ms. Reading one number per line through Console.ReadLine rather than one long line took about 40 ms against 18 ms buffered.

The middle option deserves attention because it is nearly free to adopt. int.Parse has accepted a ReadOnlySpan<char> since .NET Core 2.1, and MemoryExtensions.Split yields Range values rather than strings. Changing string to ReadOnlySpan<char> and indexing with the range removes every substring.

The byte reader is what to keep in a template. It is twenty lines, it never allocates, and it does not care how the input is spaced.

Reach for it when input is more than a few thousand tokens. Below that, write whatever is clearest.

Pattern 47 — Span<T> and stackalloc

Span<T> is a pointer and a length. Slicing one is arithmetic. Slicing an array with the same [a..b] syntax allocates a new array and copies.

stackalloc puts a small, fixed-size buffer on the stack. No allocation, no garbage collection, and it is gone when the method returns.

// 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");

It prints:

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 length

The frequency table is the everyday use. A new int[128] inside a function called a hundred thousand times is a hundred thousand allocations; stackalloc int[128] is none.

The size must be a small constant. Stack space is around 1MB by default — the same budget that limited recursion depth in part 7 — so stackalloc on anything that scales with input is how you turn a slow program into a dead one.

And note the last two lines. data[..500000] on an int[] copied a megabyte. The identical expression on a ReadOnlySpan<int> copied nothing. Same syntax, completely different cost, and nothing in the code makes that visible.

Reach for it when a small fixed buffer is needed inside a hot function, or when you are slicing and only reading.

Pattern 48 — Overflow

C# arithmetic is unchecked by default. Overflow does not throw; it wraps, silently, as defined behaviour.

// 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}");

It prints:

(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,000

Three habits come out of that output.

Write lo + (hi - lo) / 2. Every binary search in part 4 used it. (lo + hi) / 2 is correct for small values and produces a negative index for large ones.

Sum into a long. Six values that each fit comfortably in an int do not have a sum that fits. The accumulator’s type is what matters, not the elements’.

Cast before multiplying, not after. (long)a * b widens a first, so the multiplication happens in 64 bits. (long)(a * b) does the multiplication in int, overflows, and then widens the wrong answer.

The rule of thumb: int runs out just past two billion. If any intermediate value could reach that — and a product of two values near 10⁵ already does — use long. It costs nothing on a 64-bit runtime.

checked { } is useful while debugging, to make an overflow announce itself at the line that caused it rather than somewhere downstream.

Pattern 49 — Modular arithmetic

Answers “modulo 10⁹+7” appear constantly, because the real answer would need a big-integer library.

Two things are needed: exponentiation that does not take a billion multiplications, and division, which does not exist.

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");

It prints:

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   <- correct

Power squares the base and halves the exponent, so 2^1000000 takes twenty squarings.

Division is replaced by multiplying by the modular inverse. Fermat’s little theorem says that for a prime p, a^(p-1) ≡ 1, so a^(p-2) is the inverse of a. Since 10⁹+7 is prime, Inverse is one call to Power. The output verifies it: 3 * inverse(3) ≡ 1, and dividing then multiplying returns the original.

The last two lines are the bug this pattern is really about. a * b where both are int overflows before % Mod ever runs, and the result is wrong while looking entirely reasonable. Keep everything long, and take the modulus after every multiplication rather than at the end.

Reach for it when the problem says “modulo 10⁹+7”. Counting problems, path counts, combinatorics.

Pattern 50 — Writing output

The mirror image of pattern 46, and the effect is larger.

Console.Out has AutoFlush on. Every WriteLine pushes to the underlying stream, so 200,000 lines is not 200,000 string operations — it is 200,000 trips through the operating system.

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();
}

It prints:

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.

Four hundred thousand writes against twenty, for byte-identical output. (Four hundred thousand rather than two, because WriteLine writes the value and the newline separately.)

Measured on this machine, 200,000 lines took about 190 ms unbuffered, about 24 ms through a 64KB buffer, and about 15 ms accumulated in a StringBuilder first. That is the same order of saving as everything else in this part, from one line of setup.

The one thing that will bite you: flush before exiting. With AutoFlush = false, anything still in the buffer when the process ends is simply lost, and the symptom is a solution that scores zero while working perfectly on your machine — because a debugger session flushes on exit and a judge harness may not.

What to remember

• Console.ReadLine in a loop is the usual reason a correct C# solution times out. Not the algorithm.

• int.Parse takes a ReadOnlySpan<char>. Changing the type and indexing with a Range removes every substring allocation for almost no effort.

• array[a..b] copies. span[a..b] does not. Identical syntax, and the cost is invisible at the call site.

• stackalloc is for small constant sizes only. It shares the 1MB stack that limits recursion.

• Use lo + (hi - lo) / 2, accumulate into long, and cast before multiplying. (long)a * b, never (long)(a * b).

• C# does not warn about overflow. It wraps. checked { } while debugging makes it speak up at the right line.

• a^(p-2) mod p is the modular inverse when p is prime, and 10⁹+7 is. Take the modulus after every multiplication, in long arithmetic.

• Turn off AutoFlush, and flush before you exit. Forgetting the flush loses the entire output, and it looks like a wrong answer rather than a missing one.

That is all fifty

Ten parts, fifty patterns, from two integers walking towards each other to the buffer that decides whether any of it finishes in time.

None of it is worth much as a list to memorise. What makes these useful is recognising the shape — minimise the maximum meaning binary search on the answer, values from 1 to n meaning the array is its own hash table, exactly K meaning count “at most” twice and subtract. The code is the easy part once the shape is named.

The whole series is C# Competitive Programming Patterns, and every program in it was run on .NET 10 before it was published.