CEOI 2018 - Global Warming

Authors: Albert Ye, Kevin Sheng

Official Analysis

We can view the temperatures as an array vv. We want to decrement one contiguous interval by a value dxd \le x such that the length of the longest increasing subsequence is longest possible. Note that we don't need to consider incrementing as well because every interval's decrease corresponds to another interval's increase.

Subtasks 1-3: Brute Force

One key observation is that it is useless to subtract dd from any interval [l,r][l,r] as opposed to just [1,r][1, r] for any l1l \neq 1. Additionally, observe that it is optimal to always subtract xx from the interval [1,r][1, r] no matter what.

An O(n2logn)\mathcal{O}(n^2 \log n) algorithm would involve brute forcing for all prefixes. Subtract xx from each interval [1,i][1, i] for all i{1,2,,n}i \in \{1, 2, \dotsc, n\} and then find the LIS after each subtraction.

Subtask 4: One pass

Take the LIS of the array. Any O(nlogn)\mathcal{O}(n \log n) algorithm to find the LIS will pass.

General Solution

For each ii, let LiL_i be the length of the longest increasing subsequence that ends at and contains ii and RiR_i be the length of the longest increasing subsequence starting at ii after [1,i][1, i] is decremented. We can compute each RiR_i by storing the length of the longest decreasing subsequence for each prefix of the reverse of the input array.

The final answer is maxi{0,1,,n}Li+Ri1\max_{i \in \{0, 1, \dotsc, n\}} L_i+R_i-1.

Implementation

In the implementation LiL_i is preflongestipref_longest_i and Ri1R_i-1 is the variable pospos in the second for loop.

C++

#include <bits/stdc++.h>
using namespace std;
int temps[200005];
int pref_longest[200005];
int main() {
int n;
int x;
cin >> n >> x;

Java

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 {

Python

"""
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)

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!