Задача от яндекса "Генерация скобочных последовательностей"

В общем яндекс крайне странная контора, которая сделала очень странные задания и много лет не может нормально описать условия) всё упёрлось в операции ввода/вывода. Следующий вариант работает всегда c запасом:

import java.io.*;

public class BracesGenerator5 {
    static final String inputFile = "input.txt";
    static final String outputFile = "output.txt";
    static BufferedReader br;
    static BufferedWriter bw;

    static char[] input;
    static byte nextPositionToSetup = 1;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new FileReader(inputFile));
        bw = new BufferedWriter(new FileWriter(outputFile));
        byte n = Byte.parseByte(br.readLine());
        if(n == 0) return;
        input = new char[n * 2];
        input[0] = '(';
        generateBraces(1, 0);

        br.close();
        bw.close();
    }

    public static void generateBraces(int openBrackets, int closeBrackets) throws IOException {
        if (nextPositionToSetup == input.length) {
            bw.write(input);
            bw.newLine();
            return;
        }
        if (openBrackets == 0 || (openBrackets < input.length / 2)) {
            input[nextPositionToSetup] = '(';
            nextPositionToSetup++;
            generateBraces(openBrackets + 1, closeBrackets);
            nextPositionToSetup--;
        }
        if (closeBrackets < openBrackets) {
            input[nextPositionToSetup] = ')';
            nextPositionToSetup++;
            generateBraces(openBrackets, closeBrackets + 1);
            nextPositionToSetup--;
        }
    }
}

Какая здесь связь с алгоритмами - непонятно.

А вот это рабочий вариант при итеративном алгоритме:

import java.io.*;

public class BraceGeneratorIterative {
    static final String inputFile = "input.txt";
    static final String outputFile = "output.txt";
    static BufferedReader br;
    static BufferedWriter bw;
    static char[] result;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new FileReader(inputFile));
        bw = new BufferedWriter(new FileWriter(outputFile));
        byte n = Byte.parseByte(br.readLine());
        if (n == 0) return;
        result = new char[2 * n];
        for (int i = 0; i < 2 * n; i++) {
            result[i] = (i < n) ? '(' : ')';
        }
        bw.write(result);
        bw.newLine();
        boolean sequenceWasGenerated = true;
        while (sequenceWasGenerated) {
            sequenceWasGenerated = generateNextSeq(n);
            if (sequenceWasGenerated) {
                bw.write(result);
                bw.newLine();
            }
        }
        br.close();
        bw.close();
    }

    public static boolean generateNextSeq(int n) {
        int open = 0;
        int closed = 0;
        for (int i = 2 * n - 1; i >= 0; i--) {
            if (result[i] == '(') {
                open++;
                if (closed > open) {
                    closed--;
                    result[i] = ')';
                    for (int k = 1; k <= open; k++) {
                        result[k + i] = '(';
                    }
                    for (int c = 1; c <= closed; c++) {
                        result[c + i + open] = ')';
                    }
                    return true;
                }
            } else {
                closed++;
            }
        }
        return false;
    }
}

Да, задача оказалась про скорость вывода.

Для n = 15 рекурсивный алгоритм делает 48760365 изменений в буфере и печатает 9694845 строк по 31 байту каждая. В среднем меняется пять символов в массиве символов, после чего массив отправляется на печать.

Печать переводит каждый символ из массива из UNICODE в набор байт для записи в выходной поток. Это требует времени. Я и вы знаем что в массиве лежат ASCII символы, которые отображаются в байты выходного потока один к одному. Но Java этого не знает и применяет универсальные алгоритмы для обработки UNICODE.

Вычислительная часть алгоритма меняет пять символов, печать преобразует тридцать символов в байты и печатает их. Ясно, что печать будет играть существенную роль в скорости работы программы.

Кроме того System.out.println рассчитан на интерактивное использование, он сбрасывает буфер после каждой строки, что дополнительно замедляет вывод.

Решение без оптимизации вывода:

import java.util.Scanner;

public class Temp {
    static int n;
    static char[] buffer;

    public static void main(String... args) {
        n = new java.util.Scanner(System.in).nextInt();
        buffer = new char[2 * n];
        enumerate(0, 0);
    }

    static void enumerate(int left, int right) {
        if (left == n && right == n) {
            System.out.println(buffer);
            return;
        }
        if (left < n) {
            buffer[left + right] = '(';
            enumerate(left + 1, right);
        }
        if (right < left) {
            buffer[left + right] = ')';
            enumerate(left, right + 1);
        }
    }
}

Запуск для n = 15 работает дольше пяти секунд (строка real). Большое время в строке sys связано с задержками при сбросе буфера:

$ time -p echo 15 | java Temp | wc -l
9694845
real 5.22
user 2.55
sys 6.68

Чтобы ускорить печать, перейдём от символов к байтам и уберём из процесса преобразование UNICODE. Перевод строки \n добавим в конец буфера, это в два раза сократит количество операций вывода. На System.out наденем буфер в 64 килобайта, он не имеет своего буфера.

Сам алгоритм не изменился, только вывод:

import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Temp {
    static int n;
    static byte[] buffer;
    static BufferedOutputStream output = new BufferedOutputStream(System.out, 64 * 1024);

    public static void main(String... args) throws IOException {
        n = Integer.parseInt(new BufferedReader(new InputStreamReader(System.in)).readLine());
        buffer = new byte[2 * n + 1];
        buffer[2 * n] = '\n';
        enumerate(0, 0);
        output.flush();
    }

    static void enumerate(int left, int right) throws IOException {
        if (left == n && right == n) {
            output.write(buffer);
            return;
        }
        if (left < n) {
            buffer[left + right] = '(';
            enumerate(left + 1, right);
        }
        if (right < left) {
            buffer[left + right] = ')';
            enumerate(left, right + 1);
        }
    }
}

Скорость выросла в двадцать раз. Задержки при выводе почти исчезли:

$ time -p echo 15 | java Temp | wc -l
9694845
real 0.25
user 0.24
sys 0.08

Результаты тестирования на https://contest.yandex.ru/contest/8458/problems/D/. Слева программа с простым выводом, справа с оптимизированным. Простой вывод переполняет память в тринадцатом тесте. Могу предположить что UNICODE обработка порождает много временных объектов и сборщик мусора не успевает их убрать.