Comments 20
Наименование переменных, конечно, ужасное
Исправлю по мере возможности.
Практически все такие комбинаторные задачи на k-ый лексикографический объект решаются примерно одинаково: вам надо научиться считать, сколько таких объектов есть с заданным перфиксом, а потом перебирать префикс по одному символу. Тут не надо даже бинарного поиска.
Все последовательности начинаются или с '(' или с ')'. Мы можем посчитать, сколько их и тех и других. Если первых хотя бы k - то мы знаем, что k-ая последовательность будет среди них, и зафиксировать первый символ как '('. Вообще тут все пока очеивдно, ибо вторых 0, ведь все последовательности начинаются с открывающей скобки. Но дальше интереснее: зафиксировали мы первый символ. Есть последовательности в которых второй символ '(' или ')', подсчитали каждые, сразу поняли какой символ будет вторым, ведь мы знаем какая по счету из них нам нужна. Зафиксировали второй символ. И т.д.
Назовем балансом разность количества '(' и ')'. В правильной скобочной последовательности баланс в каждом перфиксе не отрицателен а в конце 0.
Вот есть у вас какой-то префикс. Нам не важно, что именно в нем, от него нам важен лишь баланс. Именно это определяет, какие скобочки можно ставить дальше. Пусть его баланс k. Осталость n символов дополнить. Надо научиться считать сколько последовательностей можно сюда дописать. Это динамика: F(n,k) = F(n-1,k-1) + F(n-1, k+1). И база F(n, -1) = 0, F(0,0) = 1, F(0,k) = 0. Опять же, все искомые последовательности начинаются или с '(' или с ')'. Считаем сколько каждых, для чего новый символ добавляем в перфикс. Вообще, это F можно интерпретировать как количество правильных последовательностей длиной n+k, начинающихся с k '('. Почти то же что и у вас.
Вот уже решение с O(n^2) предподсчетом работающее за O(n). Ну, и памяти тоже O(n^2) надо на таблицу.
Но его можно соптимизировать, кажется до линии, если научиться считать F(n, k) через комбинаторику как-то быстрее, но тут надо выписать числа и помедетировать над ними.
Добавлю про оптимизацию до O(n). Если выписать F:
n k0 1 2 3 4 5 6 7 8
0 |1
1 |0 1
2 |1 0 1
3 |0 2 0 1
4 |2 0 3 0 1
5 |0 5 0 4 0 1
6 |5 0 9 0 5 0 1
7 |0 14 0 14 0 6 0 1
8 |14 0 28 0 20 0 7 0 1То можно заметить, что все числа тут - это числа каталана, только выписаные по диагоналям и с кучей лишних 0. Четность n, k для не нулевых значений всегда будет совпадать и F(n,k) = Cat((n+k)/2, n-k). Если обозначить m=(n+k)/2, t =n-k, то F(n,k) = (m+t)!(m-t+1)/(t!(m+1)).
Для самого начала мы можем это число подсчитать за линию умножений и делений, а потом при постановке символа у нас m и t уменьшаются на 1 или остаются прежними. В любом случае, можно пересчитать новое число каталана просто домножив и поделив на что-то за константу.
Это все, конечно, если считать что у нас значения помещаются в целые числа. Тут нельзя ничего считать по модулю, потому что нам нужно точное значение количества последовательностей. Если считать с длинной арифметикой, тут числа порядка O(n) и решение будет за O(n^2) и O(n) памяти. Но если у вас считать с длинной арифметикой, то у вас будет O(n^3) предподсчет и само решение за O(n^2 log n).
Но минус у этого решения тоже есть: нельзя все считать в маленьких числах, даже если искомый номер последовательности в целые числа влезает. Но в этом случае можно просто считать все F через сложения, не считая левый нижний угол, ибо там слишком большие числа будут.
Да это сложное решение какое-то. Мне мое кажется попроще. Но однажды придется сесть и разобраться, кажется.
Я недавно решал эту задачу на кодоварсе, и придумал решение, весьма похожее на "общепринятое". Попробую объяснить своими словами. У меня F(X, Y) - сколько всего есть "подходящих строк", в которых X открывающих скобок и Y закрывающих. Подходящая строка - это окончание правильной скобочной последовательности.
F считается через ДП: F(0, y) = 1, F(x > y) = 0, F(x, y) = F(x-1, y) + F(x, y-1)
Формируем последовательность в цикле. На каждой итерации у нас ещё не использовано A открывашек и B закрывашек (на старте A=B=n), а значение k меньше чем F(A, B). При выборе открывашки, из оставшихся скобок можно будет собрать F(A-1, B) разных вариантов. Если k < F(A-1, B), то на данной итерации выбираем открывашку, в противном случае выбираем закрывашку, а из k вычитаем значение F(A-1, B) для поддержания инварианта. Цикл заканчивается, когда все открывашки использованы (когда A=0), потом просто дописываем в конец неиспользованные ")"
Вот сделал свое решение O(n) c O(1) памяти. БОльшая часть кода для счета без переполнения. Если входной номер большое число, то все придется считать в длинной арифметике и будет O(n^2), но кода может чуть поменьше. Моя F - это сколько последовательностей с n пар скобками с k открвающимеся в начале. Думаю, что-то подобное с пересчетом через домножение можно сделать и с вашими F.
код
// F(n,k) = Сколько последовательностей из n пар начинаются с k '('
// F(n,k) = F(n, k+1) + F(n-1, k-1)
// 1
// 1 1
// 2 2 1
// 5 5 3 1
// 14 14 9 4 1
//
// Это же числа каталана! Только отраженные.
// Вот формула
// F(n, k) = (2*n-k)!(k+1)/((n-k)!(n+1)!)
//
// Научимся пересчитывать внутри строки:
// k++ => mult by (k+2)*(n-k)/(2*n-k)/(k+1)
// k-- => mult by (2*n-k+1)*k/(k+1)/(n-k+1)
//
// А если мы заменяем последнюю '(' на ')':
// k-=2 --n => mult by /(k+1) /(n-k+1) *(n+1) *(k-1)
// Считаем a*n/d без переполнения (мы знаем, что влезет).
int64_t SafeMult(int64_t a, int n, int d) {
// a = (q*d + r)
// a / d * n = q*n + r*n/d
int64_t q = a / d;
return q * n + (a - q * d) * n / d;
}
// Проверка a*n/d < b без переполнения.
bool SafeCompare(int64_t a, int n, int d, int64_t b) {
// Проверяем a/d < k/n
// Сначала целые части
if (d == 0) return false;
if (n == 0) return 0 < b;
int64_t int_l = a / d;
int64_t int_r = b / n;
if (int_l < int_r) return true;
if (int_l > int_r) return false;
// Целые равны, проверим дробные
// a % d / d < b % n / n
// Числа маленькие, можно перемножить.
return (a % d) * n < (b % n) * d;
}
// Можно ли сдвинуться влево в строке не перескочив через t?
bool CanDecreaseK(int64_t count, int n, int k, int64_t t) {
int den = (k+1)*(n-k+1);
int num = (2*n-k+1)*k;
return SafeCompare(count, num, den, t);
}
// Замена последней '(' на ')'.
void Replace(int64_t &count, int &n, int &k) {
int den = (k+1)*(n-k+1);
int num = (n+1)*(k-1);
k -= 2;
n--;
count = SafeMult(count, num, den);
}
// Поставили '('.
void IncreaseK(int64_t &count, int n, int &k) {
int num = (k+2)*(n-k);
int den = (2*n-k)*(k+1);
++k;
count = SafeMult(count, num, den);
}
// Убрали последнюю '('.
void DecreaseK(int64_t &count, int n, int &k) {
int den = (k+1)*(n-k+1);
int num = (2*n-k+1)*k;
--k;
count = SafeMult(count, num, den);
}
// Построить k-ую (считая с 1) последовательность из n пар скобок.
string Generate(int n, int64_t k) {
string answer;
if (k == 1) {
for (int i = 0; i < n; ++i) {
answer += '(';
}
for (int i = 0; i < n; ++i) {
answer += ')';
}
return answer;
}
// Поддерживаем инваринант:
// answer содержит начало искомой строки.
// count - сколько всего строк с таким началом есть.
// Сколько '(' будет в начале?
// Начинаем с максимального количества.
int64_t count = 1;
int num_opening = n;
while (CanDecreaseK(count, n, num_opening, k)) {
DecreaseK(count, n, num_opening);
}
for (int i = 0; i < num_opening; ++i) {
answer += '(';
}
// Сейчас у нас минимальное количество '(', которых еще мало.
// Надо последнюю убрать.
// Все такие строки мы пропускаем, значит надо вычесть из номера.
k -= count;
// Заменяем '(' на ')'
answer.back() = ')';
Replace(count, n, num_opening);
while (n > num_opening) {
// Пробуем сначала поставить '('
IncreaseK(count, n, num_opening);
answer += '(';
// Если таких строк мало, надо их пропустить и ставить ')'
if (count < k) {
k -= count;
Replace(count, n, num_opening);
answer.back() = ')';
}
}
for (int i = 0; i < num_opening; ++i) {
answer += ')';
}
return answer;
}Крутой способ. Потом прогоню под дебагом, чтобы лучше понять.
Я думаю, тут сразу надо говорить о длинной арифметике, потому что иначе всё это O(1). По памяти тогда будет O(n)? А по времени наверно O(n^2 * ln(n)), там ведь умножения длинных чисел.
Мой вариант (как и каноничный) занимает O(n^3) по времени и памяти.
Если делать с длинной арифметикой, то тут будет O(n^2) по времени и O(n) по памяти. Ибо там умножения/деления на короткие и n сравнений длинных чисел. И, если уж делать с длинной арифметикой, то можно первую половину решения выкинуть. Там мы считаем, сколько надо поставить '(' сначала, и таким образом выбрасываем огромное количество последовательностей, чтобы количество оставшихся с данным префиксом было мелким. Но, если мы большие числа считаем, этого делать не надо. Тогда выбрасываем первый цикл, считаем вместо него число каталана (общее количество последовательностей из n пар). А потом остается основной цикл while (n > num_opening). Выбрасываем все Safe функции и там остается только IncreaseK и Replace.
Основаная идея даже проще вашего решения. Не надо искать закономерности и структуру последовательностей, это простой и универсальный принцып, как поиск в словаре. Вы знаете, сколько слов начинается на 'А'. Если их больше рано искомому k вы знаете, что ваше слово начинается на 'А' Иначе вы все эти строки вычеркиваете из расмотрения и пересчитваете k. Продолжаете с 'Б' и т.д. пока не найдете первую букву. Потом вы фиксируете ее и смотрите на вторую. Все что вам надо уметь, это считать сколько у вас бывает последовательностей с таким началом.
Дальше чуть-чуть логики и математики, чтобы научиться считать сколько последовательностей есть с кажым началом.
Вот если вы хотите сделать без длинной арифметики, да за O(N) с O(1) памяти (как у меня ниже, посмотрите, если интересно), вот там придется уже побольше математики нагородить, чтобы пересчитывать количество объектов быстро и без переполнения. Переполенение потому, что объектов-то экспоненциально много, и если вы попросите 10000000-ую последовательность из 100 скобок, то можно неаккуратно попробовать подсчитать, например, сколько их всего, а это ни в какое 64-битное число не влезет никак.
Я пытался представить последовательность в виде битов, но мне не хватило мозгов вывести окончательную закономерность.
((())) = 000111 = 7
(()()) = 001011 = 11
()(()) = 010011 = 19
...
()()() = 010101 = 21
Т.е. можно идти от 
вверх с шагом 
до 
(или вниз при инверсии) и отсеивать ненужные. Вот универсальный корректный отсев мне и не удалось придумать.
Тут что-то вроде алгоритма Найораны можно получить, чтобы по одной битовой последовательности получать следующую. Но там весьма сложная операция: последний ноль, перед которым больше 0, чем 1, заменяем на 1, и в конце ставим все оставшиеся 1 в конец. Но уж закономерность по битам получать номер и обратно - это что-то совсем незаписываемое.
Да, это я про генерацию всех доступных написал. Вообще, меня интересовала не столько битовая магия, сколько само получение числа, соответствующего набору скобок.
Касательно номера последовательности. Если посмотреть на закономерность, то там приращения идут
для 10 скобок
992 - 16 => ((((())))) : тут '(' == 1, ')' == 0
976 - 8 => (((()())))
968 - 4 => ...
964 - 2
962
---
944 - 8
936 - 4
932 - 2
930
---
920 - 4
916 - 2
914
---
908 - 2
906
Сначала идёт 5 чисел, потом 4 и т.д. Потом повторяются, но 16 уже не будет. Размер групп уменьшается. Расстояние между числами в группе всегда равно степени двойки. А вот на расстоянии между группами я споткнулся. Но я не исключаю, что для него тоже есть закономерность. Если она существует, можно, наверное, быстро вычислить нужное число.
Это только для маленьких чисел. Вот вам "приращения" для всех скобочных последовательностей длины 10:
Скрытый текст
((((()))))
(((()()))) -16
(((())())) -8
(((()))()) -4
(((())))() -2
((()(()))) -18
((()()())) -8
((()())()) -4
((()()))() -2
((())(())) -10
((())()()) -4
((())())() -2
((()))(()) -6
((()))()() -2
(()((()))) -26
(()(()())) -8
(()(())()) -4
(()(()))() -2
(()()(())) -10
(()()()()) -4
(()()())() -2
(()())(()) -6
(()())()() -2
(())((())) -18
(())(()()) -4
(())(())() -2
(())()(()) -6
(())()()() -2
()(((()))) -58
()((()())) -8
()((())()) -4
()((()))() -2
()(()(())) -10
()(()()()) -4
()(()())() -2
()(())(()) -6
()(())()() -2
()()((())) -18
()()(()()) -4
()()(())() -2
()()()(()) -6
()()()()() -2Во-первых, не всегда степени двойки. Во-вторых, скачет как ему вздумается. Для большего количества скобочек там еще более запутанная ситуация будет. Начало и конец, действительно более менее регулярны, потому что там весьма локальные изменения около центра происходят. Но потом они разрастаются и изменения происходят по всей строке.
Закономерность я описал выше, но ее не описать так просто в терминах битов. Там надо найти последний 0, где баланс левее положителен. Тут фигурирует что-то вроде popcnt от части числа.
Вы невнимательно прочитали. Приращения, не кратные степени - это скачок между группами. Посмотрите внимательнее на мой (и свой тоже) пример. Там идет группа из 5 чисел, расстояние между которыми кратно степени двойки. Затем скачок. Затем группа из 4 чисел, расстояние между которыми кратно степени двойки и т.д.
P.S. начало для 12 скобок
4032 = 32
4000 = 16
3984 = 8
3976 = 4
3972 = 2
3970
----
3936 = 16
3920 = 8
3912 = 4
3908 = 2
3906
----
3888 = 8
3880 = 4
3876 = 2
3874
P.P.S Т.е. максимальное расстояние (между первым и последним членами) для группы длины 
равно 
; 
. В обоих случаях 
, где 
похоже код в конце не рабочий, попробовал (ради любопытства) в одном из Swift Online Compiler - куча ошибок выдает. Это же Swift?
import Foundation
let vbs = Array("(()(()())...())")
let n = vbs.count / 2
var array = Array(repeating: Array(repeating: 0, count: n + 1), count: n + 1)
if n > 0 {
array[1][1] = 1
}
for i in 2...n {
array[i][1] = array[i - 1][i - 1]
for j in 2...i {
array[i][j] = array[i][1] + array[i][j - 1] - (j > 1 && i > 1 ? array[i - 1][j - 2] : 0)
}
}
var inserts = Array(repeating: 0, count: n)
var k = 0
var j = max(n - 1, 0)
for i in 0..<(2 * n) {
if vbs[i] == "(" {
k += 1
} else {
k -= 1
if j < n {
inserts[j] = k
}
j = max(j - 1, 0)
}
}
var m = 0
for i in (1...n).reversed() {
let ii = inserts[i - 1]
if ii > 0 && (ii - 1) < array[i - 1].count {
m += array[i][ii] - array[i - 1][ii - 1]
}
}
print(array[n][n] - (m + 1))Этот код работает для правильной скобочной последовательности, без проверок за выход из диапазона для массивов.
"(()(()())...())" -неправильная скобочная последовательность
Это вообще не скобочная последовательность
Три точки тут для отображения того, что здесь может быть любая скобочная правильная последовательность.
Исправьте на правильную
"()()(())" "()(())()((()))" и тп
Ну и код не работает для "()", так как есть 2...n, а такой диапазон даст ошибку, так как n должен быть больше или равен 2.
Код просто нужно обернуть в функцию и перед ее заупском сделать требуемые проверки.
Делать проверки в самом алгоритме - неправильно, это влияет на производительность, их нужно делать перед проверкой.
Если хочется исправить и случай для "()" вместо for нужно просто while использовать.
Правильная скобочная последовательность