Olimpiada de Computación Canadiense 2021
Swap Swap Sort
code
```cpp ```tags
- offline, small to large, BIThint 1
- La respuesta es la cantidad de inversiones en el array $a$. La cantidad inicial la podemos hallar con cualquier algoritmo para hallar todas las inversiones, i.e. usar BIT.hint 2
- Siempre cambiamos dos elementos con valores consecutivos, $p_i$ y $p_{i+1}$. Notemos que no cambia la cantidad de inversiones salvo entre ellos dos, debemos quitar la cantidad de inversiones que produce: $p_i < p_{i+1}$, y agregar la cantidad de inversiones que produce: $p_i > p_{i+1}$. Este cálculo es: $$inv(p_{i+1}, p_i) - inv(p_i, p_{i+1})$$ Donde $inv(x, y)$ indica la cantidad total de inversiones entre los elementos en $a$ con valor $x$ e $y$, siendo $x < y$.notar: $inv(x, y) + inv(y, x) = sz(x) \times sz(y)$, donde $sz(c)$ es la cantidad de elementos $c$ en el array $a$.
hint 3
- Notemos que solo nos interesa hallar $inv(x, y)$ para pares en nuestras $q$ consultas, podemos calcular cuales pares son, procesando todas las consultas y respondemos en offline.Si navegamos por todos los elementos con valor $x$, desde el menor al mayor índice, podemos calcular con un binary search la cantidad de inversiones, i.e. La cantidad de elementos $y$ con índice menor. Esta cálculo parece pesado, pero podemos usar una técnica small to large como en codechef camp 2016, consiguiendo una complejidad de $O(n \sqrt{q} \log{n})$.
hint 4
- Para reducir un factor $\log{n}$ podemos aplicar un segundo algoritmo offline, en este caso sobre el cálculo de estas inversiones. Para ello guardamos las consultas por cada posición de tal forma que con un barrido por los índices solo debemos ver en un array la cantidad de elementos que han aparecido. Complejidad final: $O(n\log{k} + q\log{n} + n\sqrt{q})$Weird Numeral System
tags
- dp, digits, greedyhint 1
Written on June 8, 2021