Здравствуйте, Lazytech, Вы писали:
L>Insane Coloured Triangles | Codewars
L>К сожалению, ни одно из моих решений не укладывается по времени, потому что все они брутфорсные.
L>Смутно подозреваю, что вместо работы со всей строкой можно как-то анализировать по несколько символов из начала и конца строки, но вот как...
Так а почему у тебя внешний цикл не укорачивается на каждой итерации то?
Здравствуйте, Lazytech, Вы писали:
L>К сожалению, ни одно из моих решений не укладывается по времени, потому что все они брутфорсные.
R = 0, G = 1, B = 2.
Несложно заметить, что функция определения элемента следующего ряда f(Ci, Ci+1 ) = (0 — Ci — Ci+1) mod 3.
Тогда можно переработать алгоритм на целочисленную математику и получить ускорение на порядок-другой.
Ну или заметить, что финальное число будет чем-то в духе = (-1)n-1 * (C0*1 + C1*(1)*(n-1) + C2*(2)*(n-1) + C3 * (3) * (n-1) + ...+ Cn-1*(1)*(n-1) + Cn-1*1) mod 3
С коэффициентами и знаком мог и наврать
Здравствуйте, Lazytech, Вы писали:
L>Insane Coloured Triangles | Codewars L>К сожалению, ни одно из моих решений не укладывается по времени, потому что все они брутфорсные. L>Смутно подозреваю, что вместо работы со всей строкой можно как-то анализировать по несколько символов из начала и конца строки, но вот как...
Исходная пара цветов преобразуется правилом f(u, v) = -u-v (mod 3)
То есть для получения ответа исходный вектор цветов достаточно умножить скалярно на соответствующую строчку треугольника Паскаля и на (-1)n. Всё по модулю 3.
Задачка на аккуратное вычисление биномиальных коэффициентов по малому модулю.
Здравствуйте, ltc, Вы писали:
ltc>Так а почему у тебя внешний цикл не укорачивается на каждой итерации то?
У меня там 3 решения, о каком из них идет речь?
P.S. Кажется, понял, о чем речь. У меня же там, в зависимости от решения, на каждой итерации внешнего (или единственного) цикла либо строка, либо дистанция от начала массива до условно конечного элемента укорачивается на единицу. Все решения рабочие, просто крайне неэффективные.
Здравствуйте, watchmaker, Вы писали:
W>Задачка на аккуратное вычисление биномиальных коэффициентов по малому модулю.
Можно было сказать это на немецком, я бы понял с таким же успехом. Про треугольник Паскаля знаю, про модуль — тоже, а про биномиальные коэффициенты, если когда-то и знал, то давно забыл...
Здравствуйте, dead0k, Вы писали: D>R = 0, G = 1, B = 2. D>Несложно заметить, что функция определения элемента следующего ряда f(Ci, Ci+1 ) = (0 — Ci — Ci+1) mod 3. D>Тогда можно переработать алгоритм на целочисленную математику и получить ускорение на порядок-другой.
Переход на целочисленную математику действительно значительно ускорил код! По моим грубым прикидкам, на пару-тройку порядков (самое быстрое из старых решений в лучшем случае проходило один тест со строкой средней длины, а новое решение прошло все сто таких тестов, плюс пару тестов со строками большой длины). По времени всё равно не уложился, но уже что-то.
Еще одно решение
function triangle(row) {
const colors = 'RGB';
let a, b, ab;
let rowArr = row.split('').map( char => colors.indexOf(char) );
for (let i = rowArr.length; i > 1; i--) {
a = rowArr[0];
for (let j = 1; j < i; j++) {
b = rowArr[j];
ab = ( 6 - a - b ) % 3;
a = b;
rowArr[j - 1] = ab;
}
}
return colors[ rowArr[0] ];
}
Здравствуйте, Lazytech, Вы писали:
L>Insane Coloured Triangles | Codewars
L>Смутно подозреваю, что вместо работы со всей строкой можно как-то анализировать по несколько символов из начала и конца строки, но вот как...
#!/usr/bin/lua
function fn(x)
local s,c,r,c1,r1,c2,r2,r3
function r3(t,r)
r=0 while t%3==0 do t=t//3 r=r+1 end
return t%3,r
end
if #x<2 then return x[1] end
s=x[1]+x[#x] c=1 r=0
for i=2,#x-1 do
c1,r1=r3(#x-i+1)
c2,r2=r3(i-1)
c=(c*c1*c2)%3
r=r+r1-r2
if r==0 then s=s+x[i]*c end
end
if #x%2==0 then s=2*s end
return s%3
end
function F(s)
local x,t,RGB,r={},{R=0,G=1,B=2},"RGB"
s:gsub("[RGB]",function(c) table.insert(x,t[c]) end)
r=fn(x)+1 return RGB:sub(r,r)
end
print(F"RRGBRGBB")
: не для всех внутренних элементов они равны единице. Например, для строк длиной 4 результат определяется суммой граничных символов, а от двух внутренних никак не зависит.
Здравствуйте, watchmaker, Вы писали: W>Задачка на аккуратное вычисление биномиальных коэффициентов по малому модулю.
Вычисление биномиальных коэффициентов "в лоб" для n=100000 не быстро даже если считать по модулю.
Наверное, для ускорения расчетов надо учитывать повторяющиеся паттерны (фракталы?)
Тогда достаточно рассчитать всего несколько первых рядов треугольника.
Здравствуйте, Буравчик, Вы писали: Б>Здравствуйте, watchmaker, Вы писали: W>>Задачка на аккуратное вычисление биномиальных коэффициентов по малому модулю. Б>Вычисление биномиальных коэффициентов "в лоб" для n=100000 не быстро даже если считать по модулю.
Теорема Люка говорит нам, что для посчёта биномиального коэффициента достаточно будет сложить log3N чисел.
В задаче ограничение на число элементов L = 100000.
Одиннадцать операций сложения — это не очень долго. Даже наоборот, достаточно быстро.
(в формуле в вики там умножение, но практичнее складывать логарифмы; а впрочем можно и умножать, не сильно медленнее)
const int inf = 65536;
// предпосчитанная таблица C^k_n, n=0..2, k=0..2
// BIN3LOG2[n][k] ≈ log_2(C^k_n mod 3)const int BIN3LOG2[3][4] = {
{0, -inf, -inf},
{0, 0, -inf},
{0, 1, 0},
};
// экспонента: 2^x mod 3int pow2mod3(int x) {
return (x < 0) ? 0 : 1 + (x & 1);
}
// вычисление C^k_n, где n, k записаны в троичной системе счисленияint b(const char nv[], const char kv[], const size_t l) {
int rl = 0;
for (size_t i = 0; i < l; ++i) {
rl += BIN3LOG2[nv[i]][kv[i]];
}
return pow2mod3(rl);
}
остальное
char solve(const string& l) {
size_t n = l.size();
const std::vector<char> bc = binomial(n - 1);
int r = 0;
for (size_t i = 0; i < n; ++i) {
r += l[i] * bc[i];
}
r <<= ~n & 1;
return"BRGBRG"[r % 3 + 3];
}
Лень делать совсем уж быстро, поэтому функция подсчёта строки треугольника Паскаля сделана отдельно и с выделением памяти, а не inplace. Зато сразу видно, что в решении нет ничего кроме скалярного произведения и учёта чётности.
binomial
Тут только одна содержательная строка, остальное — перевод в троичную систему счисления и инкремент в ней же
std::vector<char> binomial(size_t n) {
std::vector<char> r;
r.reserve(n + 1);
std::vector<char> nv; // n в троичной системе счисленияfor (size_t tn = n; tn; tn /= 3) {
nv.push_back(tn % 3);
}
nv.push_back(0);
std::vector<char> kv(nv.size(), 0); // k в троичной системе счисленияfor (size_t k = 0; k <= n; ++k) {
r.push_back(b(nv.data(), kv.data(), nv.size() - 1));
for (size_t t = 0; ; t++) {
if (kv[t] == 2) {
kv[t] = 0;
} else {
kv[t] += 1;
break;
}
}
}
return r;
}
Кстати, fun fact: можно исходный вектор символов не приводить к 0,1,2, так как ascii-коды символов RGB уже имеют различные остатки от деления на 3. Сразу можно символы на биномиальные коэффициенты умножать
Б>Наверное, для ускорения расчетов надо учитывать повторяющиеся паттерны
Да, можно.
Например, учитывать, что треугольник симметричный и поэтому можно вычислить лишь половину коэффициентов, и исходную строку можно предварительно сложить со своим реверсом и дальше обрабатывать тоже только первую половину.
Или не вычислять коэффициенты подряд, а поменять циклы местами — тогда можно будет отбрасывать весь интервал, если встретился нулевой множитель, так как финальные коэффициенты на нём также будут нулевые.
Ну или банально векторизовать вычисления — тут всё очень регулярно и с минимум ветвлений.
Впрочем, кажется, эти идеи ускорят вычисление максимум в несколько раз, и не окупятся тут по соотношению ускорение/трудозатраты
Здравствуйте, watchmaker, Вы писали:
W>Задача хоть и решается за единственный проход по массиву, но веса, с которыми нужно брать элементы при суммировании, устроены чуть-чуть сложнее
: не для всех внутренних элементов они равны единице. Например, для строк длиной 4 результат определяется суммой граничных символов, а от двух внутренних никак не зависит.
Да был не прав. Поправил:
#!/usr/bin/lua
function fn(x)
local s,c,r,c1,r1,c2,r2,r3
function r3(t,r)
r=0 while t%3==0 do t=t//3 r=r+1 end
return t%3,r
end
if #x<2 then return x[1] end
s=x[1]+x[#x] c=1 r=0
for i=2,#x-1 do
c1,r1=r3(#x-i+1)
c2,r2=r3(i-1)
c=(c*c1*c2)%3
r=r+r1-r2
if r==0 then s=s+x[i]*c end
end
if #x%2==0 then s=2*s end
return s%3
end
function F(s)
local x,t,RGB,r={},{R=0,G=1,B=2},"RGB"
s:gsub("[RGB]",function(c) table.insert(x,t[c]) end)
r=fn(x)+1 return RGB:sub(r,r)
end
print(F"RGGR")
Здравствуйте, watchmaker, Вы писали:
W>[skip] Например, для строк длиной 4 результат определяется суммой граничных символов, а от двух внутренних никак не зависит.
Здравствуйте, Буравчик, Вы писали:
Б>Наверное, для ускорения расчетов надо учитывать повторяющиеся паттерны (фракталы?) Б>Тогда достаточно рассчитать всего несколько первых рядов треугольника.
Небольшое математическое исследование я точно не потяну.
Здравствуйте, watchmaker, Вы писали:
W>Например, учитывать, что треугольник симметричный и поэтому можно вычислить лишь половину коэффициентов, и исходную строку можно предварительно сложить со своим реверсом и дальше обрабатывать тоже только первую половину. W>Или не вычислять коэффициенты подряд, а поменять циклы местами — тогда можно будет отбрасывать весь интервал, если встретился нулевой множитель, так как финальные коэффициенты на нём также будут нулевые. W>Ну или банально векторизовать вычисления — тут всё очень регулярно и с минимум ветвлений. W>Впрочем, кажется, эти идеи ускорят вычисление максимум в несколько раз, и не окупятся тут по соотношению ускорение/трудозатраты
Похоже, я ошибся с названием темы: «Простая с виду задачка с подвохомfor senior software engineers only».
Здравствуйте, watchmaker, Вы писали:
W>Кстати, fun fact: можно исходный вектор символов не приводить к 0,1,2, так как ascii-коды символов RGB уже имеют различные остатки от деления на 3. Сразу можно символы на биномиальные коэффициенты умножать
Да, совпало
W>Впрочем, кажется, эти идеи ускорят вычисление максимум в несколько раз, и не окупятся тут по соотношению ускорение/трудозатраты
Не, там один паттерн вложен в другой — каждый треугольник состоит из таких же шести треугольников. Общее количество вычислений будет линейным от номера ряда в треугольнике Паскаля.
Про треугольник Паскаля знаю, про модуль — тоже, а про биномиальные коэффициенты, если когда-то и знал, то давно забыл...
