Боря программирует

slice.reverse

Вчера решал задачу на КФ, где нужно было уметь делать следующее. Дана строка длиной 2*10^5 символов, к ней нужно применить 2*10^5 операций. Каждая операция — развернуть какой-то подотрезок этой строки. TL=1с.

Это довольно известная задача, которую можно решать, например, с помощью декартового дерева за O(log n) на запрос.

После контеста в комментариях рассказали прикольный трюк, как можно получить АС с решением, которое делает O(n) операций на запрос. Вместо того чтобы просто хранить строку s, будем еще дополнительно хранить ее развернутую копию s_rev. Тогда, чтобы развернуть подстроку s[fr..to], можно просто скопировать готовую подстроку из s_rev:

fn reverse(&mut self, fr: usize, to: usize) {
let n = s.len();
let s = &mut self.s[fr..to];
let s_rev = &mut self.s_rev[n - to..n - fr];
s.swap_with_slice(s_rev);
}

Например, s='abcde'. Сохраним s_rev='edcba'. Как развернуть подстроку s[1..3]='bc'? Поменяем ее с s_rev[(5-3)..(5-1)]='cb'. Теперь s='acbde', а s_rev='edbca'.

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

Это решение получало АС за 889мс. Потом оказалось, что в задаче плохие тесты и на самом деле оно работает в 2 раза дольше, но все равно довольно быстро!

Самое смешное, что решение, которое просто вызывает .reverse на нужной подстроке (правда с указанием, что нужно использовать avx2) работает еще в два раза быстрее:

#[target_feature(enable = "avx2")]
unsafe fn reverse(s: &mut [u8]) {
s.reverse();
}

www.tgoop.com/bminaiev_blog/46

2.0K viewsSep 27, 2023 at 10:34

slice.reverse

Вчера решал задачу на КФ, где нужно было уметь делать следующее. Дана строка длиной 2*10^5 символов, к ней нужно применить 2*10^5 операций. Каждая операция — развернуть какой-то подотрезок этой строки. TL=1с.

Это довольно известная задача, которую можно решать, например, с помощью декартового дерева за O(log n) на запрос.

После контеста в комментариях рассказали прикольный трюк, как можно получить АС с решением, которое делает O(n) операций на запрос. Вместо того чтобы просто хранить строку s, будем еще дополнительно хранить ее развернутую копию s_rev. Тогда, чтобы развернуть подстроку s[fr..to], можно просто скопировать готовую подстроку из s_rev:

fn reverse(&mut self, fr: usize, to: usize) {
let n = s.len();
let s = &mut self.s[fr..to];
let s_rev = &mut self.s_rev[n - to..n - fr];
s.swap_with_slice(s_rev);
}

Например, s='abcde'. Сохраним s_rev='edcba'. Как развернуть подстроку s[1..3]='bc'? Поменяем ее с s_rev[(5-3)..(5-1)]='cb'. Теперь s='acbde', а s_rev='edbca'.

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

Это решение получало АС за 889мс. Потом оказалось, что в задаче плохие тесты и на самом деле оно работает в 2 раза дольше, но все равно довольно быстро!

Самое смешное, что решение, которое просто вызывает .reverse на нужной подстроке (правда с указанием, что нужно использовать avx2) работает еще в два раза быстрее:

#[target_feature(enable = "avx2")]
unsafe fn reverse(s: &mut [u8]) {
s.reverse();
}

BY Боря программирует