Skip to Content

Global Warming

Análisis oficial 

Podemos ver las temperaturas como un arreglo vv. Queremos decrementar un intervalo contiguo en un valor dxd \le x de modo que la longitud de la subsecuencia creciente más larga (LIS) sea lo más grande posible. Nótese que no hace falta considerar también incrementar, porque cada disminución de un intervalo corresponde al aumento de otro intervalo.

Subtareas 1-3: fuerza bruta

Una observación clave es que no sirve restar dd de un intervalo [l,r][l,r] en lugar de solo [1,r][1, r] para cualquier l1l \neq 1. Además, obsérvese que es óptimo restar siempre xx del intervalo [1,r][1, r] sin importar qué.

Un algoritmo O(n2logn)\mathcal{O}(n^2 \log n) consistiría en probar por fuerza bruta todos los prefijos. Restamos xx de cada intervalo [1,i][1, i] para todo i{1,2,,n}i \in \{1, 2, \dotsc, n\} y luego hallamos la LIS después de cada resta.

Subtarea 4: una pasada

Tomamos la LIS del arreglo. Cualquier algoritmo O(nlogn)\mathcal{O}(n \log n) para hallar la LIS pasará.

Solución general

Para cada ii, sea LiL_i la longitud de la subsecuencia creciente más larga que termina en ii y lo contiene, y RiR_i la longitud de la subsecuencia creciente más larga que empieza en ii después de decrementar [1,i][1, i]. Podemos calcular cada RiR_i guardando la longitud de la subsecuencia decreciente más larga para cada prefijo del reverso del arreglo de entrada.

La respuesta final es maxi{0,1,,n}Li+Ri1\max_{i \in \{0, 1, \dotsc, n\}} L_i+R_i-1.

Implementación

En la implementación LiL_i es preflongestipref_longest_i y Ri1R_i-1 es la variable pospos en el segundo bucle for.

#include <bits/stdc++.h> using namespace std; int temps[200005]; int pref_longest[200005]; int main() { int n; int x; cin >> n >> x; for (int i = 0; i < n; i++) { cin >> temps[i]; } vector<int> dp(n, INT_MAX); int longest = 0; // longest increasing subsequence ending at i for (int i = 0; i < n; i++) { int j = lower_bound(dp.begin(), dp.end(), temps[i]) - dp.begin(); dp[j] = temps[i]; pref_longest[i] = j + 1; longest = max(longest, pref_longest[i]); } dp = vector<int>(n, INT_MAX); // longest decreasing subsequence ending at i of reverse // = longest increasing subsequence starting at i for (int i = n - 1; i >= 0; i--) { int pos = lower_bound(dp.begin(), dp.end(), -temps[i] + x) - dp.begin(); longest = max(longest, pref_longest[i] + pos); int insert_pos = lower_bound(dp.begin(), dp.end(), -temps[i]) - dp.begin(); dp[insert_pos] = -temps[i]; } cout << longest << endl; }
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /** * this code here treats the change as incrementing the suffix instead of * decrementing the prefix as in the editorial but it's basically the same thing */ public class glo { public static void main(String[] args) throws IOException { BufferedReader read = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer initial = new StringTokenizer(read.readLine()); int tempNum = Integer.parseInt(initial.nextToken()); int maxCheating = Integer.parseInt(initial.nextToken()); int[] temps = Arrays.stream(read.readLine().split(" ")) .mapToInt(Integer::parseInt) .toArray(); // this[i] = the longest subsequence that ends at and contains temps[i] int[] prefLongest = new int[tempNum]; ArrayList<Integer> minEndings = new ArrayList<>(); // standard LIS stuff for (int i = 0; i < tempNum; i++) { int t = temps[i]; int pos = bisectLeft(minEndings, t); prefLongest[i] = pos + 1; if (pos == minEndings.size()) { minEndings.add(t); } else { minEndings.set(pos, t); } } int longest = 0; ArrayList<Integer> maxBegins = new ArrayList<>(); for (int i = tempNum - 1; i >= 0; i--) { int t = temps[i]; // we use negatives here to keep the binary search happy // first find the maximum increasing subsequence in the suffix that // starts at i int pos = bisectLeft(maxBegins, -t); longest = Math.max(longest, prefLongest[i] + pos); // then insert the changed temperature for later iterations int insertPos = bisectLeft(maxBegins, -t - maxCheating); if (insertPos == maxBegins.size()) { maxBegins.add(-t - maxCheating); } else { maxBegins.set(insertPos, -t - maxCheating); } } System.out.println(longest); } private static int bisectLeft(List<Integer> arr, int x) { int lo = 0; int hi = arr.size(); while (lo < hi) { int mid = (lo + hi) / 2; if (arr.get(mid) < x) { lo = mid + 1; } else { hi = mid; } } return lo; } }
""" this code here treats the change as incrementing the suffix instead of decrementing the prefix as in the editorial but it's basically the same thing """ from bisect import bisect_left temp_num, max_cheating = [int(i) for i in input().split()] temps = [int(i) for i in input().split()] assert temp_num == len(temps) # this[i] = the longest subsequence that ends at and contains temps[i] pref_longest = [] min_endings = [] # standard LIS stuff for i, t in enumerate(temps): pos = bisect_left(min_endings, t) pref_longest.append(pos + 1) if pos == len(min_endings): min_endings.append(t) else: min_endings[pos] = t longest = 0 max_begins = [] for i in range(temp_num - 1, -1, -1): t = temps[i] # we use negatives here to keep the binary search happy # first find the maximum increasing subsequence in the suffix that starts at i pos = bisect_left(max_begins, -t) longest = max(longest, pref_longest[i] + pos) # then insert the changed temperature for later iterations insert_pos = bisect_left(max_begins, -t - max_cheating) if insert_pos == len(max_begins): max_begins.append(-t - max_cheating) else: max_begins[insert_pos] = -t - max_cheating print(longest)